[TIL] 퀵 정렬

퀵 정렬은?

• 정렬 알고리즘의 꽃이라 불리는 알고리즘으로, '찰스 앤터니 리처드 호어'씨가 개발

• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행

• 하나의 리스트를 피벗 기준 비균등하게 분할하고, 분할된 리스트를 정렬하고 다시 합치는 분할 정복 알고리즘의 하나로 매우 빠른 수행 속도를 자랑

  • 합병 정렬과의 차이점은 리스트를 비균등하게 분할한다는 점

• 기준점(Pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모아줌으로써 정렬을 진행

시간 복잡도

• (최선) 레코드의 개수가 2의 거듭 제곱 형태로 나타날 경우 O(NlogN)

• (최악) 리스트가 계속 불균형하게 나뉘는 경우(이미 정렬된 리스트)에는 O(N^2)

퀵 정렬 방법

• 퀵 정렬은 기준점을 정한다고 앞서 언급했는데, 보통 기준점은 맨 앞에 있는 값을 기준점으로 잡고 시작한다.

        a. 현재 아래의 리스트에서 기준점은 가장 앞에 있는 3이며, 
        기준점을 기준으로 오른쪽으로는 보다 큰 값, 왼쪽으로는 보다 작은 값을 찾아준다.
        
		[3, 7, 8, 1, 5, 9, 6, 10, 2, 4]

        b. 3을 기준으로 큰 값은 바로 옆에 있는 7, 작은 값은 2이다.
           그리고 두 인덱스를 swap한다.

       		[3, 2, 8, 1, 5, 9, 6, 10, 7, 4]

        c. 기준점을 유지한 상태로, 과정을 반복하면 보다 큰 값 8과 작은 값 1을 
	   탐색할 수 있다. 마찬가지로 swap 한다.

       		[3, 2, 1, 8, 5, 9, 6, 10, 7, 4]

        d. 기준점을 유지한 상태로, 과정을 반복했으나, 큰 값의 인덱스를 찾는 과정과
	   작은 값의 인덱스를 찾는 과정이 서로 교차했다.
	   이럴 경우에는 기준점과 가장 작은 숫자를 swap해준다.
       
       		[1, 2// 3 // 8, 5, 9, 6, 10, 7, 4]
            
        e. 처음 기준점이었던 3을 기준으로 좌측에는 작은 수, 우측에는 큰 수가
	   정렬되어 있는 것을 확인할 수 있다. 분할이 이루어진 것이다.
	   좌측부터 똑같은 방식으로 기준점을 1로 잡고 진행해보면,
       
       => 1을 기준으로 우측에는 큰 수가 확인되지만 작은 수는 확인되지 않는다.
	  이 때는 결국 자기 자신과 바뀌고 끝난다. 그리고 다음 기준점 2는
	  그대로 출력 된다.
       
       		[1 // 2 // 3 // 8, 5, 9, 6, 10, 7, 4]
            
        f. 오른쪽에서 기준점 8을 기준으로 큰 값 9와 작은 값 4를 서로 swap한다.
        
       	 	[1 // 2 // 3 // 8, 5, 4, 6, 10, 7, 9]
            
        g. 마찬가지로 기준점 8을 기준으로 큰값 10과 작은 값 7을 swap 한다.
        
	        [1 // 2 // 3 // 8, 5, 4, 6, 7, 10, 9]
            
        h. 그리고 똑같은 과정을 수행했으나, 작은 값과 큰 값의 인덱스가 서로 교차하므로 
	   기준점과 작은값 7을 교체한다.

	        [1 // 2 // 3 // 7, 5, 4, 6 // 8 // 10, 9]
            
       i. 이러한 방식으로 진행을 하다보면 결국에는 아래의 결과가 나올 것이다.
       
       	        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

파이썬 코드로 구현하기

• 위에 설명한 방식의 정석적인 방법은 아니지만, 퀵 정렬의 핵심 개념은 가지고 가는 코드

• 코드의 핵심은 재귀와 분할/정복

def quick_sort(array):
    if(len(array)) < 2:
        return array

    else:
        pivot = array[0]
        lesser = [ element for element in array[1:] if element <= pivot ]
        greater = [ element for element in array[1:] if element > pivot ]
        return quick_sort(lesser) + [pivot] + quick_sort(greater)

정렬 알고리즘의 시간 복잡도 비교

• 단순(구현 간단)하지만 비효율적인 방법 : 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법 :퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

[출처] : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html