퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬 #include int num = 10; int data[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; int main(void) { quickSort(data, 0, num - 1); for (int i = 0; i = ed) return; // st > ed : 값이 원래 자리에 들어간 경우 // ( ex_ 정렬된 값 1 2 3 5 6 7 8 9 10 1은 이미 정렬이 되어있다. int key = st; // 그러므로 quickSo..

앞서 배운 선택 정렬 , 버블 정렬, 삽입정렬 알고리즘 모두 시간 복잡도 O(N ^ 2)를 가지는 알고리즘이다. 이러한 알고리즘은 데이터의 갯수가 10만 개만 넘어가도 일반적인 상황에서는 매우 사용하기 어려운 알고리즘이다. ​ 퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬 -> 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤 배열을 반으로 나눈다. ​ 퀵 정렬은 특정한 기준 값이 있는데 이를 피벗이라고 하며 피벗값을 기준으로 왼쪽과 오른쪽으로 나눈다. 퀵 정렬의 예 3 7 8 1 5 9 6 10 2 4 피벗 값(일반적으로 가장 앞에있는 값) : 3 3 2 8 1 5 9 6 10 7 4 검색했을 때 3보다 큰 7과 N이 1,000,000일 때 ? N : 20

삽입 정렬 : 각 숫자를 적절한 위치에 삽입하는 정렬 방법 ​ 1 10 5 8 7 6 4 3 2 9 를 오름차순으로 정렬하시오 int main(void) { int i, j, tmp; int array[10] = { 1,10,5,8,7,6,4,3,2,9 }; for (int i = 0; i array[j + 1]) { tmp = array[j]; array[j] = array[j + 1]; array[j + 1] = tmp; j--; } } for (i = 0; i < 10; i++) { printf("%d\n", array[i]); } return 0; } 삽입 정렬은 필요할 때만 위치를 바꾸는 특성이 있다. ​ 삽입정렬..

버블 정렬 : 옆에 있는 값과 비교해서 더 작은 값을 반복적으로 앞으로 내보내는 알고리즘 ​ 1 10 5 8 7 6 4 3 2 9 를 오름차순으로 정렬하시오 int main(void) { int i, j, tmp; int array[10] = { 1,10,5,8,7,6,4,3,2,9 }; for (i = 0; i array[j + 1]) { tmp = array[j]; array[j] = array[j + 1]; array[j + 1] = tmp; } } } for (i = 0; i < 10; i++) { printf("%d\n", array[i]); } return 0; } 1 10 5 8 7 6 4..

병합 정렬 : 피벗 값이 없고 일단 정확히 반으로 자르고 나중에 정렬 -> 퀵 정렬과 마찬가지로 ' 분할 정복' 방법을 채택한 알고리즘 ​ 정확하게 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)의 시간 복잡도를 가진다. ​ 76583519를 병합 정렬을 사용하여 정렬한다고 했을 경우 시작 : 7 6 5 8 3 5 9 1 1 : 67 58 35 19로 2개씩 묶어서 2개씩 각각 정렬해 준다. 2 : 5678 1359로 4개씩 묶어 4개씩 각각 정렬해 준다. 3 : 13556789 ​로 하나로 합치며 정렬하여 준다. ​ 이때 폭을 N 높이를 log2N이라고 한다. 즉, 위 정렬은 8 * log28(3) 번 연산을 한다. 1번에서 8번 -> 76 정렬 때 2번, 58 정렬 때 2번, 35 정렬 ..

​ ​ 알고리즘 순서도의 도형 각각의 의미이다!

선택정렬 : 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘 ​ 1 10 5 8 7 6 4 3 2 9 를 오름차순으로 정렬하시오 1 10 5 8 7 6 4 3 2 9 을 정렬하기 위해서는 ​ 1 ~ 10 => 10 , 2 ~ 10 => 9 , 3 ~ 10 => 8 .... , 10 ~ 10 => 1 => 1 + 2 + 3 + 4 + ... + 10 10 * (10 + 1) / 2 = 55 (1 + 7) / 2 * 4 ​ 1 ~ 10 까지 정렬하기 위해서 최소한 55번의 비교 연산을 해야한다. ​ 즉 위 알고리즘의 수행시간은 => N * (N + 1) / 2 로 나타낼 수 있다. 컴퓨터에서는 "/ 2" 나 "+ 1" 는 N의 값이 클 경우 의미가 없기 때문에 무시한다 ​ 그렇기 때문에 결과적으로 N ..