[알고리즘/Python] 선택정렬 | selection sort

선택정렬 [ selection sort ]

 

- 전체원소 중에 가장 작은 값을 가장 앞에 있는 원소와 바꾸고, 바꾼 원소를 제외하고 계속 가장 작은 값을 앞으로 보내는 정렬

패스	테이블	최솟값
0	[9, 1, 6, 8, 5, 4, 2, 0]	0
1	[0, 1, 6, 8, 5, 4, 2, 9]	1
3	[0, 1, 2, 8, 5, 4, 6, 9]	2
4	[0, 1, 2, 8, 5, 4, 6, 9]	4
5	[0, 1, 2, 4, 5, 8, 6, 9]	5
6	[0, 1, 2, 4, 5, 8, 6, 9]	6
7	[0, 1, 2, 4, 5, 6, 8, 9]	8

 

시간복잡도 ⏱

•     최선의 경우 : O(n²) 
•     최악의 경우 : O(n²) 
•     평균 : O(n²) 

장점

 

1. 구현이 쉬움2. 정렬을 위한 비교 횟수는 많지만 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야하는 자료상태에서는 효율적

 

단점

 

1. 항상 O(n²) 이라는 시간복잡도를 갖기 때문에 시간이 오래 걸리는 정렬 방식

 

[ python selection sort code | 파이썬 선택 정렬 코드 ]

data = list(map(int, input().split()))

def select_sort(data):
    
    for i in range(len(data)-1):
        tmp = i
        for j in range(i + 1,len(data)):
            if data[tmp] > data[j] : 
                tmp = j
       
        data[i],data[tmp] =  data[tmp],data[i]
        
select_sort(data)
print(data)

---

[ 합병정렬 | Merge Sort ]

[ 힙 정렬 | Heap Sort ]

[ 삽입정렬 | Insertion Sort ]

[ 퀵 정렬 | Quick Sort ]