모두의 알고리즘 문제08. 선택 정렬 연습문제

연습문제 풀기 전에 이전에 못한 선택정렬의 빅오 표기법에 대해 알아보자. 선택정렬의 비교 방법은 리스트 안의 자료를 한번씩 비교하는 방법과 거의 같다. 문제03의 동명이인 찾기와 비슷한 경우다.

 

0번째 위치는 자신을 제외한 전 위치와 비교하니 n-1번 비교, 1번째는 n-2번 비교. 이런식으로 쭉 가다가 n-2번째의 n-1번째와 1번 비교하게 되고, n-1번째는 비교할 대상이 없으니 0번 비교하게 된다. 정리하자면 이렇게 되는데

 

위치	비교횟수
0	3
1	2
2	1
3	0

 

이는 1부터 마지막 수까지 전부 더하는 것과 같기 때문에 n(n-1)/2 공식을 쓸 수 있다. 즉 빅 오 표기법으로 선택정렬은 O(n^2)라고 나타낸다.

 

O(n^2)인 알고리즘이므로 입력 크기가 커질수록 정렬하는 시간이 굉장히 오래 걸리게 된다.

 

 

 

 

 

8-1 일반적인 선택 정렬 알고리즘을 사용해서 리스트 [2, 4, 5, 1, 3]을 정렬하는 과정을 적으라.

 

오름차순으로 정렬한다고 가정한다.

 

1. 리스트 0번째 자리의 원소를 제일 작은 원소a라고 가정한다.

 

2. a와, 리스트 1번부터 마지막까지의 원소를 비교하여 a보다 작은 원소들 중 가장 작은 원소를 a의 자리와 교체한다.

 

3. 리스트 1번과, 리스트 2번부터 마지막까지의 원소를 비교하여 1번보다 작은 원소들 중 가장 작은 원소와 1번의 자리를 교체한다.

 

4. 리스트 2번과, 리스트 3번을 비교하여 가장 작은 원소와 리스트 2번의 자리를 교체한다.

 

5. 리스트 3번과 리스트 4번을 비교하여 작은 원소를 3번에 위치시킨다.

 

6. 리스트4번은 마지막 자리이므로 비교할 필요가 없다. 정렬 끝.

 

 

 

8-2 이론파트에서 오름차순으로 정렬하던 것과 달리 내림차순으로 알고리즘을 고쳐라.

 

def sel_sort(a):
    n=len(a)
    for i in range(0, n-1):
        max_idx=i
        for j in range(i+1, n):
            if a[j] > a[max_idx]:
                max_idx = j
                a[i], a[max_idx]= a[max_idx], a[i]


d = [2, 4, 5, 1, 3]

sel_sort(d)
print(d)

결과: [5, 3, 4, 2, 1]

 

이것도 파이참에서 오류가 났다. 컴퓨터 문제인거 같기도 한데 일단 알아봐야겠다. 코드를 아래와 같이 고쳤다.

 

def sel_sort(a):
    n=len(a)
    for i in range(0, n-1):
        max_idx=i
        for j in range(i+1, n):
            if a[j] > a[max_idx]:
                a[i], a[j]= a[j], a[i]


d = [2, 4, 5, 1, 3]

sel_sort(d)
print(d)

이러면 결과는 [5, 4, 3, 2, 1]로 잘 나온다