[면접대비] 퀵정렬

퀵정렬(Quicksort)

매우 빠른 정렬 알고리즘으로 특히 평균 시나리오에서 효율적이다.

분할(partitioning) 개념에 기반한다.

분할

• 배열의 임의의 수를 고른다. 이 수는 피벗(pivot)이라고 부른다.
• 피벗보다 작은 수는 피벗의 왼쪽에, 큰 수는 피벗의 오른쪽에 둔다.

배열에서 분할 구현 방법

1. 왼쪽 포인터를 한칸씩 옮기며 피벗과 값을 비교한다. 피벗보다 크거나 같으면 멈춘다(값 A).

2. 오른쪽 포인터를 한칸씩 옮기며 피벗과 값을 비교한다. 피벗보다 작거나 같으면 멈춘다. 또는 배열 맨앞에 도달해도 멈춘다(값 B).

3-1. 값 A의 위치와 값 B의 위치를 바꾼다. 다시 1을 반복한다.

3-2. 값 A의 위치가 값 B의 위치를 넘어선 경우 왼쪽 포인터의 값과 피벗을 교환한다.

결과적으로 완전히 정렬되지는 않으나 분할된 배열을 얻을 수 있다.

4. 피벗의 양쪽을 배열로 보고 재귀함수를 적용해 1~3을 동일하게 수행한다.

5. 하위 배열이 0, 1개 포함이라면 기저조건에 해당된다. 해당 함수는 여기서 종료된다.

 

삽입 정렬과 퀵 정렬의 빅 오 비교

	최선의 경우	평균적인 경우	최악의 경우
삽입 정렬	O(N)	O(N^2)	O(N^2)
퀵 정렬	O(NlogN)	O(NlogN)	O(N^2)

 

평균적인 경우에 퀵 정렬은 삽입 정렬보다 빠르다.

많은 언어에서 내장 정렬 함수를 구현하는데 사용된다.

퀵 셀렉트

배열을 정렬하지 않아도 되지만 몇번째로 작은 값, 또는 몇번째로 큰 값을 구할 때 사용할 수 있다.

퀵 정렬과 이진 검색의 요소를 사용한다.

 

피벗을 선택하여 분할을 1회 진행한다.

5번째 셀에 피벗이 위치한다면, 피벗 값은 배열 내에서 다섯번째로 작다.

만약 2번째로 작은 값을 구한다면 왼쪽의 배열에서 구할 수 있을 것이다.

전체 배열을 정렬하지 않고도 값을 찾을 수 있다.