누구나 자료구조와 알고리즘 - (10) 퀵 정렬(Quicksort)

 

 

 

 

 

퀵 정렬(Quicksort)

 

버블 정렬, 선택 정렬, 삽입 정렬같은 알고리즘이 있지만 대부분의 언어에서는 퀵 정렬(Quicksort)를 선택한다.

퀵 정렬은 매우 빠른 정렬 알고리즘으로 평균 시나리오에서 효율적이다. 최악의 시나리오에서는 삽입 정렬, 선택 정렬과 성능이 유사하지만 대부분의 경우의 평균 시나리오에서는 훨씬 빠르다.

 

 

1.1. 퀵 정렬의 분할

퀵 정렬은 분할이라는 개념에 기반한다.

배열을 분할 한다는 것은 배열로부터 임의의 수인 피벗(pivot)을 가져와 피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 둔다.

 

1. 여기서 3을 피벗으로 지정하고 두 개의 포인터를 사용한다.

0 pointer1

5

2

1

6 pointer2

3 pivot

 

2. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.

0

5 pointer1

2

1

6 pointer2

3 pivot

 

3. 오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다.

0

5 pointer1

2

1 pointer2

6

3 pivot

 

4. 둘을 교환한다.

0

1

2

5

6

3 pivot

 

5. 교환하다가 왼쪽 포인터가 오른쪽 포인터에 도달하면 이동을 중지하고 왼쪽값과 피벗을 교환한다.

0

1

2

3 pivot

6

5

분할이 끝나면 피벗 왼쪽에 있는 값은 모두 피벗보다 작고 피벗 오른쪽에 있는 값은 모두 피벗보다 크다고 확신할 수 있다.

 

 

 

 

1.2. 퀵 정렬

• 퀵 정렬은 분할과 재귀로 이뤄진다. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또 다른 배열로 보고 1단계와 2단계를 재귀적으로 반복하는 것이다.
• 퀵 정렬은 새로운 빅 오 카테고리로 O(NlogN) 알고리즘이다. (원소가 N개 일 때 원소가 2배로 늘어날 때 마다 필요한 단계수가 한 단계씩 늘어나기 때문에 N x logN이다.) 이 알고리즘은 가장 빠른 정렬 알고리즘이다.
• 많은 알고리즘에서 정렬을 더 큰 프로세스의 일부로 사용한다. 그러면 최소 O(NlogN) 알고리즘까지 도달할 수 있다.

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.