[Python] 선택 정렬 알고리즘을 대체하는 제자리 정렬 구현 (in-place sort)

 

선택 정렬 알고리즘이란,

[5, 3, 8, 1, 2, 7]이라는

리스트가 존재한다면

 

 

왼쪽 리스트	오른쪽 리스트	설명
( )	(5, 3, 8, 1, 2, 7)	초기 상태
(1)	(5, 3, 8, 2, 7)	1 선택
(1, 2)	(5, 3, 8, 7)	2 선택
(1, 2, 3)	(5, 8, 7)	3 선택
(1, 2, 3, 5)	(8, 7)	5 선택
(1, 2, 3, 5, 7)	(8)	7 선택
(1, 2, 3, 5, 7, 8)	( )	8 선택

 

위 표와 같이

정렬되지 않은

오른쪽 리스트에서

가장 작은 숫자들을 찾아

왼쪽 리스트로 옮겨,

 

오른쪽 리스트가

공백이 될 때까지

반복하는 것이다.

 

하지만 위의 방법으로 구현하면

크기가 같은 리스트가

하나 더 있어야하므로

메모리를 요구한다.

 

 

그러므로

한 개의 리스트로

추가적인 공간을

필요로 하지 않는 정렬인

제자리 정렬을 구현해보자.

 

이 방법은

요소의 최소값을 구해

인덱스를 반복적으로 비교하며

자리 바꿈을 하는 원리이다.

 

 

 

def selectionSort(list):
    for i in range(len(list)):
        least = i
        leastValue = list[i]
 
        for j in range(i+1, len(list)):
            if list[j] < leastValue:
                least = j
                leastValue = list[j]
                
        temp = list[i]
        list[i] = list[least]
        list[least] = temp
 
list = [3, 4, 1, 5, 9, 8, 2, 6, 7]
selectionSort(list)
print(list)

 

 

  - 설명  

line 15에 

리스트가 선언되어 있다.

 

 

line 1부터 보자.

selectionSort 함수에서

리스트의 길이만큼

인덱스를 반복(i = 0부터)하며,

 

첫 번째 값(index = 0)이

최소값이라는 가정으로 시작한다.

 

 

line 6을 보자.

index 0과 1,

index 1과 2, .... 을

반복 비교하며 

자리를 바꿔주므로

j라는 index 변수도 필요하다.

이것은 i보다 1 더 크다.

 

list[i]가 더 작은 값이라고 가정했는데,

list[j]가 더 작다면

list[i]와 list[j]의 값을

순서를 바꿔줘야 한다.

least의 값은 j가,

leastValue의 값은 list[j]가 된다.

 

 

line 11-13을 보자.

list[i]의 값을

temp에 저장해두고,

list[j](list[least])의 값은

list[i]의 위치로,

저장해둔 temp의 값은

list[j]의 위치로 바꾼다.

 

 

 

  - 결과  

 

 

 

잘 이해가 가지 않는다면

파이썬 튜터를 활용하여

list[i], list[j],

least, leastValue, temp의 값과

리스트들의 값이 

변화하는 과정을

꼭 알아보면 좋겠다.