Sorting algorithm(정렬 알고리즘) 1탄 - Selection sort(선택 정렬)

 

💗 Sorting algorithm (정렬 알고리즘) :  데이터 등을 일정 순서대로 정렬, 나열하는 알고리즘. 💗

 

 

정렬 알고리즘 종류
1. Selection sort (선택 정렬)
2. Insertion sort (삽입 정렬)
3. Merge sort (합병 정렬)
4. Bubble sort (거품 정렬, 버블 정렬)

 

 

1. Selection sort  (선택 정렬 알고리즘)

- 가장 작은 수와 가장 왼쪽에 있는 수를 swap.

→ 가장 작은 수를 제외한 나머지 수들 중 최소 값과 가장 왼쪽에 있는 수를 swap.

→ 이런 식으로 계속 반복.

 

 

최소값: 5

가장 왼쪽 값: 70

5 ↔ 70

 

 

5는 정렬 완료.

정렬되지 않은 값들 중 최소값: 60

정렬되지 않은 값들 중 가장 왼쪽 값: 100

60 ↔ 100

 

 

동일한 방식으로... 100 ↔ 70

 

 

정렬 완료!!!

 

 

 

 

# 최소값을 구하는 내장함수(min) 사용한 버전.
from typing import List
def selection(L: List) -> List:
    for i in range(len(L)-1):
        a = i + L[i:].index(min(L[i:]))
        L[i], L[a] = L[a], L[i]
        print(L)
    return L

selection([5,20,7, 100,100,7])   # 답: [5, 7, 7, 20, 100, 100]

 

 

# 최소값 구하는 함수까지 구현한 버전
from typing import List
def selection2(L: List) -> List:
    for i in range(len(L)):
        minIndex = i
        for z in range(i+1, len(L)):
            if (L[z] < L[minIndex]):
                minIndex = z
                
        L[i], L[minIndex] = L[minIndex], L[i]
        print(L)
    return L


selection2([500, 20, 7, 100, 100, 17, 34, 17])
# 답: [7, 17, 17, 20, 34, 100, 100, 500]