[정렬] 퀵 정렬

퀵 정렬이란

기준 값을 선정하여 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘 입니다.

기준값에 따라 시간 복잡도가 평균 O(nlogn)에서 최악의 경우에는 O(n ² )

 

퀵 정렬 과정

1. 데이터 분할을 하는 pivot데이터를 설정
2. pivot을 기준으로 아래 2.1 ~ 2.5 과정을 거쳐 데이터를 2개의 집합을 분리
   1. start 가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동
   2. end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동
   3. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end 가 가리키는 데이터보다 작으면 start, end가 가리키는 데이터를 swap 하고 start 는 오른쪽, end는 왼쪽으로 한칸씩 이동
   4. start 와 end 가 만날 때 까지 2.1 ~ 2.3 을 반복
   5. start와 end 가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.
3. 분리 집합에서 각각 다시 pivot을 설정한다.
4. 분리 집합이 1개 이하가 될 때 까지 1~3을 반복

글로만 설명하면 이해가 쉽지 않기 때문에 위 내용을 그림을 통해 설명해보면,

 

1. 정렬해야 하는 배열이 존재하고 배열에서 pivot, start, end를 설정합니다.

일반적으로  pivot은 배열의 첫번째 수 혹은 마지막 수로 정합니다.

 

 

2. start 가 pivot 보다 작으면 start를 오른쪽으로 한칸씩 이동합니다.

3. start 가 pivot 보다 크기때문에 start 는 60에서 멈춥니다.

4. end 가 pivot 보다 크기 때문에 end 를 왼쪽으로 한칸 이동합니다.

5. end 가 pivot 보다 작기 때문에 end 는 5에서 멈춥니다.

6. start와 end 를 swap 하고 pivot 데이터 45는 swap 한 사이로 들어가게 됩니다. 이렇게 되면 pivot (45)를 기준으로 왼쪽은 pivot보다 작은 수 오른쪽은 pivot보다 큰수들이 남게 됩니다.

 

7. 이전 pivot (45)의 왼쪽에서 다시 start, end, pivot을 설정 후 위 과정을 반복합니다.

 

이렇게 퀵 정렬에 대해 알아보았습니다. 설명이 부족하거나 틀린 부분이 있다면 피드백 부탁드립니다.