[알고리즘] 선택정렬 (w/파이썬)

---

개념

 

이름 그대로, 

배열 내 최솟값을 '선택'해서 맨 앞 인덱스와 교환하는 방법이다.

첫 인덱스가 최솟값으로 변경 되면, 그 다음 인덱스부터 시작하는 배열로 최솟값을 찾아

그 다음 인덱스를 최솟값으로 변경한다.

 

아래의 배열을 선택정렬로 정렬해보자.

 

 

1. 0번 인덱스부터 4번 인덱스중 최솟값인 2번 인덱스와 0번 인덱스 자리를 바꾼다.

 

2. 0번 인덱스가 이미 최솟값이 됐으니, 1번 인덱스부터 4번 인덱스 중 최솟값인 1번 인덱스를 그냥 놔둔다.

 

3. 2번 인덱스부터 4번 인덱스 중 최솟값인 4번 인덱스를 2번 인덱스와 교환한다.

 

 

원래같으면 3번 인덱스와 4번인덱스 사이의 숫자를 확인하겠지만,

이미 정렬이 완료 됐으니 그만 한다.

 

---

구현

 

비교 대상을 설정해야 한다.

비교 대상과 루프를 돌렸을 때 나오는 숫자를 비교했을 때,

더 작은 수를 비교 대상에 대입 후

마지막까지 루프를 돌린 후 작은 수가 담긴 비교 대상을 제일 앞 인덱스로 만든다.

 

lists = [8, 3, 2, 7, 6]

for i in range(len(lists) - 1):
    min = i
    for j in range(i, len(lists)):
        if lists[j] < lists[min]:
            min = j
    lists[i], lists[min] = lists[min], lists[i]
print(lists)

---

시간복잡도

 

이중 for문이기 때문에 O(n^2) 이다.