퀵
-
[Sort] 퀵 정렬(Quick sort)CSE/Sort 2015. 6. 12. 15:40
퀵 정렬(Quick Sort) [출처: 위키] 정의: 퀵정렬은 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다. 먼저 기준 값을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(Divide)한다. 왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다. 위의 정의를 잘 이해 하셔야 퀵 정렬이 쉽게 이해 됩니다!!! 1단계 위 처럼 8개의 값을 정렬 합시다!! 저기 보시면 2라는 숫자가 기준 값(Pivot)이 됬는데요... 기준 값을 구하는 법은 배열의 시작 값과 끝 값의 인덱스를 더한 것에서 2를 나눠줍니다. 즉 위에서는 ( 0 + 7 ) / 2 = > 3 이라는 인덱스 값이 나오니깐 배열의 3번째는 2라는 숫자입니다!!! ..