1000만개 정렬 : https://www.acmicpc.net/problem/2751 ================================== 풀이 ==================================== ​ 퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬 int data[1000000]; void quickSort(int *data, int start, int end) { if (start >= end) { return; } int key = start, st = start + 1, ed = end, tmp; while (st = data[st] && st ed) { tmp = data[key]; data[key] = data[ed]; data[ed] =..

퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬 #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