[Algorithm] 선택 정렬은 뭐야?

선택 정렬이란 정렬되지 않은 정보들 중에서 가장 작은 값을 정렬되지 않은 순서 중 가장 앞에 있는 정보와 바꾸는 정렬 방식을 말한다. 선택 정렬은 입력받은 모든 정보를 모두 확인한다는 점에서 가장 원시적인 방법으로 그만큼 연산의 수가 많은 알고리즘이다.

 

다음은 1부터 5까지의 숫자를 무작위로 배치한 정보를 선택 정렬을 이용하여 정렬하는 방식이다.

 

선택 정렬 순서 1번째

무작위로 배치된 숫자들을 나타낸 것이다. 여기서 1은 정렬되지 않은 숫자들 중에서 가장 작은 숫자이면서 가장 앞에 있으므로 정렬할 필요 없이 가만히 있는다. (밑에서부터 정렬된 숫자들은 배경을 파란색으로 바꾸도록 하겠다.)

 

선택 정렬 순서 2번째

1은 이미 정렬이 되었고, 다음 순서에서는 나머지 숫자 5,3,2,4 중에 가장 작은 숫자를 찾고, 그 값을 정렬되지 않은 가장 앞의 순서와 정보를 바꿔준다. 위의 그림에서는 5와 2의 순서를 바꿔주면 되는 것이다.

 

선택 정렬 순서 3번째

위의 과정을 반복하면 남은 수 중에 가장 작은 값은 3이고, 3의 위치가 가장 앞이므로 별도의 과정 없이 3이 정렬된다.

 

선택 정렬 순서 4번째

위의 과정을 반복하면 남은 수 중에 가장 작은 값은 4이고, 5의 위치가 맨 앞이므로 4와 5를 바꿔준다.

 

선택 정렬 순서 5번째

위의 과정을 반복하면 남은 수 중에 가장 작은 값은 5이고, 5의 위치가 맨 앞이므로 별도의 과정 없이 5가 정렬된다.

 

선택 정렬 순서 6번째

이렇게 선택 정렬의 알고리즘 작동 순서에 대해서 알아보았다. 선택 정렬 과정에서 알 수 있듯이 모든 배열들을 하나하나 확인하여 정렬하는 방식으로 시간 복잡도는 O(N^2)입니다. 즉, 정보의 계수가 100개라면 연산의 숫자는 대략 10,000번을 해야 한다는 것입니다.

 

다음은 선택 정렬 알고리즘을 코드로 표현한 것입니다.

 

array = [1,5,3,2,4]
 
for i in range(len(array)):
  minIndex = i;
  for j in range(i+1, len(array)):
    if array[minIndex] > array[j]:
      minIndex = j
  array[i], array[minIndex] = array[minIndex], array[i]
 
print(array)

 

위의 코드에서 minIndex는 가장 작은 정보의 인덱스를 말한다.

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