선택 정렬

 

정렬(sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것

일반적으로 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다.

---

 

선택 정렬

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

매번 가장 작은 것을 선택한다는 의미에서 '선택'정렬 알고리즘이라고 한다.

 

 

 

 

선택 정렬 예시

 

 

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

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스. 맨 처음 시작은 0번째 인덱스로
 
    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]

 

 

• 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다
• 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다
  • N + (N-1) + (N-2) + ... + 2
  • 가장 마지막 원소는 정렬을 수행해주지 않아도 되기 때문에 2
• 이는 (N^2 + N -2) /2 로 표현할 수 있는데, 빅오 표기법에 따라 O(N^2)로 나타낸