정렬 알고리즘은 굉장히 다양하다. 이 중 선택정렬, 삽입정렬, 퀵정렬, 계수정렬에 대해서 정리해보려고 한다.
이번 포스팅에서는 선택정렬과 삽입정렬을 정리해보려고 한다.
정렬 알고리즘으로 데이터를 정렬하면 다음에 배울 이진 탐색이 가능해진다. 따라서 정렬 알고리즘은 이진 탐색의 전처리 과정이기 때문에 제대로 짚고 넘어가도록 하자.
Selection sort (선택 정렬)
데이터가 무작위로 여러개 있을 때 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 방법이다. 가장 원시적인 방법이라고 할 수 있다.
매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 한다.
선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다.
어려운 방법이 아니어서 따로 자세한 설명은 하지 않도록 하려고 한다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
print(array)시간 복잡도는 반복문이 얼마나 중첩되었는지를 기준으로 간단하게 판단할 수 있다.
선택 정렬의 시간 복잡도는 O(N^2)이다. 2중 반복문이 사용됐기 때문이라고 할 수 있다.
만약 정렬해야 할 데이터의 개수가 100배 늘어나면 이론적으로 수행 시간은 10,000배로 늘어난다.
그렇다면 이러한 시간 복잡도를 가진 선택 정렬은 조금 비효율적일 것이다.
실제로 데이터의 개수가 100개일 때 선택 정렬 소요 시간이 0.0123초라고 하는데 10,000개 일 때는 소요 시간이 약 15초라고 한다.
선택 정렬은 기본 정렬 라이브러리를 포함해서 다른 알고리즘과 비교했을 때 매우 비효율적이다.
하지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦기 때문에 선택 정렬 소스코드에 익숙해질 필요가 있다.
Insertion sort (삽입 정렬)
선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다.
하지만 다른 측면에서 한번 생각해보자.
"데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하면 어떨까?"
삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다.
물론 삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 알려져 있다.
특히 삽입 정렬은 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.
선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하교 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.
삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다. 더불어 특정한 데이터가 적절한 위치에 들어가기 전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
(1) 다음과 같이 숫자가 있다고 먼저 가정하자.
삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 이미 정렬되어 있다고 판단하기 때문이다.
7 5 9 0 3 1 6 2 4 8
(2) 두 번째 데이터인 5가 어떤 위치로 들어갈지 판단한다. 7의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 가지 경우만 존재한다. 오름차순으로 정렬할 것이기 때문에 7의 왼쪽에 삽입한다.
5 7 9 0 3 1 6 2 4 8
(3) 이어서 9가 어떤 위치로 들어갈지 판단한다. 삽입할 수 있는 위치는 총 3가지이며 9는 5와 7보다 크기 때문에 원래 자리 그대로 두면 된다.
5 7 9 0 3 1 6 2 4 8
위와 같이 적절한 위치에 삽입하는 과정을 N-1번 반복하게 되면 모든 데이터가 정렬된 것을 확인할 수 있다.
삽입정렬에서 가장 중요한 특징은 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 뒤의 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 되는 것이다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
print(array)삽입 정렬의 시간복잡도는 O(N^2)이다. 선택 정렬과 마찬가지로 2중 반복문을 사용하기 때문이다.
참고로 하나 말하자면, 2중 반복문을 사용한다고 해서 반드시 시간복잡도가 O(N^2)인 것은 아니다. 만약에 반복문 안에서 별도로 함수가 추가된다면 해당 함수의 시간 복잡도까지 고려해야한다.
삽입 정렬의 경우에는 swap 기능만 사용되기 때문에 시간복잡도가 다음과 같은 것이다.
삽입 정렬의 가장 큰 특징은 데이터가 거의 정렬되어 있는 상태일 때 매우 빠르게 동작한다는 것이다.
만약 0부터 9까지 전부 정렬이 되어있는 상태라면 매번 첫 과정에서 위치가 결정되기 때문에 반복문을 돌지 않는다. 따라서 상수 시간만 소요되기 때문에 시간 복잡도는 O(N)이 될 것이다.
