퀵정렬 원리 아주 쉽게 이해하기(Quick Sort)

안녕하세요. 알고리즘을 공부하던 중, 퀵 정렬(Quick sort) 이 한 번에 이해가 가지 않아서, 원리를 파헤치는 글을 올리게 되었습니다!!

 

퀵 정렬 방식은 간단합니다.

 

1) pivot(기준)을 정한다.

2) pivot의 제자리를 찾아준다.

 

이를 반복하는 것이 퀵 정렬입니다.

퀵 정렬을 하는 방식은 여러 가지가 있지만 저는 제가 배운 호어 분할(Hoare Partition) 방식으로 설명하겠습니다.

 

예를 들어 1~5 의 숫자가 적힌 카드가 무작위로 나열되어있다고 해봅시다. 이를 오름차순으로 정렬하는 것이 우리의 목표입니다.

?

?

?

?

?

 

 

먼저 가장 첫 번째 카드의 원소를 pivot으로 정합니다.

Pivot

?

?

?

?

 

 

그럼 뒤에 나열된 4장은 각각 Pivot의 카드에 적힌 수보다 작거나, 큰 수들일 것입니다.

 

5장의 카드 나열을 Pivot 기준으로 생각해본다면 다음과 같은 경우의 수들이 있을 것입니다.

 

1) Pivot + Pivot 보다 큰 카드 4장

Pivot

⬆️

⬆️

⬆️

⬆️

 

2) Pivot + Pivot 보다 큰 카드 3장 + Pivot 보다 작은 카드 1장

Pivot

⬆️

⬆️

⬆️

⬇️

 

3) Pivot + Pivot 보다 큰 카드 2장 + Pivot 보다 작은 카드 2장

Pivot

⬆️

⬆️

⬇️

⬇️

 

4) Pivot + Pivot 보다 큰 카드 1장 + Pivot 보다 작은 카드 3장

Pivot

⬆️

⬇️

⬇️

⬇️

 

5) Pivot + Pivot 보다 작은 카드 4장

Pivot

⬇️

⬇️

⬇️

⬇️

 

 

 

이 때, 왼쪽부터 원소들을 검사하는 Left Filter 와, 오른쪽부터 원소들을 검사하는 Right Filter를 돌립니다.

 

 

Left Filter 는 왼쪽부터 돌면서 Pivot에 쓰인 값보다 작다면 넘어가고, 크다면 저장합니다.

Right Filter 는 오른쪽부터 돌면서 Pivot에 쓰인 값보다 크다면 넘어가고, 작다면 저장합니다.

 

 

카드가 다음과 같이 나열되어있을 때를 예시로 설명해보겠습니다.

 

3) Pivot + Pivot 보다 큰 카드 2장 + Pivot 보다 작은 카드 2장

Pivot

⬆️

⬆️

⬇️

⬇️

 

 

Left Filter와 Right Filter를 돌립니다.

Pivot

⬆️ (Left)

⬆️

⬇️

⬇️ (Right)

 

2번째 카드가 Pivot 보다 크므로, Left Filter 에는 2번째 카드가 저장되었고,

5번째 카드가 Pivot보다 작으므로 Right Filter에는 5번째 카드가 저장되었습니다.

 

두 필터에 값이 모두 저장되었다면, 그 두 카드의 위치를 바꿉니다.

Pivot

⬇️

⬆️

⬇️

⬆️

 

그리고 다음 카드부터 각각 또 필터를 돌립니다.

Pivot

⬇️

⬆️ (Left)

⬇️ (Right)

⬆️

 

3번째 카드가 Pivot 보다 크므로, Left Filter 에는 3번째 카드가 저장되었고,

4번째 카드가 Pivot보다 작으므로 Right Filter에는 4번째 카드가 저장되었습니다.

 

두 필터에 값이 모두 저장되었다면, 그 두 카드의 위치를 바꿉니다.

Pivot

⬇️

⬇️

⬆️

⬆️

 

그리고 다음 카드부터 각각 또 필터를 돌립니다.

Pivot

⬇️

⬇️ (Right)

⬆️ (Left)

⬆️

 

이 때, Left Filter와 Right Filter의 인덱스가 교차되었습니다.

이 때, Left FIlter 가 지나온 자리들은 Pivot보다 작은 수 이거나, 큰 수였다면 Right Filter의 Pivot 보다 작은 수로 교체된 수 입니다.

결국, Left FIlter 가 지나온 자리들은 Pivot보다 작은 수들로 이루어져있습니다.

 

Right Filter도 마찬가지입니다.

Right FIlter 가 지나온 자리들은 Pivot보다 큰 수 이거나, 작은 수였다면 Right Filter의 Pivot 보다 작은 수로 교체된 수 입니다.

결국, Left FIlter 가 지나온 자리들은 Pivot보다 큰 수들로 이루어져있습니다.

 

그렇기에 Right Filter 자리의 카드와 Pivot 자리의 카드를 바꾸면, 그 자리가 바로 Pivot 카드의 자리가 됩니다.

⬇️

⬇️

Pivot

⬆️

⬆️

 

Pivot의 제 자리를 찾아줬습니다.

이제 Pivot의 왼쪽 카드들과 오른쪽 카드들도 지금 했던 방식인

 

1) Pivot을 정하고

2) 그 자리를 찾아준다.

 

을 반복하면 퀵 정렬로 카드들을 오름차순으로 정렬하게 됩니다.