기준에 따라 데이터를 정렬

정렬 알고리즘 개요

정렬: 데이터를 특정한 기분에 따라서 순서대로 나열하는 것

프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나로, 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(binary search)이 가능해진다.

다양한 정렬 알고리즘이 있지만 이 책에서는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 언급하려고 한다. 더불어 파이썬에서 제공하는 기본 정렬 라이브러리를 적용하여 좀 더 효과적인 정렬 수행 방법도 다루려 한다.

정렬 되지 않은 0부터 9가 쓰여 있는 카드가 주어진 상황을 이용해 정렬에 대해 설명하겠다.

<aside> 🃏 7 5 9 0 3 1 6 2 4 8

</aside>

선택 정렬(Selection Sort)

이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까?

이 방법은 가장 원시적인 방법으로 매번 ‘가장 작은 것을 선택’한다는 의미에서 선택 정렬 알고리즘이라고 한다.

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.

array = [7,5,9,0,3,1,6,2,4,8]
for i in range(len(array)):
        min_idx = i
        for j in range(i+1,len(array)):
                if array[min_idx] > array[j]:
                        min_idx = j
        array[i], array[min_idx] = array[min_idx], array[i] #swap
print(array)

시간 복잡도: O(N^2)

삽입 정렬(Insertion Sort)

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다. 다른 접근 방법을 생각해보자.

‘데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?’

삽입 정렬은 선택 정렬과 비교해서 구현 난이도가 높은 편이지만 실행 시간 측면에서 더 효율적이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어 있을 때’ 훨씬 효율적이다.

삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미를 가지고 있으며, 첫 번째 데이터는 이미 정렬이 되었다고 간주하여 두 번째 데이터부터 정렬을 시작한다.

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):
                if array[j] < array[j-1]: #한칸씩 왼쪽으로 이동
                        array[j], array[j-1] = array[j-1], array[j] #swap
                else: break
print(array)