[Algorithm]정렬(1) - 선택, 삽입 정렬

💡정렬이란?

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열 하는것 이다. 알고리즘 문제를 풀어본 사람이라면 정렬에 대해 수도 없이 많이 들어봤을텐데, 오늘은 이 정렬에 대해서 짚고 넘어가 보자. 상황에 적절하지 못한 정렬 알고리즘을 사용하면 필요 이상으로 시간을 많이 소요하게 되는데, 이것 때문에 정렬 알고리즘을 공부하는 이유이기도 하다. 다음은 여러가지 정렬 알고리즘에 대한 설명이다. 내림차순 정렬은 기본으로 파이썬에서 제공되는 정렬 라이브러리를 이용해 오름차순 정리를 한 후, 문자열을 뒤집는 메서드를 활용하여 내림차순 정렬을 할 수 있다. 이 뒤집는 연산은 O(N)이기 때문에, 여기서는 오름차순 정렬만 다루도록 하겠다.

 

📌 선택 정렬(Selection Sort)

컴퓨터가 데이터를 정렬할때 어떻게 할지 생각해보자. 이 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하면 어떨까? 이 방법은 가장 원시적인 정렬 방법으로, 선택 정렬(selection sort)라고 부른다. 이해를 돕기 위해 예시와 함께 보자.

 

정렬 알고리즘에서는 정렬할 데이터의 갯수를 N으로 칭한다. 다음 예제에서는 N = 10인 경우를 가정한다. 또한, 다음 그림에서 회색 카드는 '현재 정렬되지 않은 데이터중 최솟값'을 의미하며, 하늘색 카드는 '이미 정렬된' 데이터를 의미한다.

 

다음은 파이썬으로 구현한 선택정렬 코드이다.

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)

 

여기서 스와프(swap)란 특정한 리스트가 주어졌을때 두 변수의 위치를 변경하는 작업을 의미한다. 파이썬에서는 간단히 리스트 내의 두 원소의 위치를 변경 할 수 있다.

# 0 인덱스와 1 인덱스의 원소 교체하기
array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)

 

  📊 선택 정렬의 시간 복잡도

그렇다면, 선택 정렬의 시간 복잡도는 어떨까? 사실 위에서 언급한 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하면 어떨까? 여기서 알고리즘을 공부 해 본사람이라면 눈치를 챌 수 있듯, 너무 연산의 횟수가 많다. 이유는 매 반복문마다 리스트를 차례로 검사하며 가장 작은 값을 찾아야 하기 때문이다.

 

선택 정렬은 N -1 번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 선택 정렬의 시간 복잡도는 O(N^2)로, 효율이 좋지 않은 정렬 알고리즘이다. 직관적으로 이해하자면, 소스코드상의 for반복문이 2중으로 겹쳐 있기 때문이다. 만약, 정렬해야 할 데이터의 갯수가 100배로 늘어나면, 이론적으로 수행시간은 10,000배가 늘어난다. 그렇다면, 이러한 시간 복잡도를 가지는 선택 정렬이 얼마나 효율적일까?

 

위의 표에서 볼 수 있듯, 선택 정렬은 효율적인 알고리즘은 아니다. 하지만 코딩 테스트에서 가장 작은 값을 찾는 일이 잦으므로 항상 기억해두자.

 

📌 삽입 정렬(Selection 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):  # 인덱스 i부터 1까지 감소하며 반복하는 문법
        if array[j] < array[j - 1]:  # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else:  # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

 

여기서 range에 대해 잠깐 짚고 넘어갈 부분이 있는데,

파이썬의 `range`는 3개의 매개 변수(`start`, `end`, `step`)를 받는다. 세 번째 매개 변수인 `step`은 숫자 간의 간격을 지정하는 역할을 한다. 이 `step` 값이 양수일 경우 `start` 인덱스부터 `end-1` 인덱스까지 `step`만큼 증가하며 순회한다. 반면, `step` 값이 -1일 경우 `start` 인덱스부터 `end+1` 인덱스까지 1씩 감소한다. 이를 이용하면 리스트를 역순으로 순회하거나 특정 범위에서 감소하는 순서로 값을 생성할 수 있다.

예를 들어, `range(5, 0, -1)`은 5부터 시작하여 1씩 감소하면서 1까지의 숫자를 생성한다.

for i in range(5, 0, -1):
    print(i, end=' ')  # 출력: 5 4 3 2 1

이 코드는 `start`가 5, `end`가 0, `step`이 -1이므로, 5에서 1씩 감소하며 1까지의 숫자를 출력한다. 이와 같이 `range` 함수의 `step` 매개 변수를 적절히 사용하면 다양한 순회 패턴을 구현할 수 있다.

삽입 정렬의 시간 복잡도는 선택 정렬과 같이 O(N^2)이다. 하지만, 여기서 꼭 기억 해야할 내용은 삽입 정렬은 현재 데이터가 정렬된 상태라면 매우 빠르게 동작 한다는 점이다. 가장 효율적인 정렬 알고리즘으로 알려진 퀵 정렬 조차도 정렬이 거의 되어있는 상황에서는 삽입 정렬이 더 빠르게 동작한다.

 

다음에는 퀵 정렬에 대해서 설명하겠다.