정렬 알고리즘

알고리즘이 문제를 푸는 방법이라고 했는데, 그러면 정렬 알고리즘은 뭘 정렬하기 위한 방법이겠지? 네, 맞습니다. 이것도 여러가지가 있는데 대표적인 것 다섯가지만 일단 알아보자.

코드와 알고리즘 관련 설명은

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

여기서 볼 수 있다.

---

버블 정렬

a = [80, 58, 66, 100, 71, 39, 89, 67, 25, 9]

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        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)

bubble_sort(a)

[58, 80, 66, 100, 71, 39, 89, 67, 25, 9]
[58, 66, 80, 100, 71, 39, 89, 67, 25, 9]
[58, 66, 80, 100, 71, 39, 89, 67, 25, 9]
[58, 66, 80, 71, 100, 39, 89, 67, 25, 9]
[58, 66, 80, 71, 39, 100, 89, 67, 25, 9]
[58, 66, 80, 71, 39, 89, 100, 67, 25, 9]
[58, 66, 80, 71, 39, 89, 67, 100, 25, 9]
[58, 66, 80, 71, 39, 89, 67, 25, 100, 9]
[58, 66, 80, 71, 39, 89, 67, 25, 9, 100]
[58, 66, 80, 71, 39, 89, 67, 25, 9, 100]
[58, 66, 80, 71, 39, 89, 67, 25, 9, 100]
[58, 66, 71, 80, 39, 89, 67, 25, 9, 100]
[58, 66, 71, 39, 80, 89, 67, 25, 9, 100]
[58, 66, 71, 39, 80, 89, 67, 25, 9, 100]
[58, 66, 71, 39, 80, 67, 89, 25, 9, 100]
[58, 66, 71, 39, 80, 67, 25, 89, 9, 100]
[58, 66, 71, 39, 80, 67, 25, 9, 89, 100]
[58, 66, 71, 39, 80, 67, 25, 9, 89, 100]
[58, 66, 71, 39, 80, 67, 25, 9, 89, 100]
[58, 66, 39, 71, 80, 67, 25, 9, 89, 100]
[58, 66, 39, 71, 80, 67, 25, 9, 89, 100]
[58, 66, 39, 71, 67, 80, 25, 9, 89, 100]
[58, 66, 39, 71, 67, 25, 80, 9, 89, 100]
[58, 66, 39, 71, 67, 25, 9, 80, 89, 100]
[58, 66, 39, 71, 67, 25, 9, 80, 89, 100]
[58, 39, 66, 71, 67, 25, 9, 80, 89, 100]
[58, 39, 66, 71, 67, 25, 9, 80, 89, 100]
[58, 39, 66, 67, 71, 25, 9, 80, 89, 100]
[58, 39, 66, 67, 25, 71, 9, 80, 89, 100]
[58, 39, 66, 67, 25, 9, 71, 80, 89, 100]
[39, 58, 66, 67, 25, 9, 71, 80, 89, 100]
[39, 58, 66, 67, 25, 9, 71, 80, 89, 100]
[39, 58, 66, 67, 25, 9, 71, 80, 89, 100]
[39, 58, 66, 25, 67, 9, 71, 80, 89, 100]
[39, 58, 66, 25, 9, 67, 71, 80, 89, 100]
[39, 58, 66, 25, 9, 67, 71, 80, 89, 100]
[39, 58, 66, 25, 9, 67, 71, 80, 89, 100]
[39, 58, 25, 66, 9, 67, 71, 80, 89, 100]
[39, 58, 25, 9, 66, 67, 71, 80, 89, 100]
[39, 58, 25, 9, 66, 67, 71, 80, 89, 100]
[39, 25, 58, 9, 66, 67, 71, 80, 89, 100]
[39, 25, 9, 58, 66, 67, 71, 80, 89, 100]
[25, 39, 9, 58, 66, 67, 71, 80, 89, 100]
[25, 9, 39, 58, 66, 67, 71, 80, 89, 100]
[9, 25, 39, 58, 66, 67, 71, 80, 89, 100]

인접한 두 수를 비교해가면서 정렬하는 방식. 비유하자면 얘가 얘보다 출석번호가 큰가를 일일이 확인하고 출석번호가 더 크면 뒤로 보낸다. 

보시다시피 코드는 심플하지만, 실행 결과를 보면 하나하나 대조해가면서 얘가 얘보다 크면 뒤로 빼는 방식이라 효율면에서는 씁 에반데 소리가 절로 나온다. 

선택 정렬

a = [80, 58, 66, 100, 71, 39, 89, 67, 25, 9]

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)

selection_sort(a)

[9, 58, 66, 100, 71, 39, 89, 67, 25, 80]
[9, 25, 66, 100, 71, 39, 89, 67, 58, 80]
[9, 25, 39, 100, 71, 66, 89, 67, 58, 80]
[9, 25, 39, 58, 71, 66, 89, 67, 100, 80]
[9, 25, 39, 58, 66, 71, 89, 67, 100, 80]
[9, 25, 39, 58, 66, 67, 89, 71, 100, 80]
[9, 25, 39, 58, 66, 67, 71, 89, 100, 80]
[9, 25, 39, 58, 66, 67, 71, 80, 100, 89]
[9, 25, 39, 58, 66, 67, 71, 80, 89, 100]
[9, 25, 39, 58, 66, 67, 71, 80, 89, 100]

