선택 정렬

선택 정렬 : 주어진 배열의 가장 큰 원소와 마지막 원소의 위치를 바꾼다. 정렬이 된 원소를 제외한 나머지 원소들로 같은 작업을 반복한다.

 

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 값을 기준으로 재귀의 중단점을 정한다. 방법은 위의 단순 정렬 함수와 마찬가지로 정렬되지 않은 원소 중에서 가장 큰 값을 찾아 마지막 원소와 위치를 바꿔준다.  

 

 

 이렇게 완성해놓고 보니까 재귀를 사용할 필요는 없을 거 같다! 괜히 한 번 해보겠다고 시간만 쓴 거 같고 머리만 아팠던 거 같다! 

 누가 작성을 하든 가장 쉽고 편하게 작성할 수 있는 장점이 있는 알고리즘 같다.