선택정렬(Selection Sort) - 파이썬 코드 구현

selection sort python code
선택정렬을 파이썬 코드로 구현해 보자.

---

 

선택정렬(Selection sort 기본 설명)

위키피디아에 있는 정의를 참고해 보자.

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

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

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

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

그림으로 표현하면,

이런식으로 되는데, 자세히 보면 '패스'(배열 한 번을 훑는 것)마다, 정렬이 완료된 배열의 길이가 늘어나는 것을 볼 수 있다.

즉, 패스 1은 1짜리 정렬된 배열을 만들고, 패스 2는 정렬된 2짜리 배열을 만든다. 그러므로 패스 3에서는 (전체 배열의 길이) - (패스 2까지 정렬이 완료된 배열의 길이) 만 훑어서 그 중 최솟값 선택한 후, 2개 짜리의 정렬된 배열의 마지막에 붙여주기만 하면 된다.

파이썬 코드 :

# Selection sort implementation
import sys #for sys.maxsize

array1 = [4,3,9,1,5,6,7,22,3243,436,56,4,73,45,24,23,5]
array2 = [100]

def swap(array, a, b):
    array[a], array[b] = array[b], array[a]


def selec_sort(input_arr):
    for i in range(len(input_arr)):
        min_index = i
        my_min = input_arr[i]

        for j in range(i, len(input_arr)):
            if input_arr[j] < my_min:
                my_min = input_arr[j]
                min_index = j
        swap(input_arr, i, min_index)


    return input_arr


def print_array(input_arr):
    for i in range(len(input_arr)):
        print(input_arr[i], end=' ')
    print()

print_array(array1)

array3 = selec_sort(array1)
selec_sort(array3)

print_array(array3)