-
[Sort] 퀵 정렬(Quick sort)CSE/Sort 2015. 6. 12. 15:40
퀵 정렬(Quick Sort)
[출처: 위키]
정의: 퀵정렬은 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다.
먼저 기준 값을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(Divide)한다.
왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고,
오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다.
위의 정의를 잘 이해 하셔야 퀵 정렬이 쉽게 이해 됩니다!!!
1단계
위 처럼 8개의 값을 정렬 합시다!!
저기 보시면 2라는 숫자가 기준 값(Pivot)이 됬는데요...
기준 값을 구하는 법은 배열의 시작 값과 끝 값의 인덱스를 더한 것에서 2를 나눠줍니다.
즉 위에서는
( 0 + 7 ) / 2 = > 3
이라는 인덱스 값이 나오니깐 배열의 3번째는 2라는 숫자입니다!!!
그렇게 피봇을 정하고 나면 퀵 정렬이 시작이 됩니다!!
위 그림처럼 L 과 R 이 퀵 정렬을 시작하기 위해 있는 변수입니다.
L과 R이 하는 일을 알아야 겠죠?!?!
L은 피봇 값보다 크거나 같은 값을 찾습니다.
R은 피봇 값보다 작은 값을 찾습니다.
1) 이 두 행위를 하는 녀석들이 둘이 같은 자리에서 만나기 전에!
값을 찾으면 둘이 swap을 해줍니다!
2) 두 L과 R이 값을 하나만 찾고 나머지가 만나게 되면
만난 값과 피봇 값을 swap 합니다!
위 두 개념이 좀 중요해요!!! 자 그럼 시작 합니다!
시작과 동시에 L은 피봇 값보다 크거나 같은 값!을 찾았죠??
L은 저기서 가만히 있습니다.
그럼 R이 계속해서 움직입니다.
계속 움직여서 확인 결과 피봇 값 (2) 보다 작은 값이 없어서
L과 만납니다!!
아까 L과 R이 만나면 어떻게 되죠??
2) 의 규칙을 따라서,
69와 2가 swap 되는 거죠???
결국 이렇게 해서 1단계가 마무리 됩니다! 아직까진 크게 정렬이 되어있진 않아요!!!
2단계
그럼 2단계를 시작하는데 다시 피봇을 정해야 합니다!!!
0 부터 6의 인덱스 이므로
3이라는 위치값이 피봇이네요!
아래와 같이 되겠네요~
그럼 먼저, L을 움직입니다!!
10은 피봇보다 작죠? pass
30은 피봇보다 큽니다!!! 올치 걸려 드러부렀쓰야~
L이 30을 Hold 합니다.
L이 Hold 된 상태 이므로 R을 움직여서 비교해볼 차례입니다!!!
먼저, 22는 피봇보다 크므로 pass
다음 31도 크므로 pass
8은 피봇보다 작네요~???????
그럼 R이 8을 Hold!!
으잉??? L과 R이 값을 찾았네요????
1)의 규칙을 적용해서 !!!!
L과 R의 값을 swap!!!!
값이 swap 되었습니다!
그러고 나서 다시 L 과 R은 만날때 까지 계속 움직입니다!
다시, L을 비교하면 8은 아까 했으니깐,
69로 넘어가서 Hold 죠??
L은 69에서 멈춤니다.
R은 피봇을 넘어 L과 만납니다.
결국 둘이 만났죠??
2)의 규칙!!!!!
LR의 자리와 피봇값을 swap!!!
으잉????
L과 R의 자리만 바꾼다 하지 않았소 자네...?
그렇죠... L 과 R만 바꿨습니다 저는...
다만 좀 다음 단계를 준비하느라 이렇게 벌써 만들어 버렸네요...
이제부터 퀵 정렬의 진가!!!
Devide & Conquer를 제대로 하게 되네요!
먼저 아까 2는 정렬이 다되어서 범위 내에 빠졌으므로 녹색으로 표현
그러고 나면 보라색은 LR 값이므로 신경 쓸 필요 없습니다!
그럼 저 괄호로 표시된 2 부분 과!
피봇 값이 보이시죠???
네. 이번 단계에서 정한 피봇이 단계를 끝나면서 2개의 그룹으로 나눠 진겁니다...
무슨 말씀이신지 잘 이해 못할 거라 이해합니다...
설명을 워낙 잘 못해서리...
중요한 점은!!!
16이라는 피봇 의 왼쪽은 16보다 작은 값으로 구분 되있고!
오른쪽은 16보다 큰 값이죠???
네. 결론은 그룹핑 된 거 따로 해서 정렬을 통해 진행이 된다는 거죠!!!!
이정도로 설명하고 진행을 해보도록 하겠습니다!!!
다음 단계는 저기 보이는 10 과 8을 정렬합니다!!!
왜냐하면 그러하기 때문이죠....
3단계
먼저 피봇은 아래와 같습니다!
0 + 1 / 2 = 0 이죠 결국,
피봇을 정하고
L 과 R의 위치를 정해야 합니다!!
먼저, L은 피봇값과 일치하는 값이므로 Hold!
R은 피봇값보다 작은 값이므로 Hold!
두값이 swap 되겠죠???
1) 규칙으로 인해서!!!
그러면서 결국 피봇 원소를 swap 했으므로 비교를 안하게 됩니다!
위의 상태에서 아래상태로 해서 이번 단계를 종료하게 되는거죠!!
이 상태에서 8이 혼자 남습니다...
혼자 남게되면 정렬이고 나발이고 패스하게 되므로 이번 단계에서의
아까 나눠져있던 왼쪽 그룹핑에 대한 정렬은 마무리가 됩니다.
4단계
이번 단계는 오른쪽 그룹핑에 대한 정렬을 할 차례입니다!
피봇을 정하면 인덱스가 1인 위치가 피봇이 됩니다!
30!!
자 그럼 시작해 보시죠!!
L은 그냥 벌써 Hold! 가 되죠??? ( 30 보다 큰 값이니깐요.)
R도 Hold ! (30 보다 작은 값이니깐요.)
그럼 둘이 swap 해줍니다!!
다음으로 다시 비교를 해나가면!
L은 결국 30(피봇) 에서 멈추 겠죠???
R도 계속 움직여서 피봇에서 멈추게 됩니다! ( 왜냐하면 다 피봇보다 큰 값이니깐요.)
결국 L과 R은 Pivot 이네요??
이렇게 되서...
22는 8과 같이 정렬을 할 필요가 없어지고
오른쪽의 새로운 그룹에 대해 정렬을 다음 단계에서 진행하면 끝입니다!!!
5단계
피봇까지 구해서 정렬을 시작할라고 봤더니 뭐... 시작해 봅시다!
L은 피봇이니깐 Hold!!
R은 69니깐 pass
그러면 L과 R과 Pivot 이죠???
31의 위치는 확정이 됩니다!
이렇게 해서 69가 남지만 결국 원소가 한개 이므로 끝이 납니다...
이렇게 해서 정렬이 끝났네요...
휴...
그렇죠...
삽입 버블 선택 이거와는 또 다른
개념으로 정렬을 해서 어렵죠!!! ㅠㅠ
이해 합니다...
그래도 이게 또 위에 들과는 다르게 좀 더 좋은 성능을 뽑아내므로 알아 두세요!!!
이 퀵 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!
Worst일 경우만
Best와 average는
을 갖습니다!
소스 코드를 통해 보도록 하죠!!
QuickMain.java
123456789package Quick;public class QuickMain {public static void main(String[] args) {int [] arr = {69, 10, 30, 2, 16, 8, 31, 22};QuickSort.quickSort(arr, 0, arr.length - 1);}}cs QuickSort.java
123456789101112131415161718192021222324252627282930313233343536373839404142434445package Quick;import Selection.SelectionSort;public class QuickSort {static int i = 0;public static void quickSort(int[] arr, int begin, int end) {if (begin < end) {int p = partition(arr, begin, end);quickSort(arr, begin, p - 1);quickSort(arr, p + 1, end);}}public static int partition(int arr[], int begin, int end) {int left = begin;int right = end;int pivot = (left + right) / 2;System.out.println("[퀵 정렬 " + ++i + "단계: pivot: " + arr[pivot]);while (left < right) {while ((arr[left] < arr[pivot]) && (left < right))// L 움직이는 부분left++;while ((arr[right] >= arr[pivot]) && (left < right))// R 움직이는 부분right--;if (left < right) {SelectionSort.swap(arr, left, right);}}SelectionSort.swap(arr, pivot, right);SelectionSort.printArr(arr);return left;}}cs 'CSE > Sort' 카테고리의 다른 글
[Sort] 기수 정렬(Radix Sort) (0) 2015.06.12 [Sort] 합병 정렬(Merge Sort) (0) 2015.06.12 [Sort] 셸 정렬(Shell Sort) (0) 2015.06.12 [Sort] 삽입 정렬(Insertion sort) (0) 2015.06.12 [Sort] 버블 정렬(Bubble Sort) (0) 2015.06.12 [Sort] 선택 정렬(Selection Sort) (0) 2015.06.12
