파이썬 정렬 알고리즘 퀵 정렬

이전 정렬 알고리즘 정리 글

파이썬 정렬 알고리즘 선택정렬

 

파이썬 정렬 알고리즘 삽입정렬

 

파이썬 정렬 알고리즘 버블 정렬

 

 

퀵 정렬

기본 개념 : 기준을 가지고 그 기준을 중심으로 UP, Down으로 구분 → 다시 또 기준을 가지고 다시 Up , Down으로 구분

참고) 기준을 보통 pivot으로 이야기를 하고, 보통은 크게 맨앞, 중간, 맨뒤를 함 → 응용이 다양하게 됨

→ pivot에 대한 선정에 대해서도 여러가지 방법이 있음.

아래의 그림은 맨 앞의 값을 가지고 하는 것

 

step 1

 

1. 현재 pivot = 5로 기준을 잡고
왼쪽에서부터 pivot = 5보다 큰 데이터를 선택하므로 7이 선택,
오른쪽에서부터는 pivot=5보다 작은 데이터를 선택하므로 4가 선택이 됨
→ 이 둘에 대해서 Swap으로 바꿈

 

step 2

 

2. 기준 pivot = 5로 아직 유지
왼쪽에서부터 다시 pivot =5 보다 큰 데이터를 찾을 때 까지 가다 9가 선택,
오른쪽에서부터 다시 pivot =5 보다  작은 데이터를 선택하므로 2가 선택
→ 이 둘에 대해서 swap으로 바꿈

 

step 3

 

3. 기준 pivot =5로 아직 유지
왼쪽에서부터 다시 pivot =5 보다 큰 데이터를 찾을 때 까지 가면 6이 선택,
오른쪽에서부터 다시 pivot = 5 보다 작은 데이터를 찾을 때 까지 가면 1이 선택
→ 이런 경우에서는 서로 위치가 엇갈림
→ 기존 pivot=5와 작은 값의 위치 변경

 

step 4

 

4. 위의 과정으로 기준 pivot =5 보다 up, down 이 서로 분할이 됨 이것을 Divide 라고 함

 

나누는 이유
한 번에 힘드니까 기준 pivot =5 보다 큰것들에서 다시 정렬, 작은 것에서 다시 정렬

 

step 5

5. 다시 왼쪽으로 pivot = 1로 왼쪽 덩어리에 대해서 기준을 잡고,
위에서 한 그대로 다시  함

 

step 6

6. 다시 Up 덩어리에서 다시 제일 왼쪽의 기준 pivot = 6 으로 기준을 잡고 위에서 한 그대로 다시 함

 

이렇게 분할을 하면서 원소의 갯수가 1개인 경우가 되면 종료

 

아래의 그림과 같이 pivot 이라는 기준으로 계속 나눠지면서 내려감.

 

퀵 정렬 코드

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

def quick_sort(array):
	if len(array) <= 1:	# 길이가 1보다 작으면 바꿀게 없으므로 그대로 값을 리턴
		return array
	pivot = len(array) // 2	# piviot을 리스트에서 가운데 숫자로 선택
	front_arr, pivot_arr, back_arr = [], [], []
	for value in array:
		if value < array[pivot]:
			front_arr.append(value)
		elif value > array[pivot]:
			back_arr.append(value)
		else:
			pivot_arr.append(value)
	print(front_arr, pivot_arr, back_arr)	# 숫자가 정렬 되는 것을 볼 수 있음
    				# 재귀함수를 통해 나눠진 숫자들을 계속 정렬
	return quick_sort(front_arr) + quick_sort(pivot_arr) + quick_sort(back_arr)

print("before: ",array)
array = quick_sort(array)
print("after:", array)

before: [8, 4, 6, 2, 5, 1, 3, 7, 9]
[4, 2, 1, 3] [5] [8, 6, 7, 9]
[] [1] [4, 2, 3]
[] [2] [4, 3]
[] [3] [4]
[6] [7] [8, 9]
[8] [9] []
after: [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

시간복잡도

아래 그림과 같이 대략적으로 가운데를 기준으로 up, down이 구분이 된다고 하면 아래와 같은 식으로 내려가게 

가로 * 세로 = N * logN = NlogN

 

• O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가)
  • 버블 정렬(Bubble Sort)
  • 선택 정렬(Selection Sort)
  • 삽입 정렬(Insertion Sort)
• O(n log n)의 시간 복잡도
  
  • 퀵 정렬(Quick Sort)