[CS] 선택 정렬

 

 

 

 

선택 정렬

 

 

선택정렬은 말 그대로 선택해서 정렬한다는 것입니다.

 

예를 들면, 초등학교 키번호르를 생각해보시면 됩니다.

 

학생들을 줄을 세우고 한번 쭉 둘러보며 키가 가장 작은 학생을 찾습니다.

 

가장 키가 작은 학생을 찾아 맨 앞으로 세우고 다시 줄을 쭉 둘러봅니다.

 

두 번째로 키가 작은 학생을 찾아 두 번째에 세우고 줄을 다시 둘러보며 세번째로 작은 학생을 찾습니다.

 

이러한 반복으로 정렬하는 방식이 선택정렬입니다.

 

선택정렬의 진행

 

 

선택 정렬의 진행순서를 좀 더 자세히 살펴보겠습니다.

 

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4와 6과 2와 9와 1을 차례차례 비교합니다.
	      그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
       [1, 6, 2, 9, 4] 이렇게요!

자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.

2단계 : [1, 6, 2, 9, 4]
           6과 2와 9와 4를 차례차례 비교합니다.
           그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다!
       [1, 2, 6, 9, 4] 이렇게요!

3단계 : [1, 2, 6, 9, 4]
              6과 9와 4를 차례차례 비교합니다.
              그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다!
       [1, 2, 4, 9, 6] 이렇게요!

4단계 : [1, 2, 4, 9, 6]
                 9와 6을 비교합니다!
                 그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다!
       [1, 2, 4, 6, 9] 이렇게요!


자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?
버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만,
실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용해야 합니다!

 

 

 

구현

 

def selectionsort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
        minimun = iter
        for cur in range(iter + 1, len(lst)):
            if lst[cur] < lst[minimun]:
                minimun = cur

        if minimun != iter:
            lst[minimun], lst[iter] = lst[iter], lst[minimun]

    return lst

 

 

배열의 길이가 같다는 조건하에 버블정렬과 선택정렬의 탐색횟수는 동일합니다.

 

제일 앞에있는 요소가 가장 작은 요소라고 가정을 하고, (minimun) 두 번째 요소부터 마지막 요소까지 minimun과 비교합니다.

 

minimun보다 더 작은 요소가 있다면 minimun을 그 값으로 바꿉니다.

 

이후 iter와 minimun이 같지않다면 서로의 자리를 바꿉니다.