[알고리즘] 선택정렬

안녕하세요

이번에는 선택정렬에 대하여 알아보도록 합시다.

예제 코드는 항상 파이썬으로 됩니다.

---

선택정렬(Selection Sort) 이란?

• 제자리 정렬  알고리즘의 하나이다.

         - 데이터를 하나 옮길 때 마다 공간이 하나씩 비게 된다는 사실을 기반으로, 별도의 메모리 공간을 마련할 필요가 없다.

• 현재 선택된 데이터 이후의 데이터들과 비교하여 가장 작은값을 찾아 자리를 바꿔 정렬하는 알고리즘입니다.

---

선택정렬의 과정

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.(패스)
3. 맨 처음 위치를 뺸 나머지 리스트를 같은 방법으로 교체한다.

---

선택정렬의 특징

• 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는  Θ(n²) 만큼의 시간이 걸린다.

• 선택정렬은 알고리즘이 단순하며, 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있습니다.

• 같은 값이 있는 경우, 상대적인 위치가 변경될 수 있습니다.

---

파이썬 코드 확인

def selection_sort(value_list):
    # 마지막의 경우 자동으로 정렬되므로 -1을 해준다.
    for num1 in range(len(value_list) - 1):
        min_index = num1
        for num2 in range(num1 + 1, len(value_list)):
            if value_list[min_index] > value_list[num2]:
                min_index = num2
        value_list[num1], value_list[min_index] = value_list[min_index], value_list[num1]
    return value_list
    
    
print(selection_sort([1,5,2,4,7,3]))

해당 코드를 실행하면 

[1, 2, 3, 4, 5, 7] 과 같이 정렬된 리스트가 반환되는것을 확인 할 수 있습니다.

---

선택정렬의 시간복잡도

코드에서 보듯 리스트의 길이 n 이 주어지면, for문 중첩으로 인해 처음 for문에서 n - 1번, 두번째 for문에서 n번 수행하게 됩니다. n(n-1)번만큼 수행하는데,

빅오 표기법을 사용하면 n²만큼의 시간복잡도가 됩니다.

---

References

• 선택 정렬 - 위키백과