KoreanFoodie's Study

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

Data Structures, Algorithm

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

hashnut 2019.09.19 15:42

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)
0 Comments
댓글쓰기 폼