퀵 정렬(1)

퀵 정렬

- 퀵 정렬은 가장 많이 사용되는 알고리즘이다.

- 퀵 정렬과 비교할 만큼 빠른 알고리즘에는 병합 정렬 알고리즘이 있다

- 기준을 설정하고, 다음 큰 수와 작은 수를 교환하여 리스트를 반으로 나누는 방식으로 동작한다

 

피벗 (Pivot)

- 피벗(Pivot) : 큰 숫자와 작은 숫자를 교환할 때, 교환의 기준을 말한다

- 퀵 정렬에서는 피벗(Pivot)이 사용된다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다

- 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다

- 피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬이 분류된다

 

호어 분할 방식(Hoare Parition)

- 가장 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식을 사용해보자

- 호어 분할(Hoare Partition) 방식은 첫 번째 데이터를 피벗으로 설정한다

- 피벗은 초록색 상자, 피벗보다 큰 데이터는 파란색 상자, 피벗보다 작은 데이터는 주황색 상자로 표현한다

 

1-1. 왼쪽에서부터 피벗보다 큰 데이터를 선택

 

1-2. 오른쪽에서부터 피벗보다 작은 데이터를 선택

 

1-3. 두 데이터의 위치를 변경

 

2-1. 그다음 피벗보다 큰 데이터와 작은 데이터를 찾는다

2-2. 두 데이터의 위치를 변경한다

 

3. 그다음 피벗보다 큰 데이터와 작은 데이터를 찾는다. 큰 데이터와 작은 테이터가 서로 엇갈렸다

 

4. 큰 데이터와 작은 데이터가 서로 엇갈린 경우, 작은 데이터와 피벗의 위치를 서로 변경한다

 

5. 피벗을 기준으로 왼쪽의 데이터는 모두 피벗보다 작고, 오른쪽의 데이터는 피벗보다 크다

 

 

이러한 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다

 

 

왼쪽 데이터는 모두 피벗보다 작고 오른쪽 데이터는 모두 피벗보다 크다.

왼쪽 리스트와 오른쪽 리스트에서도 각각 피벗을 설정하여 동일한 방법으로

정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 이루어진다

 

호어 분할의 전체 방식은 위와 같이 정리할 수 있다