퀵 정렬(Quick Sort)
퀵정렬?
퀵 정렬은 빠른 속도와, 간단한 구현방법 때문에
가장 많이 사용하는 정렬 방법으로 알려져 있습니다.
구현방법이 간편하다고 하지만, 개인적으로 이해하는데 시간이 좀 걸렸습니다.
퀵 정렬은 피벗으로 왼쪽에는 작은 값 오른쪽에는 큰값으로 정렬하는 방법입니다.
피벗?
특정 기준은 피벗(pivot)이라고 부릅니다.
복잡도
최악의 경우의 복잡도는 아래와 같지만
(최악의 경우 : 피벗이 가장 작은 수 이거나 가장 큰 수가 계속 선정되는 경우)
평균적인 복잡도는 아래와 같습니다.
어떠한 방법?
피벗을 가장 마지막 인덱스로 설정했습니다.
아래와 같은 배열이 있을 때
피벗 6을 기준으로 왼쪽과 오른쪽 끝에서부터
왼쪽은 6보다 큰 수 오른쪽은 6보다 작은 수를 찾습니다.
양쪽 다 찾은 수가 있다면 자리를 교환 해줍니다.
교환 후 계속해서 진행 한 후
왼쪽과 오른쪽의 수가 같아 지면 종료하고
피벗과 만난지점의 자리를 바꿔줍니다.
자리를 바꾼뒤 확인 해보면
피벗 기준으로 왼쪽에는 작은 수 오른쪽에는 큰수만 오게 됩니다.
각각 나눠진 영역에서 반복해서 같은 방법으로 진행 하면 정렬이 됩니다.
반복은 재귀호출로 진행하게 됩니다.
배열과 재귀호출을 이용한 퀵 정렬 예제
퀵 정렬 함수
if문 : 재귀 호출을 통해 종료를 위한 조건문
첫번째 while : 피벗보다 작은 수 큰 수를 찾기위한 반복문
두번째, 세번째 while : 각각 피벗보다 작은 수, 큰수를 찾는 반복문
첫번째 재귀 호출 : 피벗 기준 왼쪽을 정렬하기 위한 재귀 호출
두번째 재귀 호출 : 피벗 기준 오른쪽을 정렬하기 위한 재귀 호출
배열 출력 함수
실행 함수
실행 결과
참고 : C로 배우는 알고리즘 (이재규)
위키백과(퀵 정렬)
관련 포스팅
[DataStructure] 기수 정렬(Radix Sort)
[DataStructure] 퀵 정렬(Quick Sort)
[DataStructure] 셸 정렬(Shell Sort)
[DataStructure] 버블 정렬(Bubble Sort)
[DataStructure] 삽입 정렬(Insertion Sort)
[DataStructure] 선택 정렬(Selection Sort)
'언어 > Data Strcuture' 카테고리의 다른 글
[C] 힙 정렬(Heap Sort) (0) | 2019.05.01 |
---|---|
[C] 기수 정렬(Radix Sort) (1) | 2019.04.30 |
[C] 셸 정렬(Shell Sort) (2) | 2019.04.23 |
[C] 버블 정렬(Bubble Sort) (0) | 2019.04.20 |
[C] 삽입 정렬(Insertion Sort) (0) | 2019.04.19 |