[Algorithm] 21강 : 선택 정렬의 정의와 구현코드

정렬 알고리즘

 

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

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

 

 

 

선택 정렬

 

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

위와 같은 방식으로 첫 번째 인덱스, 두 번째 인덱스,....으로 계속해서 데이터와 바꾸는 것을 반복하여 정렬한다.

 

 

선택 정렬 구현

 

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] # 스와프
    
print(array)
=> [01,2,3,4,5,6,7,8,9]

 

 

 

선택 정렬의 시간 복잡도

 

 

선택 정렬은 N번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

빅오 표기법에 따라서 O(N 2(제곱)) 이라고 작성한다.

 

 

---

www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.