퀵 정렬 quick sort

 

퀵 정렬 개요 quick sort 

- 영국의 컴퓨터 과학자 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘

 * 토니 호어는 프로그래밍 언어의 정의와 설계에 대한 공헌으로 튜링상 수상

- 피벗을 기준으로 작은 데이터는 앞으로, 큰 데이터는 뒤로 분리해나가며 정리하는 방법.

- n개의 데이터 정렬시. 최악의 경우 O($n^2$), 평균적으로 O(n log n)번의 복잡도를 가진다.

            찰스 앤터니 리처드 호어(토니 호어).             출생일 :  1934년 1월 11일 현(87세)

 

 

퀵 정렬 알고리즘 

1. 리스트에서 하나의 원소를 고르고, 이 원소를 피벗이라 부른다.

2. 피벗을 기준으로 작은 원소들은 피벗 앞으로, 큰 원소들은 피벗의 뒤로 리스트를 둘로 나눈다.

3. 분할된 두 리스트에 대해 재귀적으로 수행한다.

 

 

 

 

 

퀵 정렬 예제

(1)

5 - 3 - 7 - 6 - 2 - 1 - 4 - 8

                p

5 - 3 - 2 - 1 - 4 - 6 - 7 - 8

                          p

 

(2)

5 - 3 - 2 - 1 - 4     6    7 - 8

     p                                p

2 - 1 - 3 - 5 - 4     6 - 7 - 8

           p

 

(3)

2 - 1       3   5 - 4   6-7-8

p                  p 

1 - 2        3   4 - 5   6-7-8

 

(4) 

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8

 

 

퀵 정렬 예제 2

https://blog.naver.com/sehoon95/80212692808?viewType=pc

 

 

퀵 정렬의 시간 복잡도

- 길이가 n인 리스트, 매번 n번 비교

- 재귀 호출 횟수가 $log_{2} n$

- 평균 시간 복잡도 : n $log_{2} n$

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

 

 

 

 시간 복잡도 비교

 

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html