저번 시간에는 여러 가지 알고리즘의 사례로 선형 탐색과 이진 탐색에 대해 알아보았습니다. 이번 시간에는 또 다른 여러 가지 알고리즘의 사례로 정렬에 대해 알아 봅시다.
👮♀️ 정렬(sorting)
정렬이란, 리스트의 원소들을 특정 순서로 정리하는 것입니다. 오름차순과 내림차순이라는 말을 자주 들어보셨을 텐데요. 이 둘이 바로 특정 순서에 해당됩니다.
사실, 우리는 앞서 리스트를 배울 때, 내장함수인 sorted와 .sort() 메소드가 있다는 사실을 알았습니다. 두 개념을 활용하면 되는데 왜 굳이 정렬에 대해 따로 배워야 할까요?
앞서 알고리즘의 정의를 알려드리며 알고리즘을 코드로 구현할 때는 내장 함수의 사용을 최대한 배제한다고 했습니다. 그 이유는 알고리즘 구현을 통해 문제 해결의 기초를 다지기 위함이라고도 했습니다.
정렬은 알고리즘의 기초입니다. 또한, 모든 개발자가 알아야 하는 가장 기본적인 알고리즘이기도 하죠. 따라서, 정렬을 코드로 직접 구현하는 방법을 아는 것은 개발자가 되기 위한 필수 과정에 속한다고 할 수 있습니다.
정렬에는 여러 가지 알고리즘이 있지만 우선 두 가지 경우만 배워보도록 하죠.
👮♀️ 선택 정렬
첫번째로 선택 정렬(Selection Sort)을 알아봅시다. 선택 정렬은 가장 먼저 생각해 볼 수 있는 자연스러운 정렬 알고리즘입니다. 아주 직관적이죠.
가장 작은 값을 찾아 0번 인덱스에 놓고 그 다음 작은 값을 찾아 1번 인덱스, 그 다음 작은 값을 찾아 2번 인덱스... 이런 식으로 정렬하는 것을 말합니다.
이제 리스트의 예시를 봅시다.
some_list = [4, 7, 5, 2, 6, 9]위 리스트에 선택 정렬을 적용해보겠습니다. 0번 인덱스부터 차례로 보시죠. 0번 인덱스에는 최솟값이 들어가야 합니다. 출발점을 기준으로 하면 4가 제일 작은 값이네요.
다음으로 1번 인덱스를 보면 7이 나왔습니다. 4는 7보다 작으므로 여전히 4는 최솟값입니다. 이 리스트에서는 2가 나올 때까지 계속 4가 최솟값의 자리를 유지하다가 2가 나오는 순간 최솟값이 2로 바뀝니다.
이후, 이 리스트에는 더이상 2보다 작은 값이 없으므로 0번 인덱스의 값 4와 3번 인덱스의 값 2의 자리를 바꿔줍니다. 이렇게 하면 0번 인덱스에 2가 들어가면서 최솟값이 됩니다.
some_list = [2, 7, 5, 4, 6, 9]이제 0번 인덱스의 값이 정해졌으니 다음으로 1번 인덱스에 들어갈 값을 찾습니다. 다시 1번 인덱스부터 5번 인덱스까지 살펴 보죠. 1번 인덱스의 7은 그 다음 인덱스의 5를 만나게 되면 최솟값의 자리를 넘겨줍니다.
마찬가지로 5는 4를 만나는 순간 자리를 넘겨주고 그 이후로는 더 작은 값이 없으니 넘어갑니다. 결과적으로는 4가 1번 인덱스에 들어가게 되죠.
some_list = [2, 4, 7, 5, 6, 9]이런 식으로 인덱스를 넘어가면서 두 수를 비교하고 기준 수보다 상대 수가 더 작으면 자리를 바꾸면 됩니다. 이 과정을 바복하면 최종적으로 다음 리스트가 완성됩니다. 맨 마지막 인덱스에는 최댓값이 오게 되죠.
some_list = [2, 4, 5, 6, 7, 9]정리하자면 선택 정렬은 각 위치에 어떤 값이 들어갈지 찾는 정렬입니다.
참고 사항으로 선택 정렬을 구현한 코드와 그 예시를 보여 드리겠습니다.
def selection_sorting(my_list):
for i in range(len(my_list)-1):
min_index = i
for j in range(i+1, len(my_list)):
if my_list[j] < my_list[min_index]:
min_index = j
temp = my_list[i]
my_list[i] = my_list[min_index]
my_list[min_index] = temp
return my_listprint(selection_sorting([4, 7, 5, 2, 6, 9]))[2, 4, 5, 6, 7, 9]👮♀️ 삽입 정렬
두번째로 삽입 정렬(Insertion Sort)을 알아봅시다. 삽입 정렬은 선택 정렬과 달리 각 값이 어떤 위치에 들어갈지를 찾습니다. 값이 아닌 위치를 찾아야 하는 것이죠.
카드 게임을 예로 들어 봅시다. 이미 정렬된 덱을 가지고 있는데 상대가 새로운 번호의 카드를 넘겨주었습니다. 그럼 정렬된 덱 사이에서 알맞은 위치를 골라 새로운 카드를 넣어주면 됩니다.
이제 리스트의 예시를 봅시다.
some_list = [4, 7, 5, 2, 6, 9]우선, 7을 기준 수로 봅시다. 일단 7의 뒷 자리는 볼 필요가 없습니다. 4와 7을 비교했을 때, 7이 더 크므로 변경 사항이 없습니다.
some_list = [4, 7]이제 5까지 범위를 넓혀 봅시다. 7은 5보다 큰 수 이므로 7을 오른쪽으로 한 칸 옮기고 7이 빠진 빈 자리에 5를 넣으면 됩니다.
some_list = [4, 5, 7]다음으로 2까지 범위를 넓힙니다. 5와 비교했을 때, 2가 작으므로 5를 오른쪽으로 한 칸 옮깁니다. 2는 4와 7보다도 작으므로 4와 7도 오른쪽으로 한 칸 옮깁니다. 그럼 인덱스 0번이 비겠죠? 그 자리에 2를 넣어주면 됩니다.
some_list = [2, 4, 5, 7]이렇게 맨 마지막 인덱스까지 기준 수와 상대 수를 비교하고 더 큰 값이 나오면 그 수를 오른쪽으로 한 칸씩 민 다음 빈 자리에 기준 수를 넣어주면 됩니다.
some_list = [2, 4, 5, 6, 7, 9]삽입 정렬의 코드와 그 예시도 함께 볼까요?
def insertion_sorting(my_list):
for end in range(1, len(my_list)):
for i in range(end, 0, -1):
if my_list[i-1] > my_list[i]:
temp = my_list[i-1]
my_list[i-1] = my_list[i]
my_list[i] = temp
return my_listprint(insertion_sorting([4, 7, 5, 2, 6, 9]))[2, 4, 5, 6, 7, 9]👮♀️ 정렬 알고리즘 비교
이 두 가지 방법 외에도 큌, 힙, 거품 등의 정렬 알고리즘이 있습니다. 그런데 이 많은 정렬 알고리즘 중 가장 효율적인 것은 어떤 정렬일까요?
이 사이트에는 여러 가지 정렬의 효율을 다양한 상황에서 보여줍니다.
몇 가지 예를 보자면 거의 정렬된 상태의 리스트를 정렬할 때에는 삽입 정렬이 가장 빠르지만 순서가 랜덤인 리스트를 정렬할 때는 '힙'이라는 정렬이 가장 빠르다고 합니다.
정반대로 정렬된 리스트의 경우, 삽입 정렬이 매우 오래 걸린다고 하네요. 선택 정렬과 합병 절렬은 상황에 영향을 받지 않고 시간도 일정하게 소요된다고 합니다.
정리하자면, 정렬에는 절대적으로 좋은 답이 없다고 볼 수 있습니다. 상황에 따라 각 알고리즘이 지니는 장단점이 있기 때문이죠. 이처럼 알고리즘을 공부할 때에는 문제 해결 뿐만이 아니라 알고리즘 자체가 효율적인지 평가할 수 있어야 합니다.
* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.