[Theory] Sort. part 1
파이썬에서는 기본적으로 정렬(sort) 기능을 제공해줍니다. * 다른 언어의 경우는 제가 잘 몰라서 파이썬 한정으로만 얘기합니다. 그러다 보니, 정렬 알고리즘에 대해서 대략적으로 어떤 알고리즘이 있다, 정도로만 알고 넘어갔었습니다. 그런데 최근 알고리즘 문제를 풀던 도중, 정렬 알고리즘을 직접 구현해야 하는 경우가 생겼습니다. 막상 구현을 하려고 하니 생각처럼 간단하지만은 않아서, 이 기회를 살려 정렬 알고리즘을 제대로 정리하고 넘어가야겠단 생각을 했습니다.
이 글에서는 대표적이면서도 개중에 간단한 정렬 알고리즘인, 선택정렬 / 삽입정렬 / 버블정렬의 경우를 먼저 설명하고, 다음 글을 통해서 다른 정렬들에 대해서도 다뤄보겠습니다.
* 기본적으로 오름차순 정렬을 다루도록 하겠습니다.
선택정렬(Selection Sort)
선택정렬이란, 리스트에서 아직 정렬이 안된 부분의 원소들 중에서 최솟값을 찾아서, 그 값을 정렬 안된 부분의 가장 왼쪽 원소와 교환하는 방식을 반복하여 정렬하는 방식을 말합니다.
def selection_sort(input_list):
for i in range(len(input_list)):
minimum_index = i
for j in range(i+1, len(input_list)):
if input_list[j] < input_list[minimum_index]:
minimum_index = j
input_list[i], input_list[minimum_index]= input_list[minimum_index], input_list[i]
return input_list정렬되지 않은 리스트 a = [3, 1, 2, 123, 213, 7, 8, 12, 0]을 입력 값으로 주고, 각 단계에서 일어나는 변화를 출력 값을 통해 확인해보겠습니다.
Step 1.
우선 정렬 안된 부분에서 최솟값을 찾아야 합니다. 정렬 안된 부분 중 첫 번째 값을 우선 최솟값이라 설정하고, 그다음 값부터 마지막 값까지 순회를 하며 비교하여, 더 작은 값을 찾을 때마다 최솟값을 갱신해주며 최종적으로 정렬 안된 부분 중 최솟값을 찾습니다.
Step 2.
정렬 안된 부분의 첫 번째 요소와, 위에서 찾은 최솟값을 교환해줍니다.
최솟값을 찾은 후, 그 값을 덮어 씌우는 게 아니라 교환해주는 것이기 때문에 해당 값 자체가 아닌 해당 값의 인덱스를 찾는다는 것만 유의하면 어렵지 않게 해결할 수 있을 것입니다.
삽입정렬(Insertion Sort)
삽입정렬이란, 리스트를 정렬된 부분과 정렬 안된 부분으로 나누어, 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분에 삽입하는 방식입니다. 선택 정렬은 정렬 안된 부분에서 기본적인 정렬이 이루어지는 반면(최솟값을 찾는 행위), 삽입정렬은 정렬된 부분을 계속해서 재정렬해나가는 방식입니다.
def insertion_sort(input_list):
for i in range(1, len(input_list)):
for j in range(i):
if input_list[i] < input_list[j]:
temp = input_list[j:i]
input_list[j] = input_list[i]
input_list[j+1:i+1] = temp
return input_list위에서 사용한 리스트 a를 통해 삽입정렬의 정렬 과정도 확인해보겠습니다.
Step 1.
정렬 안된 부분의 첫 번째 원소를 뽑은 후, 정렬된 부분의 원소 값들과 비교해줍니다. 앞에서부터 순차적으로 비교하여 첫 번째 원소 값보다 더 큰 값을 가진 원소를 만날 경우, 해당 위치가 첫 번째 원소가 삽입될 위치입니다.
Step 2.
원소 값을 교환해주는 것이 아닌 삽입해주는 것이기 때문에, 삽입 위치의 인덱스부터 정렬된 부분의 마지막 인덱스의 원소까지를 한 칸씩 뒤로 미뤄줘야 합니다. 이 부분에서 값이 덮어씌워져서 없어지는 것을 대비하여 저는 임시 변수를 지정하여 해당 값들을 담아주었습니다.
for 문을 내림차순으로 순회하는 방식을 사용하여, 정렬 안된 부분의 첫 번째 요소를 정렬된 부분의 뒤에서부터 교환해나가는 방식으로 코드를 구현하면, 좀 더 간단하게 구현할 수 있습니다.
def insertion_sort(input_list):
for i in range(1, len(input_list)):
for j in range(i, 0, -1):
if input_list[j-1] > input_list[j]:
input_list[j], input_list[j-1] = input_list[j-1], input_list[j]
return(input_list)
버블정렬(Bubble Sort)
버블정렬이란, 원소를 앞에서부터 두 개씩 비교하여, 큰 값을 앞으로 계속 뒤로 보내주어 정렬하는 방식입니다.
def bubble_sort(input_list):
i = len(input_list)
while i != 0:
for j in range(i-1):
if input_list[j] > input_list[j+1]:
input_list[j], input_list[j+1] = input_list[j+1], input_list[j]
i -= 1
return input_list
Step 1.
버블정렬의 경우 앞의 정렬 방법들과는 다르게 정렬이 뒤에서부터 이루어집니다. 최솟값을 앞으로 보내는 방식이 아니라, 최댓값을 뒤로 보내는 방식이기 때문입니다. 그래서 저는 while 문을 사용해서 반복 한 번마다 비교 범위를 하나 씩 줄여가는 방식으로 코드를 구현해보았습니다.
Step 2.
비교 범위 내의 원소들을 앞에서부터 순차적으로 비교하여 큰 값의 원소를 더 큰 인덱스 위치로 교환해주는 방식으로 진행하였습니다.
선택정렬, 삽입정렬, 버블정렬에 대해서 다뤄보았습니다. 다음 글 part 2에서는 병합정렬, 쉘정렬, 퀵정렬 등 여기서 다루지 않은 다른 정렬 알고리즘들에 대해서 이야기해보겠습니다.