기초 정렬 알고리즘 - 삽입(Insertion),선택(Selection), 버블(Bubble) - Python 예제

Python List 기본 정렬 방법

1차원 배열(List of Python)에선 정렬이 필요한 경우가 많다.

 

정렬은 오름차순 정렬과 내림차순 정렬이 존재하고, Python의 경우 내장 함수와 List 클래스의 메소드로 List의 정렬을 기본적으로 제공한다.

 

아래는 Python에서 List를 각각 오름차순, 내림차순 정렬하는 코드의 예시이다.

TestList=[5, 15, 2, 6, 12, -15, 4, 9, 11]

TestList.sort() # inplace Sort - Method of List
TestList.sort(reverse = True) # inplace Sort - Method of List

sorted(TestList) # Function of Python
sorted(TestList, reverse=True) # Function of Python

.sort()와 sorted()는 기본적으로 Python에서 제공하는 리스트 정렬 함수, 메소드이다.

 

두 방법은 작은 차이가 존재하는데, .sort()는 inplace 방식이라 원본 리스트를 직접 수정한다. 하지만, sorted()는 원본 리스트를 직접 수정하지 않는다. 따라서 아래와 같은 차이가 존재한다.

ListA=[5, 15, 2, 6, 12, -15, 4, 9, 11]

ListA.sort() # 정렬된 ListA - 이때는 반환하는 리스트가 없다.
print(ListA) # [-15, 2, 4, 5, 6, 9, 11, 12, 15]

#######################################

ListB=[5, 15, 2, 6, 12, -15, 4, 9, 11]

ListBB = sorted(ListB) # 정렬된 ListBB
print(ListB) # [5, 15, 2, 6, 12, -15, 4, 9, 11]
print(ListBB) # [-15, 2, 4, 5, 6, 9, 11, 12, 15]

---

정렬 알고리즘 - Sort Algorithm

Python에서 제공하는 강력한 정렬 기능이 존재하지만, 어떤 정렬 알고리즘이 사용되었는지를 이해하기 위해 정렬 알고리즘의 가장 기초적인 정렬 알고리즘에 대해서 정리해보려고 한다.

 

정렬 알고리즘에 대해선 아래의 기준들로 구분이 가능하다.

 

1. 시간 복잡도 - Time Complexity
2. Stable & Unstable
3. 공간 복잡도 - Space Complexity

기준 1은 Big O Notation을 통해 정렬 알고리즘의 최악, 평균 시간 복잡도 등을 구분하는 것이다.

기준 2는 동일한 값이 존재할 때, 최초의 순서를 유지하느냐(Stable) 유지하지 못하느냐(Unstable)에 따라 나눌 수 있다.

기준 3는 정렬을 수행할 때 추가적인 메모리 공간(변수)이 필요한가에 따라 알고리즘을 구분할 수 있다. - 공간복잡도

 

이번 글에서는 정렬 알고리즘에서 가장 기본적인 삽입 정렬(Insertion Sort), 선택(Selection Sort), 버블 정렬(Bubble Sort) 알고리즘에 대해 살펴보겠다.

---

삽입 정렬 - Insertion Sort

삽입 정렬은 기본적으로 O(N^2)의 시간복잡도를 가지는 정렬 알고리즘이다.

또한, 입력된 중복값의 순서를 유지(Stable)하는 알고리즘이고, 추가적인 변수가 필요없는 O(1) 공간복잡도를 갖는다.

 

일반적으로 입력된 배열 원소의 크기가 작으면 좋은 성능을 가지는 알고리즘이다.

 

삽입 정렬의 기본적인 방식은 아래와 같다.

삽입 정렬은 하나의 배열 안에서 정렬된 부분과 정렬되지 않은 부분을 나누어 정렬되지 않은 원소를 하나씩 선택하여 정렬된 배열의 원소와의 비교를 통해서 적절한 위치에 삽입하는 방식을 갖는다.

오름차순, 앞쪽부터 시작하는 삽입 정렬의 경우 아래의 과정을 갖는다.

- 최초에 첫 번째 원소는 정렬된 영역이다.
1. 배열의 두 번째 원소부터 시작한다.
2. 현재 원소를 정렬된 부분과 비교하여 삽입할 위치를 찾는다.
3. 정렬된 부분에서 현재 원소보다 큰 값들을 오른쪽으로 한 칸씩 이동시킨다.
4. 삽입할 위치를 찾았다면 현재 원소를 해당 위치에 삽입한다.
5. 위의 과정을 반복하여 전체 배열이 정렬될 때까지 진행한다.

