Alignment algorithm

정렬 알고리즘(Alignment Algorithm)은 리스트에 원소를 가장 작은 순서부터 큰 순서로 오름차림 정렬을 하는 알고리즘이다. 다양한 정렬 알고리즘을 확인해봅시다.

선택 정렬 (Selection sort)

선택 정렬은 두가지의 루프문을 이용해 선형탐색을 진행하여 가장 작은 원소 값을 변수에 저장하고 그 다음 인덱스 값과 비교해가며 더 작은 값을 찾아가는 정렬입니다.

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

for i in range(len(arr)):
	min_index = i
    for j in range(i + 1, len(arry)):
    	if array[min_index) > array[j]:
        	min_index = j
    array[i], array[min_index] = min_index, array[i]
print(array)    

실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

선택 정렬의 시간 복잡도

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다. 구현 방식에 따라서 사소한 오차는 있을 수 있지만 , 전체 연산 횟수는 다음과 같습니다.

N + (N - 1) + (N - 2) + . . . . + 2 = (N^2 + N - 1) / 2 = O(N^2)

삽입 정렬 (Insertion sort)

삽입 정렬은 처리하지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬 방식을 사용합니다. 선택 정렬에 비해 구현 난이도가 높지만, 일반적으로 더 효율적(빠르게)으로 동작합니다.

삽입 정렬의 동작 원리를 자세히 알아보자면 인덱스 i번에 위치한 원소가 이미 정렬되었다고 가정하고 i+1번째 원소가 i번째 원소보다 작을 때는 i번째 원소 앞에, 그렇지 않다면 뒤에 삽입하는 원리입니다.

arr = [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)

실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 선택 정렬과 똑같이 O(N^2)이지만 삽입 정렬은 현재 리스트의 원소들이 거의 정렬되어 있는 상태라면 바로바로 break문으로 이동해 빠르게 루프를 끝내기 때문에 매우 바르게 동작합니다. 이럴 경우 최선으로 O(N)의 복잡도를 가집니다.

O(N^2) 또는 O(N)

퀵 정렬 (Quick sort)

퀵 정렬은 말 그대로 빠른 정렬입니다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다. 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다.

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다.

퀵 정렬 예시

퀵 정렬의 시간 복잡도

이상적일 경우 위 그림과 같이 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)를 기대할 수 있습니다. (너비 x 높이 = N x logN x NlogN)

하지만 최악에 경우, 즉 이미 정렬되어있거나 거의 정렬된 상태와 비슷한 상태일 경우 비대칭적인 비율로 분할되는 것이 계속 반복(선형탐색)되기 때문에 O(N^2)의 시간 복잡도를 가질 수 있습니다.

때문에 최악의 경우에도 O(NlogN)을 항상 보장해야되는 식으로 퀵 정렬을 구상해야됩니다.

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

def quick_sort(array, start, end):
	if start >= end:
    	return
    pivot = start
    left = start + 1
    right = end
    while(left <= right):
    	while(left <= end and array[left] <= array[pivot]:
        	left += 1
        while(right > start and array[right] >= array[pivot]):
        	right -= 1
        if(left > right):
        	array[right], array[pivot] = array[pivot], array[right]
        else:
        	array[left], array[right] = array[right], array[left]
    quick_sort(array, start, right - 1)
    quick_sort(array, right +1, end)
 

quick_sort(array, 0, len(array) - 1)
print(array)

실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

파이썬의 장점을 살린 퀵 정렬 소스코드 (List slicing, List comprehension)

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

def quick_sort(array):
	if len(array) <= 1:
    	rueturn 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))

실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

계수 정렬 (Counting sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘입니다. 계수 정렬은 데이터의 크기 범위가 제한되어있어 정수 형태로 표현할 수 있을 때 사용가능합니다. 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N + K)를 보장합니다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 0, 5, 2]
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 = ' ')