컴퓨터 공학에서는 가장 필수로 가르치는 몇몇 과목이 있는데, 대표적으로 자료구조와 알고리즘이 있다.
특히 정렬 알고리즘은 자료구조를 배우면서도 종종 언급되곤 하는데, 그만큼 기초적이면서 활용도가 많다는 뜻이다.
분명 학교 과목으로 배웠지만, 산업기사 자격증을 따고 나서 다 잊어버렸다...
코딩 테스트를 위해 공부할 겸, 스스로 복기하기 위해 글을 정리하게 되었다.
(앞으로 꾸준히 포스팅 있길)
정렬되지 않은 주어진 데이터가 있다고 하자.
이럴 때 가장 단순하게 이를 정렬하는 방법에는 어떤 것이 있을까?
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
맨 처음에 프로그램을 배울 때 당시의 내 생각으로는 모든 수를 비교하여, 가장 작은 순서대로 정렬하는 것을 떠올릴거 같다.
이미 첫 번째 원소로 7이 있으므로, 이 원소를 기준으로 더 작은 값만을 선택해 나가면 된다.
두 번째 원소인 5는 7보다 작으므로, 최소값의 기준을 5로 변경한다.
세 번째 원소인 9는 최소값인 5보다 크므로, 넘어간다.
네 번째 원소인 0은 최소값인 5보다 작으므로, 최소값의 기준을 0으로 변경한다.
이후 이와 같은 식으로 반복하다가, 마지막 원소까지 비교가 끝나면 첫 번째 원소와 최소 값을 가진 원소를 서로 바꾼다.
위 이미지를 코드로 옮겨보면 다음과 같다.
# 가장 첫번째 자리의 수로는 가장 작은 수가 와야하므로
# arr[min]과 arr[i]를 비교하여 arr[i]가 arr[min]보다 작을 경우
# min = i로 값을 변경
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)-1):
if array[min] > array[i]:
min = i
if min != 0:
array[0], array[min] = array[min], array[0]
print(array)
# [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
이제 이걸 배열 마지막까지 반복하면, 모든 수가 정렬될 것이다.
위와 같은 형식의 정렬 방법을 선택 정렬이라고 한다.
전체를 정렬하는 코드는 아래와 같다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min = i
for j in range(i + 1, len(array)):
if array[min] > array[j]:
min = j
array[i], array[min] = array[min], array[i]
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
떠올리기 쉬운만큼 단순한 면이 있고, 그만큼 비효율적인 부분이 크다.
우선 시간복잡도로는 for 반복문이 2중으로 중첩되어 있으므로 O(n^2)가 될 것이다.
이는 주어진 입력의 크기가 커질수록 연산횟수가 커진다는 뜻이다.
단순히 10 크기의 입력이 주어졌을 때는 100회의 연산을 해야하지만,
100 크기의 입력이 주어졌을 때는 10,000회의 연산을 해야한다.
다른 정렬 알고리즘에 비해 비효율적인 부분이 크지만,
그래도 작은 수의 입력과 빠르게 코드를 작성해야할 때는 유용하게 사용 될 수 있다고 하니
몸에 익혀두는 것이 좋을거 같다.