퀵 정렬(Quick sort) - 파이썬 코드 구현

Quick sort python code implementation
퀵소트(Quicksort)를 파이썬 코드로 구현해 보자.

---

퀵 소트(Quick sort)

퀵 소트는 배열을 파티션을 이용해서 반으로 나누고, 다시 이전 배열을 반으로 나눈 방식을 재귀적으로 적용한다.

파티션은 일반적으로, 제일 끝 배열의 원소를 pivot으로 잡고, 해당 pivot값보다 작은 값은 왼쪽으로 몰아 넣고, 큰 값은 오른쪽으로 몰아넣는다.

이 과정을 재귀적으로 반복하면, 각 파티션마다 O(n) 타임이 걸리고, 총 파티션은 평균적으로 O(logn) 타임이 걸리므로, 총 시간은 O(nlogn)이 걸리는 것을 알 수 있다.

위키피디아의 설명을 참고해 보자.

파티션은 다음과 같이 작동한다.

수도 코드를 살펴보자.

  function partition(a, left, right, pivotIndex)
      pivotValue := a[pivotIndex]
      swap(a[pivotIndex], a[right]) // 피벗을 끝으로 옮겨 놓는다.
      storeIndex := left
      for i from left to right-1
          if a[i] <= pivotValue then
              swap(a[storeIndex], a[i])
              storeIndex := storeIndex + 1
      swap(a[right], a[storeIndex]) // 피벗을 두 리스트 사이에 위치시킨다.
      return storeIndex

파티션함수가 잘 작동한다면, 퀵 소트는 다음과 같이 쉽게 만들 수 있다.

def quick_sort(Arr, p, r):
    if p < r:
        q = partition(Arr, p, r)
        quick_sort(Arr, p, q-1)
        quick_sort(Arr, q+1, r)

예시를 통해 파티션함수가 어떻게 작동하는지 알아보자.

이제 파이썬 코드를 짜보도록 하자.

# Insertion sort implementation
import sys #for sys.maxsize
from random import randrange
import math
import time

array1 = []
array2 = []
array3 = []

for i in range(100):
    array1.append(randrange(100))
for i in range(1000):
    array2.append(randrange(sys.maxsize))
for i in range(10000):
    array3.append(randrange(sys.maxsize))

#
# Helper functions
#
# swap, print_array
#

def swap(array, a, b):
    array[a], array[b] = array[b], array[a]

def print_array(input):
    for i in range(len(input)):
        print(input[i], end=' ')
    print()    

#
# Main sorting function : 
#

# put len(Arr) - 1 into r
def partition(Arr, p, r):
    x = Arr[r]
    i = p - 1
    for j in range(p, r):
        if Arr[j] <= x:
            i = i + 1
            swap(Arr, i, j)
    swap(Arr, i+1, r)
    return i+1

def quick_sort(Arr, p, r):
    if p < r:
        q = partition(Arr, p, r)
        quick_sort(Arr, p, q-1)
        quick_sort(Arr, q+1, r)

# Measure time elapsed

f = open("insert_dataset.txt", 'w')

for i in range(100):
    array_t = []
    for j in range(100):
        array_t.append(randrange(sys.maxsize))
    start = time.process_time()
    quick_sort(array_t, 0, len(array_t)-1)
    end = time.process_time()
    f.write(str((end - start) * 1000000) + "\n")

# print("Elasped time : " + str(end-start))

f.close()