[Algorithm] 5-(1) 정렬 - 선택 정렬, 삽입 정렬

[Algorithm] 5-(1) 정렬 - 선택 정렬, 삽입 정렬

 

 

1. 선택 정렬

 

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

 

 

1) 구현 방법

 

이중 반복문을 통해 선택 정렬을 구현할 수 있다.

 

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] #스와프

 

2) 선택 정렬의 시간 복잡도

(n^2 + n - 2) / 2
= O(N^2)

 

 

 

2. 삽입 정렬

 

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 ‘삽입’한다. 구현 난이도가 높은 편이나, 선택정렬보다 효율적이다.

 

1) 구현 방법

 

7 5 9 0 3 1 6 2 4 8

 

첫번째 원소가 정렬되어 있다고 판단한다.

두번째 원소가 첫번째 원소보다 작으면 왼쪽 위치에 들어가게 하고, 크면 오른쪽에 둔다.

n번째 원소가 그 전보다 작은지를 판단하면서 정위치에 배치하게 한다.

 

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

for i in range(1, len(array)):
	for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
		if array[j] > array[j-1]:
			array[j], array[j - 1] = array[j - 1], array[j] #스와프
		else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
			break

 

2) 삽입 정렬의 시간 복잡도

 

= O(n^2)

 

그러나 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

최선의 경우 O(n) 시간 복잡도를 가진다.

ex. 0 1 2 3 4 5 6 7 8 9 일 경우.