선택 정렬 (Selection Sort) 알고리즘 (with Python3)

정렬

정렬(sort)은 자료의 크기를 순서대로 나열하는 것을 뜻한다.

 

예를들어 아래와 같은 경우를 말한다.

• 입력: 정렬할 리스트(예: [35, 9, 2, 85, 17])

• 출력: 순서대로 정렬된 리스트(예: [2, 9, 17, 35, 85])

 

선택 정렬

정렬에는 여러가지 방법이 있는데, 본 글은 선택 정렬(Selection Sort)에 대한 내용이다.

 

다른 방법의 정렬 알고리즘은 아래 글을 참고한다.

• 2020/03/21 - [Algorithm] - 삽입 정렬 (Insertion Sort) 알고리즘 (with Python3)
• 2020/03/25 - [Algorithm] - 병합 정렬 (Merge Sort) 알고리즘 (with Python3)
• 2020/03/25 - [Algorithm] - 퀵 정렬 (Quick Sort) 알고리즘 (with Python3)
• 2020/03/25 - [Algorithm] - 버블 정렬 (Bubble Sort) 알고리즘 (with Python3)

 

선택 정렬은 리스트 중에서 가장 작은 값 (또는 가장 큰 값)을 선택하여 리스트의 앞(또는 뒤)쪽으로 swap 하는 방식이다.

 

예를들어, [2, 11, 3, 7, 9] 와 같이 리스트가 있을때,

• [2, 11, 3, 7, 9] => 가장 작은 값: 2 => [2, 11, 3, 7, 9]
• [2, 11, 3, 7, 9] => 가장 작은 값: 3 => 3과 11을 교환: [2, 3, 11, 7, 9]
• [2, 3, 11, 7, 9] => 가장 작은 값: 7 => 7과 11을 교환: [2, 3, 7, 11, 9]
• [2, 3, 7, 11, 9] => 가장 작은 값: 9 => 9와 11을 교환: [2, 3, 7, 9, 11]
• [2, 3, 7, 9, 11] => 가장 작은 값: 11 => [2, 3, 7, 9, 11]

 

코딩 (with python3)

위 방식을 코드로 작성해보면 (아래 코드는 unittest 기반으로 작성되었다)

 

일반적인 선택정렬

# -*- coding: utf-8 -*-

import unittest


class Exam08(unittest.TestCase):

    @classmethod
    def setUp(cls):
        pass

    def test_selection_sort(self):
        """선택 정렬을 이용한 정렬 방법"""
        data = [2, 11, 3, 91, 7, 50, 33]
        length = len(data)

        for i in range(length):
            min_idx = i

            for j in range(i+1, length):
                # 더 작은 최솟값이 있다면, 교환(swap)한다.
                if data[min_idx] > data[j]:
                    tmp = data[min_idx]
                    data[min_idx] = data[j]
                    data[j] = tmp

            print("{} 회차: {}".format(i+1, data))

        self.assertEqual([2, 3, 7, 11, 33, 50, 91], data)


if __name__ == "__main__":
    unittest.main()

1 회차: [2, 11, 3, 91, 7, 50, 33]
2 회차: [2, 3, 11, 91, 7, 50, 33]
3 회차: [2, 3, 7, 91, 11, 50, 33]
4 회차: [2, 3, 7, 11, 91, 50, 33]
5 회차: [2, 3, 7, 11, 33, 91, 50]
6 회차: [2, 3, 7, 11, 33, 50, 91]
7 회차: [2, 3, 7, 11, 33, 50, 91]

위 test_selection_sort 메소드 처럼 정렬하는 방법이 선택정렬이다.

 

시간복잡도를 계산해보면,

1회차 n-1번 수행

2회차 n-2번 수행

...

n-2회차 2번 수행

n-1회차 1번 수행

 

총 1 + 2 +... + (n-2) + (n-1) = (n-1) * (n-2) / 2 번 수행한다.

즉, O(N^2) 이다.

Python 답게 풀기

파이썬에는 가장 작은 값을 구해주는 메소드가 있기 때문에 따로 만들 필요가 없다. min() 메소드를 이용한다.

def test_python_selection_sort(self):
    """파이썬 답게 풀어보기"""
    data = [2, 11, 3, 91, 7, 50, 33]
    sorted_data = list()

    while data:  # data 에 값이 없을때까지 반복한다.
        min_num = min(data)  # 리스트 중 `가장 작은 값`을 찾는다.
        data.remove(min_num)  # 데이터에서 `가장 작은 값`을 제거한다.
        sorted_data.append(min_num)  # `가장 작은 값`을 `결과 리스트`에 넣는다.

    self.assertEqual([2, 3, 7, 11, 33, 50, 91], sorted_data)

결과는 동일하다.

 

Reference

• https://thebook.io/006935/part03/ch08/03-01/