선택 정렬(selection sort)개념 및 구현 방법(python)

1. 정의

가장 작은 원소를 선택하여 알맞은 위치로 옮기는 알고리즘

2. 동작과정

사진을 예시로 설명하겠습니다.

 

위 정의에서 '가장 작은 원소'를 알맞은 위치로 옮기는 알고리즘이라고 명명했습니다.

알맞은 위치라는 것은 이 정렬의 목적이 오름차순 정렬인지, 내림차순 정렬인지에 따라서 달라지기 때문입니다

 

동작과정은 다음과 같습니다 :

 

a. 첫 번째 반복

첫 번째 반복에서는 배열을 순회하면서 가장 작은 값을 찾습니다. 배열의 순회가 끝난 이후, 첫 번째 원소와 가장 작은 원소의 값을 비교한 뒤, 자리를 바꿉니다

 

b. 두 번째 반복

가장 작은 원소는 배열의 첫 번째에 위치해있으니, 그 다음 위치부터 배열 순회를 시작합니다. 배열을 순회하다가 배열의 가장 작은 값인 3을 찾았고, 두 번째 위치에 있는 원소(5)와 가장 작은 원소인 (3)을 비교하여, 자리를 바꿉니다

 

위 과정이 반복되어 정렬이 완료됩니다

 

 

 

3. 장점 및 단점

선택 정렬은 어떤 단점이 존재할까요?

위 사진을 보면, 최솟값인 5를 찾았으니, 5를 제거해야합니다.

이때, 5의 오른쪽에 있던 값들이 <<(shift) 연산을 통해 한 칸씩 이동해야하며(비효율 발생)

최솟값을 넣는 과정에도 동일한 연산을 수행합니다.

5를 넣는 과정에서 (배열의 길이 - 1) 만큼 shift 연산이 진행됩니다.(비효율 발생)

 

 

 

4. 시간 복잡도

버블 정렬과 비슷하게 시간복잡도는 O(n²)이 소요됩니다 그러나, Best Case에서 O(n)이 소요된다는 장점이 존재한다

• Worst : O(n²)
• Average : O(n²)
• Best : O(n)

 

 

 

5. 구현

위에서 선택정렬은 불필요한 shift 연산이 일어나기 때문에 불필요한 연산을 만들어낸다고 설명하였습니다.

그러나 아래와 같이 코드를 구현(swap 사용)한다면, 불필요한 shift 연산을 사용하지 않아도 됩니다

def selection_sort(ls):
    n = len(ls)
    for i in range(n - 1):
        min = i
        for j in range(n - i - 1):
            if ls[j] < ls[min]:
                min = j
        ls[i], ls[min] = ls[min], ls[i]

 

 

1. list를 인자로 받아, 길이를 구한 값을 n에 할당합니다

 

2. 반복문 시행 시, 최솟값을 현재 값으로 지정합니다

 

3. 이후, 최솟값을 찾는 과정을 진행합니다. 최솟값을 찾는 과정에서 현재의 최솟값 보다 방금 탐색한 값이 더 작다면 최솟값과 방금 탐색한 값을 변경합니다