퀵 정렬은 찰스 앤터니 리처드 호어 라는 분이 1959년에 개발한 정렬 알고리즘입니다.
이름처럼 웬만한 상황에서는 빠른 알고리즘이고 많이 사용되고 있습니다.
최선 & 평균 시간복잡도는
최악 시간복잡도는
입니다.
퀵 소트가 동작하는 방법을 단순하게 표현한다면 다음과 같습니다. (오름차순 기준)
1. 가운데 값을 정한다 (기준점 4)
▼
{2 3 1 6 4 8 5 7 9}
2. 값을 기준으로 작은건 왼쪽으로 큰건 오른쪽으로 보낸다.
▼
{2 3 1 4 6 8 5 7 9}
3. 가운데 값을 기준으로 구역을 나누고 구역마다 다시 가운데 값을 정한다. (기준점 3,5)
▼ ▼
{2 3 1} 4 {6 8 5 7 9}
4. 구역마다 1~ 3번을 다시 반복한다.
▼ ▼
{2 1 3} 4 {5 6 8 7 9}
5. 또 다시 구역을 나눠서 나눌 구역이 없을 때 까지 반복한다...
위의 과정을 구현한 소스코드는 이런모양 (출처 : 위키백과)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | void quickSort(int arr[], int left, int right)//정렬할 배열,구역의 왼쪽,구역의 오른쪽 { int i = left, j = right;//i=왼쪽 ,j=오른쪽 int pivot = arr[(left + right) / 2];//기준점은 구역의 중간 int temp; do { while (arr[i] < pivot)//왼쪽이 피벗보다 (어차피)작다면 스킵 i++; while (arr[j] > pivot)//오른쪽이 피벗보다 (어차피)크다면 스킵 j--; if (i<= j)//위에서 걸러지지 못한건 서로 교체 { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } while (i<= j);//왼쪽이랑 오른쪽이랑 만날때까지 반복 /* 구역나눠 재귀 */ if (left < j)//왼쪽 구역 quickSort(arr, left, j); if (i < right)//오른쪽 구역 quickSort(arr, i, right); } | cs |
이 소스코드가 위에 설명한거랑 조금 달라보일 수 있는데
조금 달라보여도 자세히 보면 위 설명과 크게 다르지는 않습니다.
저 소스를 더 분석하자면...
1. 왼쪽(i) 오른쪽(j)과 가운데 값(피벗)이 있다.
i ▼ j
{2 3 1 6 4 8 5 7 9}
2. i, j가 피벗을 기준으로 제대로 된 위치에 있으면 스킵
(이상황에서는 결국 j랑 피벗이랑 같은위치)
i▼(j)
{2 3 1 6 4 8 5 7 9}
3. 제대로 된 위치가 아니면 i랑 j의 위치를 변경
{2 3 1 4 6 8 5 7 9}
4. 왼쪽부터 j까지 , i부터 오른쪽까지 구역나눠서 반복
{2 3 1 4} {6 8 5 7 9}
그리고 퀵소트의 원리를 보여주는 헝가리 민속 탭 떈쓰~ (겁나 흥겨움)
'프로그래밍 > 알고리즘,자료구조' 카테고리의 다른 글
| 해시 -프로그래머스 고득점 Kit를 위한 선행학습 (0) | 2020.10.11 |
|---|
stuban
ㅇ.ㅇ