배열을 쓱 보면서 가장 작은 값을 앞으로 보낸다. 앞에서부터 뒤로 쭉 둘러보면서 1번을 맨앞으로, 그 다음 2번을 맨 앞으로, 3번을 맨 앞으로… 이런 식으로 진행한다. 버블 정렬에 비해 과정이 짧아보이는데 기분탓…은 아님.

삽입 정렬

a = [80, 58, 66, 100, 71, 39, 89, 67, 25, 9]

def insert_sort(array):
    n = len(array)
    for i in range(n):
        min_index = i
        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)

insert_sort(a)

[80, 58, 66, 100, 71, 39, 89, 67, 25, 9]
[58, 80, 66, 100, 71, 39, 89, 67, 25, 9]
[58, 66, 80, 100, 71, 39, 89, 67, 25, 9]
[58, 66, 80, 100, 71, 39, 89, 67, 25, 9]
[58, 66, 71, 80, 100, 39, 89, 67, 25, 9]
[39, 58, 66, 71, 80, 100, 89, 67, 25, 9]
[39, 58, 66, 71, 80, 89, 100, 67, 25, 9]
[39, 58, 66, 67, 71, 80, 89, 100, 25, 9]
[25, 39, 58, 66, 67, 71, 80, 89, 100, 9]
[9, 25, 39, 58, 66, 67, 71, 80, 89, 100]

데이터의 사이를 비우고 그 사이로 순서에 맞는 데이터를 넣는 정렬 구조. 출석번호 2번과 4번의 사이를 벌리고 그 사이로 3번을 넣는다. 보통 사람들이 책이나 서류철같은 거 정리할 때 이런 식으로 한다.

병합 정렬

a = [80, 58, 66, 100, 71, 39, 89, 67, 25, 9]

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
    # 그리고 비교한다

merge_sort(a)

[58, 80]
[71, 100]
[66, 71, 100]
[58, 66, 71, 80, 100]
[39, 89]
[9, 25]
[9, 25, 67]
[9, 25, 39, 67, 89]
[9, 25, 39, 58, 66, 67, 71, 80, 89, 100]

폰 노이만이 고안한 알고리즘. 이 양반에 대한 이야기는 아래를 참고하시고… (야공만 재밌음)

https://www.facebook.com/engineertoon/posts/579547758898750

이게 그래서 뭐냐면… 배열의 길이가 0이나 1이 될 때까지 쪼개고 비교해서 합한다. 그러니까

1. 이 배열을 [80, 58, 66, 100, 71] [39, 89, 67, 25, 9]로 나누고
2. 또 배열을 [80, 58] [66, 100, 71] [39, 89] [67, 25, 9]로 나누고 
3. 계속 나눠서 배열의 길이가 1이 될 때까지 나눈다. (홀수 배열은 아마도 [1] [2, 3] 이런 식인 듯)
4. 나눈 배열에 있는 숫자를 비교해서 작은 쪽을 앞으로 빼고 다시 합친다. (if문이 그래서 있음)

대충 이런 식.

퀵 정렬

a = [80, 58, 66, 100, 71, 39, 89, 67, 25, 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)

quick_sort(a)

[25, 9] [39] [80, 58, 66, 100, 71, 89, 67]
[] [9] [25]
[80, 58, 66, 71, 89, 67] [100] []
[58, 66, 67] [71] [80, 89]
[58] [66] [67]
[80] [89] []
[9, 25, 39, 58, 66, 67, 71, 80, 89, 100]

로직 잘못 짜면 성능을 조지긴 한데 아무튼… 한 반에 25명이 있고 출석번호 순으로 줄을 세울 때 퀵 알고리즘은 기준점을 두고 그걸 중심으로 분할한다. 이 코드에서는 배열의 가운데(여기서는 길이가 10인 배열의 5번 값)를 기준으로 해서 정렬했다. 이것도 일종의 분할 알고리즘이라 피벗을 중심으로 앞을 정렬하고 뒤도 기준점을 잡아서 정렬한 것을 볼 수 있다.

알고리즘의 소요시간 비교해보기

버블 알고리즘이 개똥이라는데 진짜일까? 확인해보자. 일단 확인하기 위한 배열이 하나 필요한데, 시간복잡도가 체감되는 건 ‘데이터가 많아질때’이다. 그래서 배열의 길이를 10개 뭐 이렇게 스몰스케일로 안 하고

