[이코테 2021] 6. 선택 정렬

🔊본 포스팅은 '(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬' 유튜브 강의를 수강하고 정리한 글입니다.

정렬 알고리즘

• 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

  숫자가 하나씩 적힌 10장의 카드를 오름차순으로 정렬하자.
  

  컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다.

선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

선택 정렬 동작 예시

[Step 0] 처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꾼다.

[Step 1] 처리되지 않은 데이터 중 가장 작은 '1'을 선택해 가장 앞의 '5'와 바꾼다.

[Step 2] 처리되지 않은 데이터 중 가장 작은 '2'를 선택해 가장 앞의 '9'와 바꾼다.

[Step 3] 처리되지 않은 데이터 중 가장 작은 '3'을 선택해 가장 앞의 '7'과 바꾼다.

이러한 과정을 반복하면 다음과 같이 정렬이 완료된다.
→ 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.

선택 정렬 소스코드

array  [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
	min_index = i  # 가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
    	if array[min_index]>array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i]  # swap
print(array)

[실행 결과]

[0,1,2,3,4,5,6,7,8,9]

선택 정렬의 시간 복잡도

• 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
• 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.
  
• 이는 $(N^2+N+2)/2$로 표현할 수 있는데, 빅오 표현법에 따라서 $O(N^2)$이라고 작성한다.