퀵 정렬 ( Quick Sort )

퀵소트는 분할정복 알고리즘 중의 하나입니다.

분할정복이라면 무엇일까요? 간단히 얘기하면 주어진 문제를 더 작은문제로 쪼개어 재귀적으로 풀어 결과를 모아 더 큰 문제를 푸는 것입니다. 퀵소트에서 분할 정복 알고리즘이 어떻게 적용되었을까요? 차근차근 한번 알아보겠습니다.

1. 퀵소트 정의

1. 분할 

먼저 정렬하고자 하는 배열에서 임의의 피봇 값을 하나 정합니다. 피봇 값을 잡는 방법은 여러가지가 있는데 보통은 배열의 중간에 있는 값으로 잡습니다. 그 피봇을 기준으로 피봇의 왼쪽 배열은 피봇 보다 작은 값, 피봇의 오른쪽 배열은 피봇보다 큰 값으로 왼쪽과 오른쪽으로 "분할" 합니다. 

 

2. 정복

분할을 하고 난 왼쪽 배열과 오른쪽 배열의 크기가 0이나 1이 될 때까지 재귀적으로 분할정복을 반복합니다. 

 

피봇을 정하고 순환 호출이 한번 진행할때마다 최소 하나의 피봇 원소는 자리를 잡으므로 퀵소트 알고리즘은 반드시 끝난다는 것을 알수있습니다. 좀 쉽게 말해서 퀵소트는 한번의 순환 호출마다 피봇의 위치를 확정해가는 알고리즘입니다.

 

2. 퀵소트 예시

이제 한번 간단한 예시로 퀵소트가 어떻게 정렬을 하는지 한번 알아보겠습니다.

1. 배열에서 피봇을 선택합니다.

피봇설정

2. 현재 배열에서 피봇을 기준으로 왼쪽 배열의 가장 왼쪽 인덱스(s), 피봇을 기준으로 오른쪽 배열의 가장 오른쪽 인덱스 (e) 를 선택합니다.

3. S는 오른쪽으로 한칸씩, E는 왼쪽으로 한칸씩 옮겨줍니다. 단 여기서 만약 S 값이 pivot 값보다 더 크면 옮기던것을 멈춥니다. 마찬가지로 E 의 값이 pivot 값보다 더 작으면 E 를 옮기던 것을 멈춥니다.

4. 두 포인트 (S, E) 가 멈추면 S, E 의 값을 서로 스와핑 해줍니다.

5. 3, 4 번을 반복해줍니다. 

6. 계속 3, 4번을 반복하다가 S, E 가 서로 교차 되는 지점 즉 S 가 E 보다 더 오른쪽에 위치하는 순간 순회를 멈춥니다.

그렇게 되면 피봇으로 지정했던 값이 배열에서 위치를 잡게 됩니다. 즉 순회를 돌때마다 하나의 피봇이 위치를 잡게 됩니다.

이렇게 피봇을 기준으로 왼쪽은 피봇보다 작은 값들이, 오른쪽 배열에는 피봇보다 큰 값들이 들어옵니다. 위 순회를 이제 왼쪽 배열, 오른쪽 배열에 각각 적용합니다. 이 순회를 배열의 길이가 1로 쪼개질때까지 재귀적으로 반복합니다.

 

3. 퀵소트 시간복잡도

퀵소트는 분할정복 알고리즘이며 피봇을 정하여 피봇의 위치를 확정해 가는 알고리즘입니다.

피봇을 어떻게 정하냐에 따라서 최악의 시간 복잡도 O(n^2) 이 나오지만 한번 순회를 할때마다 순회길이가 반씩 줄어들기 때문에 일반적으로  O(nlogn) 입니다.

 

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog