[알고리즘][선택정렬][SelectionSort][정렬][파이썬][Python]-정리 및 코드

Selection Sort(선택 정렬)

 

선택 정렬은 버블 정렬, 삽입 정렬과 함께 가장 기본적인 정렬 알고리즘에 해당됩니다. 데이터를 처리하는 데 있어서 정렬은 가장 기본적이면서도 핵심적인 내용입니다. 선택 정렬을 살펴보기 전에 이전 포스팅에서 설명한 버블 정렬에 대해 먼저 이해하시면 선택 정렬을 이해하는데 도움이 될 겁니다.

 

 

아이디어

 

선택 정렬의 아이디어는 전체 데이터중 가장 작은 값을 앞으로 보내는 것입니다. 데이터의 앞에서부터 순서대로 선택하고 선택된 데이터의 뒤에 있는 데이터들 중 가장 값이 작은 데이터와 스왑(Swap)합니다. 이와 같은 과정을 계속해서 반복하면 데이터가 오름차순으로 정렬이 되는 것을 확인할 수 있습니다. 아래에서 구체적인 알고리즘과 코드를 살펴보겠습니다.

 

알고리즘

 

선택 정렬의 알고리즘은 다음과 같습니다. 정렬되지 않은 무작위의 숫자가 리스트에 저장되어 있고 오름차순으로 정렬을 한다고 가정합니다.

 

예 : [ 3, 2, 4, 5, 1 ] ( 정렬 되지 않은 리스트)

 

먼저 맨 앞의 3과 3 뒤의 가장 작은 값을 탐색한다(최솟값 1). 3과 1(최솟값)의 위치를 바꿔준다.

결과 1. [ 1, 2, 4, 5, 3 ]

 

그다음 위치의 값 2와 2 뒤의 가장 작은 값을 탐색한다(최소값 2). 2가 최솟 값이므로 그대로 유지한다.

결과 2. [ 1, 2, 4, 5, 3 ]

 

그다음 위치의 값 4와 4 뒤의 가장 작은 값을 탐색한다(최솟값 3). 4와 3(최솟값)의 위치를 바꿔준다.

결과 3. [ 1, 2, 3, 5, 4 ]

 

그 다음 위치의 값 5와 5 뒤의 가장 작은 값을 탐색한다(최솟값 4). 5와 4(최솟값)의 위치를 바꿔준다.

결과 3. [ 1, 2, 3, 4, 5 ]

 

이전 포스팅에서 설명한 버블 정렬과 다르게 최솟값을 찾는 탐색 과정이 추가되었고 탐색과정을 한 사이클로 볼 수 있다. 전체 사이클을 다 돌면 전체 데이터가 오름차순으로 정렬된 것을 확인할 수 있습니다.

 

시간 복잡도 Big(O)

선택 정렬은 탐색과정에서의 반복과 선택 위치를 증가시키는 반복, 즉 두 가지 반복을 진행합니다.. 탐색과정에서 약 O(N)의 시간을 필요로 하며, 사이클이 반복하는데 약 O(N)의 시간을 필요로 합니다. 즉 전체 데이터를 정렬하는 데는 최대 O(N) * O(N) = O(N^2)의 시간 복잡도를 갖습니다. 시간 복잡도를 수식으로 나타내면 다음과 같습니다.

 

T(n)= (n-1) + (n-2) + ...... 2 + 1 = n(n-1)/2 = O(n^2)

 

영상으로 이해하기

이해가 안 가시는 분들을 위해 선택 정렬을 눈으로 쉽게 이해할 수 있는 영상을 첨부하였습니다. 영상을 보면서 데이터가 이동하는 흐름을 살펴보면 알고리즘을 이해하는데 도움이 될 것이라 생각합니다.

 

 

 

소스코드

#Python

 

def Selection_sort(li):
        min_index=0
        for i in range(len(li)):
            print(li)
            min_index=i
            for j in range(i+1, len(li)):
                if li[min_index]> li[j]:
                    min_index=j
            temp=li[min_index]
            li[min_index]=li[i]
            li[i]=temp
 
 
 
if __name__=="__main__":
    list_a=[ 10-i for i in range(10) ]
    Selection_sort(list_a)
    print(list_a)

 

중간중간 print()를 추가하여 데이터가 스왑(Swap)하는 과정을 눈으로 확인할 수 있도록 작성하였습니다.

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.