Intro

데이터를 특정한 기준에 따라서 정렬하는 것을 정렬 알고리즘 이라고 한다. 정렬 알고리즘으로 데이터를 정렬한 후에는 데이터가 순서대로 정렬되어있기 때문에 이진 탐색 이 가능해진다. 정렬은 대부분의 언어에서 라이브러리 함수로 제공하고 있는데 파이썬은 sort와 sorted가 그 예시이다. 그런데도 굳이 정렬 알고리즘 원리를 따로 공부하는 것은 정렬 알고리즘에 다양한 종류가 있고, 각각의 쓰임새가 다르기 때문이다.

🔍 정렬 알고리즘 종류

1. 선택 정렬

컴퓨터가 데이터를 정렬할 때 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두번째 데이터와 바꾸는 과정을 반복하는 것을 선택 정렬 알고리즘이라고 한다.

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

for i in range(len(array)):
	min_index = i # 가장 작은 원소의 인덱스
	for j in range(i+1, len(array)):
		if array[min_index] > array[j]: # array[j]보다 array[min_index]가 클 때 원소를 바꿔줌!
				min_index = j
	# 스와프
	array[i], array[min_index] = array[min_index], array[i]

print(array)

선택 정렬 알고리즘에서의 포인트는min_index 값을 계속 변경시켜주는 것이다. 코드를 보면 알 수 있듯이 선택 정렬 알고리즘의 시간복잡도는 O(N^2)이다.

2. 삽입 정렬

특정한 데이터를 적절한 위치에 삽입하는 알고리즘을 삽입 정렬 알고리즘이라고 한다. 삽입하기 이전의 데이터들은 모두 정렬되어있으며 무조건 두번째 위치부터 정렬이 시작하게 된다.

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

for i in range(1, len(array)):
	for j in range(i, 0, -1):
		if array[j] < array[j-1]:
			array[j], array[j-1] = array[j-1], array[j]
		else:
			break

print(array)

삽입 정렬 알고리즘의 시간복잡도 또한 O(N^2)이다.

3. 퀵 정렬

정렬 라이브러리의 근간이 되는 알고리즘으로, 기준 데이터인 pivot(피벗)을 설정하고 큰 수와 작은 수를 교환한 뒤 리스트를 반으로 나누는 방식으로 동작한다. 이 말만 보면 굉장히 이해가 안갈 수 있는데,, 그림을 보고 단계적으로 설명을 적어보겠다.

1) 피벗이 될 데이터(보통 맨 처음 것)을 선택한다.
2) 왼쪽부터 피벗보다 큰 수를 고르고, 오른쪽부터 피벗보다 작은 수를 고른 후 위치를 교환한다.
3) 이때 작은 수와 큰 수의 위치가 바뀌면 작은수와 피벗의 위치를 교환한다.

이것이 퀵 정렬의 동작방식이며, 퀵 정렬 알고리즘의 시간복잡도는 O(NlogN)이다.

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

def quick_sort(array):
	if len(array) <= 1: # 리스트가 1개 이하의 원소를 가지고 있으면 종료
		return array

	pivot = array[0]
	tail = array[1:] # 피벗을 제외한 리스트

	left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
	right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

	return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

4. 계수 정렬

계수 정렬은 비교 기반의 정렬 알고리즘이 아니다. 데이터가 정수 형태로 주어져 있는 경우에만 계수 정렬 알고리즘 사용이 가능하다. 별도의 리스트를 선언한 후 정렬에 대한 정보를 그 안에 모두 담는다는 특징이 있다.

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

# 모든 범위를 포함하는 리스트 선언
count = [0] * (max(array)+1)

for i in range(len(array)):
	count[array[i]] += 1 # 각 리스트에 해당하는 인덱스 값 증가

# 등장한 횟수만큼 인덱스를 출력하는 함수
for i in range(len(count)):
	for j in range(count[i]):
		print(i, end=' ')

주어진 배열에서 특정 수가 몇 번 나왔는지 세어보고, count 배열에 담아서 해당 수만큼 출력하면 된다.
이는 O(N+K)의 시간복잡도를 갖는다.