# [Sort] Quick Sort

# ⚙️ 정렬 방식

재귀(recursive) 용법을 활용한 정렬 알고리즘.
1. 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모음.
2. 왼쪽, 오른쪽도 재귀용법을 사용하여 반복함.
  
  출처: https://en.wikipedia.org/wiki/Quicksort (opens new window)

# 📝 구현

# 랜덤 배열 생성

arr = rd.sample(range(1,101), 100)
arr += arr + arr + arr
print(arr))

1
2
3

# 랜던 배열 확인

[5, 50, 14, 52, 27, 85, 94, 66, 19, 23, 60, 36, 44, 83, 42, 100, 11, 89, 55, 28, 26, 57, 95, 30, 96, 81, 61, 12, 46, 16, 43, 70, 80, 39, 18, 65, 99, 33, 20, 45, 34, 98, 77, 8, 91, 38, 84, 35, 62, 10, 54, 64, 1, 87, 6, 88, 24, 17, 79, 9, 13, 51, 22, 59, 82, 75, 32, 29, 21, 78, 53, 25, 67, 73, 74, 68, 86, 2, 90, 72, 93, 63, 48, 97, 41, 58, 4, 71, 49, 92, 76, 56, 47, 15, 40, 3, 69, 7, 37, 31, 5, 50, 14, 52, 27, 85, 94, 66, 19, 23, 60, 36, 44, 83, 42, 100, 11, 89, 55, 28, 26, 57, 95, 30, 96, 81, 61, 12, 46, 16, 43, 70, 80, 39, 18, 65, 99, 33, 20, 45, 34, 98, 77, 8, 91, 38, 84, 35, 62, 10, 54, 64, 1, 87, 6, 88, 24, 17, 79, 9, 13, 51, 22, 59, 82, 75, 32, 29, 21, 78, 53, 25, 67, 73, 74, 68, 86, 2, 90, 72, 93, 63, 48, 97, 41, 58, 4, 71, 49, 92, 76, 56, 47, 15, 40, 3, 69, 7, 37, 31, 5, 50, 14, 52, 27, 85, 94, 66, 19, 23, 60, 36, 44, 83, 42, 100, 11, 89, 55, 28, 26, 57, 95, 30, 96, 81, 61, 12, 46, 16, 43, 70, 80, 39, 18, 65, 99, 33, 20, 45, 34, 98, 77, 8, 91, 38, 84, 35, 62, 10, 54, 64, 1, 87, 6, 88, 24, 17, 79, 9, 13, 51, 22, 59, 82, 75, 32, 29, 21, 78, 53, 25, 67, 73, 74, 68, 86, 2, 90, 72, 93, 63, 48, 97, 41, 58, 4, 71, 49, 92, 76, 56, 47, 15, 40, 3, 69, 7, 37, 31, 5, 50, 14, 52, 27, 85, 94, 66, 19, 23, 60, 36, 44, 83, 42, 100, 11, 89, 55, 28, 26, 57, 95, 30, 96, 81, 61, 12, 46, 16, 43, 70, 80, 39, 18, 65, 99, 33, 20, 45, 34, 98, 77, 8, 91, 38, 84, 35, 62, 10, 54, 64, 1, 87, 6, 88, 24, 17, 79, 9, 13, 51, 22, 59, 82, 75, 32, 29, 21, 78, 53, 25, 67, 73, 74, 68, 86, 2, 90, 72, 93, 63, 48, 97, 41, 58, 4, 71, 49, 92, 76, 56, 47, 15, 40, 3, 69, 7, 37, 31]

# 정렬 알고리즘 코드

def quick_sort(arr):
  if len(arr) <= 1: return arr
  pivot = arr[0]
  left = [item for item in arr if pivot > item]
  mid = [item for item in arr if pivot == item]
  right = [item for item in arr if pivot < item]
  return quick_sort(left) + mid + quick_sort2(right)

1
2
3
4
5
6
7

# 정렬 결과 확인

sorted_arr = quick_sort(arr)
print(sorted_arr)

1
2

[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31, 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39, 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43, 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51, 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55, 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59, 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63, 64, 64, 64, 64, 65, 65, 65, 65, 66, 66, 66, 66, 67, 67, 67, 67, 68, 68, 68, 68, 69, 69, 69, 69, 70, 70, 70, 70, 71, 71, 71, 71, 72, 72, 72, 72, 73, 73, 73, 73, 74, 74, 74, 74, 75, 75, 75, 75, 76, 76, 76, 76, 77, 77, 77, 77, 78, 78, 78, 78, 79, 79, 79, 79, 80, 80, 80, 80, 81, 81, 81, 81, 82, 82, 82, 82, 83, 83, 83, 83, 84, 84, 84, 84, 85, 85, 85, 85, 86, 86, 86, 86, 87, 87, 87, 87, 88, 88, 88, 88, 89, 89, 89, 89, 90, 90, 90, 90, 91, 91, 91, 91, 92, 92, 92, 92, 93, 93, 93, 93, 94, 94, 94, 94, 95, 95, 95, 95, 96, 96, 96, 96, 97, 97, 97, 97, 98, 98, 98, 98, 99, 99, 99, 99, 100, 100, 100, 100]

# 🧮 알고리즘 분석

MergeSort와 유사 시간 복잡도는 $O(nlogn)$
최악의 경우,(pivot이 항상 리스트의 최대값이거나 최소값일 경우)
- 모든 데이터가 left나 right 한 쪽으로 들어가는 상황만 발생한다고 하면,
- 시간 복잡도는 $O(n^2)$

← [Sort] Merge Sort 📕 2021-06-22 화 →