퀵 정렬(Quick sort)

퀵 정렬은 기준값을 정해 그 값으로부터 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬한 뒤 분할을 반복하는 방식으로 순서는 아래와 같다.

 

1. 기준점을 하나 잡는다.

   ㄴ이때 기준점은 어떤 값이든 상관 없다.

2. 오른쪽 먼저 오른쪽이 왼쪽보다 클 경우에만 반복하며, 해당 배열값이 기준점보다 크면 그 앞에 인덱스값을 비교한다.

3. 기준점보다 작은 값을 찾았을 경우 중지한다.

4. 이번에는 왼쪽을 시작하는데 오른쪽이 왼쪽보다 클 경우에만 반복하며, 기준점보다 작으면 그 뒤에 인덱스값을 비교한다.

5. 기준점보다 큰 값을 찾았을 경우 중지한다.

6. 오른쪽과 왼쪽의 인덱스값을 서로 바꾼다.

7. 이후 왼쪽의 값과 기준점을 바꾼다.

8. 배열의 시작부터 왼쪽 - 1 인덱스까지, 왼쪽 + 1인덱스부터 배열의 끝까지로 나눠 다시 정렬을 반복한다.

9. 최종적으로 배열의 크기가 1일때 정렬이 완료된다.

 

시간복잡도는 (배열의 크기)log(배열의 크기) 이다.

1행 - 기준값을 담을 변수

2, 3행 - 각각 왼쪽, 오른쪽 인덱스값을 담을 변수

 

14행 - 퀵정렬이 이루어지는 부분

17행 - 2~3번 과정

25행 - 4~5번 과정

33행 - 6번 과정

38행 - 7번 과정

42행 - 8번 과정

        ㄴ각각 둘로 쪼개서 다시 퀵정렬을 돌리기 때문에 재귀함수로 호출한다.