퀵 정렬 (Quick 정렬)

안녕하세요 오늘은 정렬 중 분할 정복으로 유명하고 빠른 정렬로 유명한 퀵 정렬에 대하여 공부해도록 하겠습니다

출처 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

( 퀵 정렬을 간단히 나타낸 gif )

먼저 간단한 예제를 통해서 무엇인지 알아보도록 하죠!!!

위와 같은 배열이 있고 이를 퀵정렬로 정렬하기위해서는 어떻게 해야할까요?

먼저 퀵정렬의 특징은 pivot이라는 중간값을 선택하는 것부터 시작합니다 또한 이를 선택하는 방법에는 두가지가 있는데

1. 배열의 중간값

2. index의 첫번째 

이중 1번째인 중간값을 선택한다고 했을때 Pivot의 값은 배열의 중간값인 9가 선택이 됩니다

다음 퀵 정렬은 다음과 같은 규칙에 의해서 정렬이 진행됩니다

1. left 즉 배열의 첫번째 인덱스에서 pivot보다 큰값을 찾아간다

2. 그 다음 right 배열의 마지막 인덱스 부터 pivot 보다 작은 값을 찾아간다

3. left와 right가 정해지면 서로 교환을 해준뒤 다시 1번과 2번을 진행한다

4. 만약 left와 right의 값이 작거나 같다면 right의 위치를 pivot과 교환해준다

5. 배열의 길이가 1이 될때까지 1 ~ 4를 반복

그렇다면 이제 순서에 따라 예제를 정렬 해보도록 하겠습니다

9의 pivot에서 left를 보니 pivot보다 크니 멈추고 right를 보니 pivot보다 작아 left와 right를 교환해주고 각각의 index를 변화시킵니다

그렇게 마저 진행을 하던중 24에서 left 1에서 right가 잡히고 여기서 교환을 한번더 진행해줍니다

그 뒤 index를 진행하고 보니 left와 right의 위치가 같아 앞서 말한 4번의 규칙인 pivot과 교환을 해주고 이 인덱스 9는 정렬이 완료됩니다

이때 pivot의 왼쪽 배열과 오른쪽 배열을 보시죠!!!

왼쪽 배열은 pivot 보다작고 오른쪽 배열은 더 큰게 보이시나요? 이렇게 차츰 차츰 정렬이 되어간다고 보시면 될 것 같습니다

그 다음 왼쪽 배열부터 다시 정렬을 시작합니다 pivot을 인덱스의 중간으로 두고 left와 right를 다시 교환합니다

다시 3이 left와 right의 인덱스가 같아 pivot과 교환을 해주고 고정합니다

그런데 왼쪽 배열과 오른쪽 배열의 길이가 1이기 때문에 처음의 {24, 12, 10} 배열을 정렬하러 이동합니다

동일한 방식으로 left와 right를 교환해주고 

left와 right의 위치가 같기에 pivot과 교환한뒤 정렬을 완료하고 보니 정렬이 안된 모든 index의 길이는 2보다 작습니다

즉 여기서 정렬이 완료가 된 것 입니다

퀵 정렬의 장점은 시간복잡도가 평균 O(n log n)으로 O(n^2)에 비해 굉장히 빠른 속도를 보여주는데 퀵 정렬에도 단점이 존재합니다

바로 pivot의 값을 최소값이나 최댓값으로 설정했을때 최악의 경우로 O(n^2)만큼 진행이 됩니다

아래는 구현 코드를 작성하고 퀵 정렬은 여기 까지로 마치도록 하고 다음에는 또 다른 분할병합 방법인 병합 정렬에 대하여 알아보도록 하겠습니다