첫 번째 원소는 정렬된 영역이라고 고정하고, 나머지 원소들을 하나씩 선택하기 위한 반복문(2 ~ N)과,
선택한 나머지 원소들을 정렬된 영역의 원소들과 비교하여 삽입할 위치를 찾는 반복문이 사용되어 O(N^2) 시간복잡도를 갖는다.

 

아래는 삽입 정렬(Insertion Sort)을 구현해본 예시이다.

def insertion_sort(input_list):
    for i in range(1, len(input_list)):
        key = input_list.pop(i)
        j = i - 1
        while j >= 0 and input_list[j] > key:
            j -= 1
        input_list.insert(j + 1, key)
    return input_list

---

선택 정렬 - Selection Sort

선택 정렬은 O(N^2)의 시간복잡도를 갖는 알고리즘이다.

입력된 배열의 중복값들의 순서를 보장해주지 못하는(Unstable) 알고리즘이고, O(1) 공간복잡도를 갖는다.

 

선택 정렬의 방식은 아래와 같다.

선택 정렬은 배열의 각 위치에 해당하는 순서의 값(i번째 최솟값)을 배치시키는 정렬 방식이다.

즉, 배열의 첫번째 위치에 배열 전체의 최솟값을 선택한 후 배치시키고, 두 번째 위치는 두 번째 위치의 최솟값을 배치시키는 방식이다.

이를 절차대로 표현하면 다음과 같다.

1. 배열의 첫 번째 원소부터 시작한다.
2. 현재 원소를 포함한 나머지 부분에서 최솟값을 찾는다.
3. 최솟값을 현재 원소와 교환한다.
4. 위의 과정을 반복하여 전체 배열이 정렬될 때까지 진행한다.

배열의 각 위치에 해당하는 i번째 최솟값을 찾아 정렬시키는 방식이다.

각 위치를 선택하는데 사용되는 반복문(1 ~ N-1)과 각 위치에 해당하는 최솟값을 찾기 위한 반복문이 사용되기 때문에 O(N^2) 시간복잡도를 갖는다.

 

아래는 선택 정렬(Selection Sort)을 구현해본 예시이다.

def selection_sort(input_list):
    for i in range(len(input_list)):
        min_index = i
        for j in range(i+1, len(input_list)):
            if input_list[j] < input_list[min_index]:
                min_index = j
        input_list[i], input_list[min_index] = input_list[min_index], input_list[i]
    return input_list

---

버블 정렬 - Bubble Sort

버블 정렬은 O(N^2)의 시간복잡도를 갖는 알고리즘이다.

입력된 중복값의 순서를 유지(Stable)하는 알고리즘이고, O(1) 공간복잡도를 갖는다.

 

버블 정렬의 방식은 아래와 같다.

버블 정렬은 인접한 두 원소를 비교하고 교환하는 과정을 반복하여 정렬시키는 방식이다.

인접한 두 원소의 비교를 배열의 끝까지 진행하게 된다면 배열의 마지막 위치에는 최대값이 배치되기 때문에, 앞쪽에서 시작하지만  뒤쪽부터 정렬되는 방식이라고 생각할 수 있다.

이를 절차대로 표현하면 다음과 같다.
1. 배열의 첫 번째 원소부터 마지막 원소까지 반복한다.
2. 현재 원소와 다음 원소를 비교한다. 만약 현재 원소가 다음 원소보다 크다면, 두 원소의 위치를 교환한다.
3. 이 과정을 배열의 끝까지 진행한다. 가장 큰 원소가 배열의 마지막에 위치한다.
4. 위의 과정을 배열의 첫 번째 원소부터 마지막 원소 직전까지 반복한다. 이 단계를 통해 두 번째로 큰 원소가 배열의 마지막에서 두 번째 위치한다.
5. 정렬이 완료될 때까지 위의 과정을 반복한다.

양옆의 원소값들을 비교하면서, 큰 값을 마지막 위치로 가져가는 방식이다.

1 ~ N-1 번의 반복이 필요하고, i번째 최대값을 배열의 뒤로 가져가는데 반복문이 필요하므로 O(N^2) 시간복잡도를 갖는다.

 

아래는 버블 정렬(Bubble Sort)을 구현해본 예시이다.

def bubble_sort(input_list):
    n = len(input_list)
    for i in range(n):
        for j in range(n-i-1):
            if input_list[j] > input_list[j+1]:
                input_list[j], input_list[j+1] = input_list[j+1], input_list[j]
    return input_list