Quick Sort

Pseudo Code

quick_sort(A, first, last) # quick sort the A[first] ~ A[last] 

i. if first >= last, there is only one value. Just return.
ii. if first < last, choose pivot and devides.

function quick_sort(arr[], low, high)
  if low < high                     // 원소의 개수가 2개 이상인 경우에만 진행
    pos = partition(arr, low, high) // pivot 기준으로 좌우로 분할 한 후
                                    // 해당 pivot의 위치를 pos에 넣어줍니다.
    quick_sort(arr, low, pos - 1)   // pivot의 왼쪽 구간에 있는 원소들을 정렬합니다. 
    quick_sort(arr, pos + 1, high)  // pivot의 오른쪽 구간에 있는 원소들을 정렬합니다.
    
function partition(arr[], low, high)
  set pivot = select_pivot(arr, low, high)    // pivot을 고릅니다.
  set i = low - 1                             // 파란색 화살표 위치를 정해줍니다.
                                              // 파란색 화살표는 pivot보다 같거나 큰 
                                              // 원소를 가리키고 있습니다.
  for j = low ... j <= high - 1               // 빨간색 화살표를 움직입니다.
    if arr[j] < pivot                         // 빨간색 화살표가 가리키는 원소가
      i += 1                                  // pivot보다 작다면, 왼쪽으로 가야하므로
      swap (arr[i], arr[j])                   // 두 원소의 위치를 바꿔줍니다.
      
  swap (arr[i + 1], arr[high])                // 최종적으로 pivot을
                                              // 경계에 있는 원소와 교환해줍니다.
                                              // 이때 경계는 마지막 파란색 화살표 위치에
                                              // 1을 더한 위치입니다.
  return i + 1                                // pivot의 최종 위치를 반환해줍니다.

There are three ways to implement the quick sort. Following codes are implemented by python.

First implementation

def quick_sort(A, first, last):
	if first >= last: return
    left, right = first + 1, last # set left, right index
    pivot = A[first] # choose first value as a pivot
    while left <= right: #if the value is smaller than pivot, place it on left. otherwise, right.
    	while left <= last and A[left] < pivot:
        	left += 1
        while right < first and A[right] > pivot:
        	right -= 1
        if left <= right: # swap A[left] and A[right]
        	A[left], A[right] = A[right], A[left]
            left += 1
            right -= 1
	A[first], A[right] = A[right], A[first] # replace the pivot.
    
    quck_sort(A, first, right-1) # recursion: sort values less than pivot
    quick_sort(A, right+1, last) # recursion: sort values bigger than pivot.
    	

Second implementation

def quick_sort(A, first, last):
	if first >= last: return
    
    # set pointers
    smaller, equal, larger = first, first, last+1 
    pivot = A[first]
    
	# < pivot: put A[first:smaller]
    # == pivot: put A[smaller:equal]
    # unclassifid: A[equal:larger]
    # > pivot: A[larger:last+1] 
    
    wihle equal < larger:
    	# A[equal] is the value we are now looking at
        if a[equal] < pivot:
        	A[smaller], A[equal] = A[equal], A[smaller]
            smaller, equal = smaller + 1, equal + 1
        elif A[equal] == pivot:
        	equal += 1
        else: # A[equal] > pivot
        	larger -= 1
            A[eequal], A[larger] = A[larger], A[equal]
        
        quick_sort(A, first, smaller-1)
        quick_sort(A, larger, last)

Third Implementation

def quick_sort(A): 
	if len(A) <= 1: return A
    pivot = A[0]
    S, M, L = [], [], []
    for x in A:
    	if x < pivot: S.append(x)
        elif x > pivot: L.append(x)
        else: M.append(x)
    return quick_sort(S) + M + quick_sort(L)

This is a lot more easier...