정렬 알고리즘 기본 (버블, 선택, 삽입정렬)

버블 정렬

인접한 두 개를 비교해서, 교환한다.

a= [-2, 45, 0, 11, -9]

for step in range(len(a)-1): #...(1)
	for i in range(len(a)-1-step): #...(2)
    	if a[i] > a[i+1]:
        	a[i],a[i+1] = a[i+1],a[i] #...(3)

시간 복잡도 (원소개수: n)
(1) for 루프 n-1 번 반복
(2) for 루프 n-1,n-2, ..., 2, 1번 반복
(3) 교환은 상수 시간 작업
=> T(n) = O(n^2)

 

한 번 회전했을 때, 요소들 중 가장 큰 값이 맨 뒤로 밀려나는 결과가 나온다.

따라서 두번째 회전에서는 맨 뒤 요소를 제외하고 정렬을 수행하면 된다.

이와 같은 원리로 세번째 회전에서는 맨 뒤-1, 맨 뒤요소를 제외하고 정렬을 수행한다.

초기: [-2, 45, 0, 11, -9]
1회전 시 (step=0): [-2,0,11,-9,45]
2회전 시 (step=1): [-2,0,-9,11,45]
3회전 시 (step=2): [-2,-9,0,11,45]
4회전 시 (step=3): [-9,-2,0,11,45]
=> 정렬 완료

 

 

선택 정렬

처리되지 않은 데이터 중 가장 작은 데이터를 선택하여, 맨 앞 데이터와 바꿈

a = [5,3,8,1,2]

for i in range(len(a)-1): #최솟값은 맨 앞에 위치해야하므로, 0부터 시작    ...(1)
	min_idx = i
    for j in range(i+1, len(a)):  #...(2)
    	if a[j]<a[min_idx):
        	min_idx = j #최솟값의 인덱스가 min_idx에 담기도록 함
	a[i],a[min_idx] = a[min_idx], a[i] #값 Swapping ...(3)

 

시간복잡도
(1) for 루프 n-1번 반복
(2) 가장 작은 값을 찾기 위한 비교 횟수 n-1, n-2, ... ,2,1
(3) 교환은 상수시간 작업
=> T(n) = O(n^2)

 

인덱스 0부터 len(a)-1까지 탐색한다.

매 탐색마다, 남은 것 중 가장 작은 값을 앞으로 가져온다.

초기: [5,3,8,1,2]
1회전 시(i=0): [1,3,8,5,2]
2회전 시(i=1): [1,2,8,5,3]
3회전 시(i=2): [1,2,3,5,8]
=> 정렬 완료

 

 

 

삽입 정렬

카드를 정리하듯, 적절한 위치에 데이터를 삽입하는 알고리즘이다.

첫번째 데이터는 그 자체로 정렬이 되어 있다고 판단하고, 두번째 데이터부터 어떤 위치로 들어가야할지 판단한다. (첫번째 데이터의 왼쪽 또는 오른쪽으로)

이어 세번째 데이터를 두번째 데이터 왼쪽 or 오른쪽 / 첫번째 데이터 왼쪽 or 오른쪽 중 어느 위치로 들어가야할지 판단한다.

a = [5,3,8,1,2]

for i in range(1, len(a): #...(1)
	key = a[i] #두번째 원소부터 시작
    j = i - 1 #왼쪽(정렬된 부분)의 마지막부터 시작
    while j >= 0 and a[j] > key: #key보다 큰 값이 있으면   ....(2)
    	a[j+1] = a[j] #그 값을 오른쪽으로 한 칸 밀고
        j -= 1 #왼쪽 값도 확인 => 왼쪽으로 한 칸씩 이동하면서, key보다 큰 값을 계속 오른쪽으로 밀어내게 됨
    a[j+1] = key #a[j]<=key이므로, key보다 작은 요소(a[j]) 뒤(->빈 자리)에 key값 삽입

 

시간 복잡도
(1) for 루프는 n-1번 반복
(2) 삽입은 최악의 경우(=모든 데이터가 정렬되어있지 않은 경우) i-1번비교
=> T(n) = O(n^2)
최선의 경우(=모든 데이터가 정렬된 경우), 비교 연산 이루어지지 않음
=> T(n) = O(n)

 

while 문이 멈추는 경우:

1. j < 0 -> 맨 앞까지 다 밀었음(key가 가장 작은 값)

2. a[j] <= key -> key보다 작거나 같은 값을 만남 (그 오른쪽에 삽입)

 

key라는 새로운 변수를 만들어 a[i] 값을 저장하는 이유는, 값을 뒤로 밀고 있기 때문에 어딘가에 해당 값을 저장해야하기 때문이다.

 

*새 변수 저장안하고, swaping으로 구현하는 방법

for i in range(1, len(a)):
	for j in range(i, 0, -1) : #j:삽입하고자 하는 원소(key)의 위치
		if a[j] < a[j-1]: #한 칸씩 왼쪽으로 이동
        	a[j], a[j-1] = a[j-1],a[j]
        else: #자기보다 작거나 같은 데이터를 만나면 그 위치에서 멈춤
        	break;

 

시간복잡도는 동일하다.

 

초기: [5,3,8,1,2]
i=1 : key=3 -> [3,5,8,1,2]
i=2 : key=8 -> [3,5,8,1,2]
i=3 : key=1 -> [1,3,5,8,2]
i=4 : key=2 -> [1,2,3,5,8]

---

참고 자료

 

https://www.programiz.com/dsa/

Insertion Sort (With Code in Python/C++/Java/C)

 

https://www.youtube.com/watch?v=KGyK-pNvWos&t=5s

 

https://youtu.be/0dG7xTt5IfQ