선택 정렬 : 주어진 배열의 가장 큰 원소와 마지막 원소의 위치를 바꾼다. 정렬이 된 원소를 제외한 나머지 원소들로 같은 작업을 반복한다.
selection_sort(A[], n) #A[1~n]
{
for last ← n downto 2 {
A[1...last] 중 가장 큰 원소 A[k]를 찾는다;
A[k] ↔ A[last];
}
}
알고리즘 실행을 위한 랜덤 배열 생성
import random
sample_list= random.sample(range(1000),100)
print(sample_list)
배열에서 가장 큰 원소를 찾는 함수
def largest(list, last):
largest=0
for i in range(1, last):
if list[i] > list[largest]:
largest = i
return largest
선택 정렬 함수
def selection_sort(a, n):
for i in range(n, 0, -1):
k = largest(a, i)
a[k], a[i-1] = a[i-1], a[k]
배열 a의 길이 n부터 시작하여 1씩 감소하면서 반복문을 돌린다. i번까지의 a배열에서 가장 큰 원소의 인덱스 값 largest를 받아 k에 넣어준 후, 정렬되지 않은 a배열의 가장 마지막 원소와 k번째의 원소의 위치를 바꿔준다.
재귀 호출을 사용한 선택 정렬 함수
def selection_sort_re(list, flag = 0):
if flag == 99:
return
max=largest(list, len(list) - flag)
sample_list[len(list)-1-flag], sample_list[max] = sample_list[max], sample_list[len(list)-1-flag]
flag+=1
selection_sort_re(list, flag)
if __name__ == "__main__":
selection_sort_re(sample_list)
flag 값을 기준으로 재귀의 중단점을 정한다. 방법은 위의 단순 정렬 함수와 마찬가지로 정렬되지 않은 원소 중에서 가장 큰 값을 찾아 마지막 원소와 위치를 바꿔준다.
이렇게 완성해놓고 보니까 재귀를 사용할 필요는 없을 거 같다! 괜히 한 번 해보겠다고 시간만 쓴 거 같고 머리만 아팠던 거 같다!
누가 작성을 하든 가장 쉽고 편하게 작성할 수 있는 장점이 있는 알고리즘 같다.