[793, 27, 646, 705, 964, 814, 804, 300, 942, 614, 765, 790, 739, 191, 474, 503, 887, 908, 476, 733, 964, 564, 579, 22, 395, 645, 713, 763, 830, 909, 206, 197, 540, 489, 124, 696, 957, 882, 759, 557, 198, 987, 424, 777, 111, 893, 813, 329, 570, 707, 226, 423, 246, 86, 878, 192, 421, 559, 871, 62, 136, 768, 831, 813, 477, 714, 805, 279, 186, 281, 404, 252, 548, 546, 594, 1, 627, 351, 721, 11, 637, 386, 657, 907, 35, 753, 827, 227, 116, 745, 586, 105, 4, 444, 488, 599, 404, 3, 291, 634, 848, 500, 260, 273, 575, 549, 713, 166, 109, 930, 761, 997, 21, 333, 160, 569, 927, 210, 315, 592, 330, 305, 839, 931, 822, 957, 738, 552, 478, 886, 809, 855, 579, 965, 661, 572, 219, 878, 830, 542, 82, 401, 30, 276, 664, 596, 616, 500, 74, 382, 191, 947, 521, 715, 575, 65, 110, 722, 751, 710, 953, 229, 586, 852, 447, 604, 529, 82, 760, 755, 167, 609, 152, 229, 276, 834, 84, 411, 817, 988, 572, 318, 192, 292, 438, 708, 450, 404, 204, 348, 387, 401, 88, 431, 246, 131, 55, 816, 211, 726]

길이 200짜리 배열을 준비했다. (물론 난수로 만들었음) 그리고 하나 더 있는데… 코드가 구동되는 시간을 뭐 스톱워치로 잴 수는 없잖음?

import random, sys, time
start = time.time()
N = int(sys.stdin.readline())

def random_array(n):
    a = []
    for i in range(n):
        i = random.randrange(1,101)
        a.append(i)
        for j in a:
            if i == j:
                i = random.randrange(1,101)
            else: 
                continue
    return a

print(random_array(N))
print('소요시간: ',round(time.time() - start,3))

import time 하고 시작시간 지정하고 완료 후의 시간에서 빼서 소요시간을 계산할 수 있다. 그리고 결과는…

1. 버블 정렬 소요시간: 7.392
2. 선택 정렬 소요시간: 0.075
3. 삽입 정렬 소요시간: 0.08
4. 병합 정렬 소요시간: 0.003
5. 퀵 정렬 소요시간: 0.000118 (3자리 했더니 안나와서 자리수 늘렸음)

버블 정렬이 진짜 느리다. 그래서 진짜 막 이거 아님 안될것같다… 그런거 아니면 버블 정렬은 지양하는 게 좋다고. 버블 정렬이 압도적이라 그렇지 2, 3번이 전체적으로 그렇게 효율이 좋지 않은데… 왜 그럴까? 병합이랑 퀵은 왜 그렇게 빠를까? 병합 정렬과 퀵 정렬은 배열을 ‘분할’해서 정렬한다. 출석 번호 정렬로 치자면 위에 3개는 한 반 전체를 정렬하는거고, 아래 두 개는 어떤 기준으로 한 반의 학생들을 그룹으로 나눠서 정렬한다.

아니 이렇게까지 해야 함?

근데 이걸 왜 정렬까지 해야 하나요? 그것은 간단하다. 데이터를 어떤 기준으로든 정렬해두면, 이진 탐색 알고리즘을 이용할 수 있다. 예? 그게 뭔 소리유? 예를 들어보자.

평소처럼 실험을 하던 제육쌈밥군(R로 스탠다드 커브 그리기 참고). 그러던 어느 날, 교수님께 퀘스트가 들어왔다.

“여기 있는 실험노트 중, 2015년 이전에 작성된 노트를 내 방으로 옮겨줘. “

제육쌈밥군이 있는 실험실은 교수님의 인기가 좋아 대학원을 거쳐 간 사람들이 꽤 있었고, 노트는 어림잡아 3~400권 정도는 되는 것 같았다.

1. 정렬이 없을 때: 일단 제육쌈밥군은 최근에 실험실에 들어온 선배들의 노트를 제외하고, 책꽂이에 꽂혀 있는 실험노트를 전부 꺼냈다. 그리고 실험노트 앞쪽에 적힌 날짜를 보면서 일일이 연도를 확인하면서 2015년 이전에 작성된 노트를 골라냈고, 교수님 사무실로 옮겼다.
2. 정렬이 있을 때(전체 정렬): 제육쌈밥군은 노트 뭉치를 가져와서 한데 모은 다음, 표지에 쓰인 연도순으로 정렬했다. 한참동안 노트를 정리한 제육쌈밥은 2015년 이전에 작성된 노트를 교수님 사무실로 옮겼다.
3. 정렬이 있을 때(분할 정렬): 제육쌈밥군은 노트 뭉치를 가져와서 책꽂이 칸별로 쌓았다. 그리고 노트 더미에서 노트를 꺼내 앞표지를 확인하면서 노트를 정리한 제육쌈밥은 정리를 마치고 2015년 이전에 작성된 노트를 교수님 사무실로 옮겼다.

세 가지 케이스를 얼핏 들어서는 별로 차이가 없을 것 같지만, 노트를 일단 정렬하게 되면 2014년 12월에 작성된 마지막 노트에 표시하고 그것만 잘라서 정리하면 된다. 정리하는데 시간은 들겠지만, 정리하고 나서 그냥 기준에 따라 뚝 자르면 되는 것.