선택 정렬(Selection Sort), 셀렉션 알고리즘

이번 포스팅에서 다룰 주제인 선택 정렬(Selection Sort)은 최솟값을 선택하여 위치를 교환하여 정렬하는 방법으로 셀렉션 알고리즘을 적용한 방식입니다. 선택 정렬 예제, 시간 복잡도, 장단점, 셀렉션 알고리즘, 선택 정렬 알고리즘 파이썬 구현에 대해 알아보겠습니다.

 

선택 정렬이란? (Selection Sort)

가장 작은 값의 원소부터 차례로 선택하여 위치를 교환하여 정렬하는 방법입니다.

셀렉션 알고리즘을 전체 자료에 적용한 것입니다.

 

셀렉션 알고리즘이란? (Selection Algorithm)

자료들 중 k번째로 크거나 작은 원소를 찾는 방법으로 최솟값, 최댓값, 중간값 등을 찾을 때 사용하기도 합니다.

정렬 알고리즘을 이용하여 자료를 정렬하고, 원하는 순서에 있는 원소를 가져오는 과정을 거칩니다.

 

ex) k번째로 작은 원소를 찾는 알고리즘

• 1번부터 k번째까지 작은 원소들을 찾아 List의 앞쪽으로 이동시키고, List의 k번째를 반환합니다.
• k가 비교적 작을 때 유용하며 O(kn)의 수행 시간을 필요로 합니다.
• k번째로 큰 원소를 찾으려면 5번 줄 코드를 if list [minIndex] < list [j]로 부등호만 바꾸면 됩니다.

def selection(list, k):
    for i in range(k):
        minIndex = i
        for j in range(i + 1, len(list)):
            if list[minIndex] > list[j]:
                minIndex = j
        list[i], list[minIndex] = list[minIndex], list[i]
    return list[k - 1]

a = [12, 68, 23, 90, 52, 76, 49]
print(selection(a, 3))

선택 정렬 과정

1. 주어진 List 중에서 최솟값을 찾습니다.
2. 최솟값을 맨 앞에 위치한 값과 교환합니다.
3. 맨 처음 위치를 제외한 나머지 List를 대상으로 위의 과정을 반복합니다.

한 단계가 끝나면 가장 작은 원소가 맨 앞자리로 정렬됩니다.

 

최솟값, 변경 대상, 정렬된 원소

 

[2, 3, 4, 1] -> [1, 3, 4, 2]

[1, 3, 4, 2] -> [1, 2, 4, 3]

[1, 2, 4, 3] -> [1, 2, 3, 4]

 

시간 복잡도와 장단점

• 평균 수행 시간: O(n²)
• 최악 수행 시간: O(n²)
• 알고리즘 기법: 비교와 교환
• 장점: 코드 구현이 쉽고, 교환의 횟수가 버블 정렬, 삽입 정렬보다 적다.
• 단점: 속도가 상당히 느리다

선택 정렬 알고리즘 코드

• 리스트에서 최솟값을 찾고 미 정렬된 리스트의 맨 앞자리와 위치를 바꾸어 정렬합니다.
• 아래 코드는 오름차순 정렬 알고리즘입니다.
• 선택 정렬 내림차순은 6번 줄 코드를 if list [min] < list [j]로 부등호만 바꾸면 됩니다.

def selection_sort(list):
    for i in range(len(list) - 1):
        min = i
        # 최솟값 찾기
        for j in range(i + 1, len(list)):
            if list[min] > list[j]:
                min = j
        list[i], list[min] = list[min], list[i]

a = [12, 68, 23, 90, 52, 76, 49]
selection_sort(a)
print(a)

 

선택 정렬 예제

[Python] SW Expert Academy - 4843. 특별한 정렬

[Python] SW Expert Academy - 4843. 특별한 정렬

---

다른 정렬 공부하기 >>

버블 정렬 알고리즘 (Bubble Sort)

버블 정렬 알고리즘 (Bubble Sort)

카운팅 정렬 알고리즘 (Counting Sort / 계수 정렬)

카운팅 정렬 알고리즘 (Counting Sort / 계수 정렬)

---

선택 정렬 파이썬으로 구현해보고, 선택 정렬 장단점, 개념, 과정, 시간 복잡도, 셀렉션 알고리즘 python 구현과 선택 정렬 예제를 알아보았습니다.