퀵 정렬(Quick Sort)

개념

분할 정복을 기반으로 정렬되는 알고리즘이며, 대용량 데이터를 정렬할 때 유리합니다.

추가적인 공간 필요 X

피벗을 기준으로 나누어진 두 개의 집단 사이에서 요소의 교환이 일어나는 불안정한 정렬입니다.

 

병합 정렬(Merge Sort)와의 차이점은

병합 정렬은 수열의 절반을 나누어 분할 정복을 수행하지만

퀵 정렬은 피벗을 기준으로 분할 정복을 수행합니다.

 

로직

피벗을 기준으로 2개의 배열로 분할하고(분할)

분할된 배열을 각각 정렬한 다음(정복)

정렬된 배열을 합하는 방식으로 동작합니다. (결합)

큰 값과 작은 값을 나누어 정렬하는 방식으로 동작합니다.

 

1. 분할

입력 배열을 피벗을 기준으로 2개의 부분 배열로 분할합니다.

피벗의 좌측에는 피벗보다 작은 값을 두고

피벗의 우측에는 피벗보다 큰 값을 둡니다.

 

2. 정복

부분 배열을 정렬합니다.

부분 배열의 크기가 2 이상이라면, 순환호출을 이용해 다시 분할-정복을 진행합니다.

 

3. 결합

정렬된 부분 배열들을 하나의 배열로 합칩니다.

순환 호출이 한 번 진행될 때마다 최소한 하나의 피벗은 위치가 정해집니다.

 

 

 

코드

자바로 작성한 삽입정렬 코드는 다음과 같습니다.