整列 / Sorting
뭔가가 주어졌을 때 이것을 정해진 순서대로 가지런하게 나열하는 것을 의미한다.
컴퓨터 분야에서 중요시되는 문제 가운데 하나로 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제이다. 실제 컴퓨터 분야에서 사용하는 데이터의 경우 숫자의 순서나 어휘의 순서대로 정렬한 다음 사용해야 되는 경우가 거의 항상 발생하는데 이걸 얼마나 효과적으로 해결할 수 있느냐가 정렬 문제의 핵심이다.
데이터를 정렬해야 하는 이유는 탐색을 위해서이다. 사람은 수십에서 수백 개의 데이터를 다루는 데 그치지만 컴퓨터가 다뤄야 할 데이터는 보통이 백만 개 단위이며 데이터베이스 같은 경우 이론상 무한 개의 데이터를 다룰 수 있어야 한다. 탐색할 대상 데이터가 정렬되어 있지 않다면 순차 탐색 이외에 다른 알고리즘을 사용할 수 없지만 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다.
대부분의 경우 삽입/삭제보다는 데이터를 조회하는 것이 압도적으로 많고 조회에 필요한 것이 바로 검색이다.
안정 정렬(stable sort)은 중복된 값을 입력 순서와 동일하게 정렬한다. 예를 들어 다음 그림과 같이 지역별 발송 시각을 시간 순으로 정렬한 택배 발송 로그가 있다고 가정해보자. 안정 정렬의 경우에는 기존의 시간 순으로 정렬했던 순서는 지역명으로 재정렬하더라도 기존 순서가 그대로 유지된 상태에서 정렬이 이뤄진다. 그러나 불안정 정렬의 경우에는 시간순으로 정렬한 값을 지역명으로 재정렬하면 기존의 정렬 순서는 무시된 채 모두 뒤죽박죽 뒤섞이고 만다.
이처럼 입력값이 유지되는 안정 정렬 알고리즘이 유지되지 않는 불안정 정렬 알고리즘보다 훨씬 더 유용하리라는 점은 쉽게 예상할 수 있을 것이다. 대표적으로 병합 정렬과 버블 정렬은 안정 정렬이며, 반면 퀵 정렬은 불안정 정렬이다. 게다가 입력값에 따라 버블 정렬 만큼이나 느려질 수 있다. 그야말로 최고의 알고리즘으로 칭송받는 퀵 정렬이 경우에 따라서는 최악의 알고리즘이 될 수도 있다. 이처럼 고르지 않은 성능 탓에 실무에서는 병합 정렬이 여전히 활발히 쓰이고 있다.
python에서 자료를 정렬할 때 쓰는 방법에는 두 가지가 있는데, 바로 리스트에 sort() 메소드를 적용하는 방법과 sorted() 내장함수를 이용하는 방법입니다. 그렇다면 이 두 방법은 어떻게 다르고, 어떤 상황에서 어느 함수를 이용해야 하는지 알아보겠습니다.
list.sort()
sorted(list)
우선, sort 함수는 리스트명.sort() 형식으로 이용하는 리스트형의 메소드입니다. 즉, 이 함수는 입력값으로 리스트밖에 받지 못합니다. 또, 이 함수는 리스트 원본값을 직접 수정합니다.
또, sorted()함수와는 다르게, 정렬을 수행한 리스트를 따로 반환하지 않습니다.
sorted 함수는 sorted(리스트명) 형식으로 이용하는 내장함수이며, 리스트 원본 값은 그래도 유지합니다. sort 함수와는 다르게 어떤 입력값이든 받을 수 있습니다. 또, 이 함수는 정렬 작업을 수행한 후의 값을 반환합니다.
원본을 유지해야 할 때에는 sorted() 함수를 이용하면 됩니다.
리스트 말고 다른 자료형을 정렬할 때에는 sorted() 함수를 이용하면 됩니다.
원본이 필요 없을 때에는 시간, 공간 절약을 위해 sort() 함수를 이용하면 됩니다.
list를 이용할 때에는 시간, 공간 절약을 위해 sort() 함수를 이용하면 됩니다.
흔히 Bubble sort, Insertion sort는 평균 시간 복잡도 𝑂(𝑛2)ㅍ으로 느린 정렬 알고리즘, Merge sort, Heap sort, Quick sort는 평균 O(nlogn)으로 빠른 알고리즘으로 알려져 있다. 정렬의 성능을 파악하는 지표에 시간은 필수이므로 Merge sort, Heap sort, Quick sort를 사용하는 것이 좋을 것 같다. 이 세 개의 정렬 알고리즘 중 어떤 것을 표준 정렬 알고리즘으로 선정하는 것이 좋을까?
최선의 경우 O(n), 최악의 경우 O(nlogn)에 추가 메모리도 들지 않는 Heap sort가 제일 성능이 좋은 알고리즘이 아닐까 하는 생각이 들 수도 있지만 평균 시간 복잡도가 O(nlogn)이라는 의미를 좀 더 자세히 살펴볼 필요가 있다.
시간 복잡도가 O(nlogn)이라는 말은 실제 동작 시간은 C×nlogn+α라는 의미이다. 상대적으로 무시할 수 있는 부분인 α 부분을 제하면 nlogn에는 앞에 C라는 상수가 곱해져 있어 이 값에 따라 실제 동작 시간에 큰 차이가 생긴다. 이 C라는 값에 큰 영향을 끼치는 요소로 '알고리즘이 참조 지역성(Locality of reference) 원리를 얼마나 잘 만족하는가'가 있다.
참조 지역성 원리란, CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리이다. 쉽게 말하자면, 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 담아놓는 것이다. 메모리를 연속으로 읽는 작업은 캐시 메모리에서 읽어오기에 빠른 반면, 무작위로 읽는 작업은 메인 메모리에서 읽어오기에 속도의 차이가 있다.
실생활 데이터의 특성을 고려하여 더욱 빠르게 고안된 이 알고리즘은 최선의 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우 시간 복잡도는
O(nlogn)이다. Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 Merge sort에 비해 적은 추가 메모리를 사용하여 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘이다.
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 선택 정렬과 기본 개념이 유사하다.
배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
def bubble_sort(arr):
for i in range(len(arr) - 1, 0, -1):
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
이전 패스에서 앞뒤 자리 비교(swap)이 한 번도 일어나지 않았다면 정렬되지 않는 값이 하나도 없었다고 간주할 수 있습니다. 따라서 이럴 경우, 이후 패스를 수행하지 않아도 됩니다.
Initial: [1, 2, 3, 5, 4]
Pass 1: [1, 2, 3, 4, 5] => Swap 있었음
*
Pass 2: [1, 2, 3, 4, 5] => Swap 없었음
* *
=> 이전 패스에서 swap이 한 번도 없었으니 종료
def bubble_sort(arr):
for i in range(len(arr) - 1, 0, -1):
swapped = False
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
이전 패스에서 앞뒤 자리 비교(swap)가 있었는지 여부를 체크하는 대신 마지막으로 앞뒤 자리 비교가 있었던 index를 기억해두면 다음 패스에서는 그 자리 전까지만 정렬해도 됩니다. 따라서 한 칸씩 정렬 범위를 줄여나가는 대신 한번에 여러 칸씩 정렬 범위를 줄여나갈 수 있습니다.
Initial: [3, 2, 1, 4, 5]
Pass 1: [2, 1, 3, 4, 5] => 마지막 Swap 위치가 index 1
^ *
Pass 2: [1, 2, 3, 4, 5] => 중간 패스 skip하고 바로 index 1로 보낼 값 찾기
^ * * *
def bubble_sort(arr):
end = len(arr) - 1
while end > 0:
last_swap = 0
for i in range(end):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
last_swap = i
end = last_swap
배열에 9, 6, 7, 3, 5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
내부 반복문에서는 현재 index부터 마지막 index까지 최소값의 index를 찾아내고, 외부 반복문에서는 이 최소값의 index와 현재 index에 있는 값을 상호 교대(swap)합니다. 각 index에 대해서 최소값을 찾기 위해 대소 비교는 여러 번 일어나나 상호 교대(swap)은 딱 한번만 일어납니다.
def selection_sort(arr):
for i in range(len(arr) - 1):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
삽입 정렬은 한마디로 표현하면 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다.
배열에 8, 5, 6, 2, 4가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
def insertion_sort(arr):
for end in range(1, len(arr)):
for i in range(end, 0, -1):
if arr[i - 1] > arr[i]:
arr[i - 1], arr[i] = arr[i], arr[i - 1]
기존에 있던 값들은 이전 패스에서 모두 정렬되었다는 점을 활용하면 불필요한 비교 작업을 제거할 수 있습니다. 예를 들면, 아래와 같이 기존 정렬 범위 [1, 2, 3, 5]
에 4가 새롭게 추가된다면, 5는 4보다 크기 때문에 swap이 필요하지만, 3은 4보다 작기 때문에 swap이 필요없습니다. 그리고 3보다 앞에 있는 숫자들은 기존 패스에서 이미 정렬을 해놓았기 때문에 당연히 3보다는 작을 것이며, 더 이상의 4와 대소 비교는 무의미합니다. 이 사실을 이용하면, 새롭게 추가된 값보다 작은 숫자를 만나는 최초의 순간까지만 내부 반복문을 수행해도 됩니다.
[1, 2, 3, 5, 4, ...]: 5 > 4 => swap
* * * * ^
[1, 2, 3, 4, 5, ...]: 3 < 4 => OK => all sorted!
* * * * *
def insertion_sort(arr):
for end in range(1, len(arr)):
i = end
while i > 0 and arr[i - 1] > arr[i]:
arr[i - 1], arr[i] = arr[i], arr[i - 1]
i -= 1
swap 작업없이 단순히 값들을 shift 시키는 것만으로도 삽입 정렬의 구현이 가능합니다. 앞의 값이 정렬 범위에 추가시킨 값보다 클 경우 앞의 값을 뒤로 밀다가 최초로 작은 값을 만나는 순간 그 뒤에 추가된 값을 꼽으면 됩니다.
def insertion_sort(arr):
for end in range(1, len(arr)):
to_insert = arr[end]
i = end
while i > 0 and arr[i - 1] > to_insert:
arr[i] = arr[i - 1]
i -= 1
arr[i] = to_insert
네이버D2 기술 블로그 - https://d2.naver.com/helloworld/0315536
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
https://www.daleseo.com/sort-insertion/
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
https://www.daleseo.com/sort-selection/