개발자 성장 기록 63 - 정렬 알고리즘 (with Python)

정렬 알고리즘이란?

목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 것을 말한다.

주어진 문제를 해결하기 위해 최선의 알고리즘을 선택해야 하는데 그때 고려해야 할 것이 시간복잡도, 공간복잡도이다.

시간복잡도는 결과를 도출하는 데 걸리는 시간을 말하며, 공간복잡도는 결과를 도출하는데 필요한 공간의 값이다.

즉, 문제를 해결하기 위해 선택해야 할 알고리즘은 적은 시간과 적은 공간을 사용하는 알고리즘이다.

빅오(Big O) 표기법과 시간복잡도

알고리즘에 대해 공부하다 보면 시간복잡도가 O(n), 혹은 O(n^2)이라는 표시를 본 적이 있을 것이다.

위와 같이 표시하는 것을 빅오 표기법이라고 한다.

O(n)
이 함수는 n만큼의 데이터가 주어졌을 때, "최악"의 경우 n만큼의 리소스를 소모한다

자주 나오는 것들은 O(1), O(n), O(n^2), O(logN) 정도가 있는데, 보기 쉽게 2차원 그래프로 나타내면 다음과 같다.

그림1. 빅오

---

파이썬의 정렬 알고리즘

대표적으로 버블, 선택, 삽입, 병합, 퀵 정렬이 있다.

각각의 알고리즘의 시간복잡도는 버블, 선택, 삽입 정렬은 O(n^2)이며, 병합, 퀵 정렬은 O(n log n)이다.

버블 정렬 (Bubble Sort)

그림2. 버블 정렬

인접한 두 수를 비교하며 정렬해 나가는 방법으로 O(n^2)의 느린 성능을 가지고 있다.

앞에서부터 시작하여 큰 수를 뒤로 보내 뒤에 있는 수가 큰 값을 가지도록 완성해 나가는 방법(혹은 반대로 뒤에서부터 반복하여 앞에 있는 수가 적은 값을 가지도록 완성해 나가는 방법)이 있다.

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

def bubble_sort(array):
    n = len(array)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
        print(array)

print("before: ",array)
bubble_sort(array)
print("after:", array)

결과

---

선택 정렬 (Selection Sort)

그림3. 선택 정렬

한 바퀴 돌 때 가장 작은 값을 찾아 맨 앞과 교환하는 방식이고 O(n^2)의 성능을 가진다.

앞에서부터 정렬해 나가는 특성을 가지고 있다.

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

def selection_sort(array):
	n = len(array)
	for i in range(n):
		min_index = i
		for j in range(i + 1, n):
			if array[j] < array[min_index]:
				min_index = j
		array[i], array[min_index] =  array[min_index], array[i]
		print(array[:i+1])

print("before: ",array)
selection_sort(array)
print("after:", array)

결과

---

삽입 정렬 (Insertion Sort)

그림4. 삽입 정렬

정렬된 데이터 그룹을 늘려가며 추가되는 데이터는 알맞은 자리에 삽입하는 방식으로 O(n^2)의 성능을 가진다.

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

def insertion_sort(array):
	n = len(array)
	for i in range(1, n):
		for j in range(i, 0, - 1):
			if array[j - 1] > array[j]:
				array[j - 1], array[j] = array[j], array[j - 1]
		print(array[:i+1])

print("before: ",array)
insertion_sort(array)
print("after:", array)

결과

---

병합 정렬 (Merge Sort)

그림5. 병합 정렬

분할 정복과 재귀를 이용한 알고리즘으로 O(n log n)의 시간 복잡도를 가지고 있어 준수한 성능을 보여준다.

반으로 쪼개고 다시 합치는 과정에서 그룹을 만들어 정렬하게 되며 이 과정에서 2n개의 공간이 필요하다.

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

def merge_sort(array):
	if len(array) < 2:
		return array
	mid = len(array) // 2
	low_arr = merge_sort(array[:mid])
	high_arr = merge_sort(array[mid:])

	merged_arr = []
	l = h = 0
	while l < len(low_arr) and h < len(high_arr):
		if low_arr[l] < high_arr[h]:
			merged_arr.append(low_arr[l])
			l += 1
		else:
			merged_arr.append(high_arr[h])
			h += 1
	merged_arr += low_arr[l:]
	merged_arr += high_arr[h:]
	print(merged_arr)
	return merged_arr

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

결과

---

퀵 정렬 (Quick Sort)

그림6. 퀵 정렬

병합 정렬과 마찬가지로 분할 정복 알고리즘으로 평균적으로 빠른 속도를 수행하며, 추가적인 메모리 공간이 필요 없다는 장점을 가진다.

병합 정렬은 균등하게 분할하였다면 퀵 정렬은 Pivot을 설정하고 그 기준으로 정렬을 한다.

다른 정렬 알고리즘보다 빠르며 많은 언어의 정렬 내장 함수로 퀵 정렬을 수행한다.

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

def quick_sort(array):
	if len(array) <= 1:
		return array
	pivot = len(array) // 2
	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)

결과

---

참고

https://velog.io/@jguuun/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://evan-moon.github.io/2018/10/13/sort-algorithm/