quick sort

[cookk]

• swap을 이용한 정렬

  • average time complexity = O(NlogN)
  • worst case time complexity = O(N^2)

• 정렬 과정

  • pivot을 정한다
  • pivot을 기준으로 작은 수는 왼쪽, 큰 수는 오른쪽

[cookk]

• methods

  
  def quick_sort(arr):
  start_loc = 0
  end_loc = len(arr) -1
  return partition_sort(arr, start_loc, end_loc)

def partition_sort(arr, start_loc, end_loc): if start_loc >= end_loc: return

pivot_loc = pick_pivot(start_loc, end_loc)

arr[pivot_loc], arr[end_loc] = arr[end_loc], arr[pivot_loc]
pivot_loc = end_loc

greater_loc, lesser_loc = get_greater_lesser_loc(arr, start_loc, end_loc, pivot_loc)
if has_greater_num(greater_loc):
    while greater_loc < lesser_loc:
        arr[greater_loc], arr[lesser_loc] = arr[lesser_loc], arr[greater_loc]
        greater_loc, lesser_loc = get_greater_lesser_loc(arr, start_loc, end_loc, pivot_loc)

    arr[greater_loc], arr[pivot_loc] = arr[pivot_loc], arr[greater_loc]
    pivot_loc = greater_loc

partition_sort(arr, start_loc, pivot_loc - 1)
partition_sort(arr, pivot_loc + 1, end_loc)
return arr

def get_greater_lesser_loc(arr, start_loc, end_loc, pivot_loc): greater_loc = get_greater_loc(arr, start_loc, end_loc, pivot_loc) lesser_loc = get_lesser_loc(arr, start_loc, end_loc, pivot_loc) return greater_loc, lesser_loc

def has_greater_num(greater_loc): if greater_loc == -1: return False return True

def get_greater_loc(arr, start_loc, end_loc, pivot_loc): for i in range(start_loc, end_loc): if arr[i] > arr[pivot_loc]: return i return -1

def get_lesser_loc(arr, start_loc, end_loc, pivot_loc): for i in range(end_loc, start_loc - 1, -1): if arr[i] < arr[pivot_loc]: return i return -1

def pick_pivot(start_loc, end_loc): return start_loc

return end_loc

return any_loc

- test
```python
import random

test_arr = list(range(0, 30))
random.shuffle(test_arr)
print("before : {}".format(test_arr))
test_arr = quick_sort(test_arr)
print("after : {}".format(test_arr))

• output

  before : [0, 5, 23, 25, 19, 29, 21, 22, 16, 2, 28, 26, 12, 20, 13, 9, 24, 15, 10, 8, 27, 11, 4, 1, 3, 7, 17, 6, 18, 14]
  after : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]