[정렬 알고리즘 정리, python] 선택 정렬, 거품 정렬, 삽입 정렬

선택 정렬이란? O(n^2)

: 선택 정렬은 여러개의 데이터가 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고

그 다음 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 과정을 반복해 전체 데이터를 정렬하는 알고리즘이다. 

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

 

1) 6 2 8 4

2) 2 6 8 4

3) 2 4 8 6

4) 2 4 6 8

 

array = [6,2,8,4]

for i in range(len(array)):
	minIndex = i
    for j in range(len(array)):
    	if array[minIndex] > array[j]:
        	minIndex = j
    array[i], array[minIndex] = array[minIndex], array[i] # 스와프 (두 변수 위치 변경)

 

* 선택정렬 장단점

장점: 구현이 쉽다. 비교횟수는 많지만 실제로 교환하는 횟수는 적어, 많은 교환이 일어나야하는 자료상태에서 효율적이다.

단점: 버블정렬과 시간복잡도는 같아 느리지만, 실제로 시간을 측정하면 버블정렬보다 조금 더 빠르다.

 

거품 정렬이란? O(N^2)

 

거품 정렬은 뒤에서부터 앞으로 정렬을 진행하는 구조이다.

오름차순 정렬 기준으로 배열의 맨 뒷공간에 가장 높은 값을 보내고, 그 앞에 두번째로 큰 값을 보낸다.

이를 위하여 배열 내 값들을 앞뒤로 서로 비교하며 자리를 바꾸는 작업을 반복한다.

작은 값을 앞으로 가져오겠다는 개념을 반대로 이용해 큰 값을 뒤로 보내며, 

원소들끼리 위치를 변경하는 모습이 물방울이 이동하는 것 같아서 버블 정렬으로 명명 되었다.

 

1) 5 3 4 1 2

2) 3 4 1 2 5

3) 3 1 2 4 5

4) 1 2 3 4 5

 

- 버블 정렬은 큰 값들을 뒤에서 앞으로 하나씩 쌓아가기 때문에 원소가 자리잡을 때마다 정렬의 범위가 하나씩 줄어든다.

- 선택정렬과는 정 반대 정렬 방향이다.

- 다른 정렬에 비해 스왑이 빈번하다.

 

for i in range(len(arr)-1,0,-1):
	for j in range(len(i)):
    	   if arr[j] > arr[j+1]:
        	  arr[j], arr[j+1] = arr[j+1], arr[j]

 

* 거품 정렬 장단점

장점: 구현이 쉽고 코드가 직관적이다.

단점: 비효율적이다. 최악/최선 상관 없이 O(N^2)이기때문에 효율적이지 않다.

 

삽입 정렬이란?

 

삽입정렬이란 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤, 그 위치에 삽입되는 정렬로

그 앞까지의 데이터는 이미 정렬되어있다고 가정한다. 그래서 첫번째 데이터는 그 자체로 정렬되어있다 판단하고

두번째 데이터부터 정렬을 시작한다. 특정 데이터를 적절한 위치에 '삽입'한다고 해서 삽입 정렬이라 부른다.

 

1) 6 2 8 4

2) 2 6 8 4 

3) 2 6 8 4

4) 2 4 6 8

 

array = [6, 2, 8 4]

for i in range(len(array)):
	for j in range(i, 0 , -1):
		if array[j] < array[j-1]:
        		array[j], array[j-1] = array[j-1], array[j]
        	else:
        		break

 

*삽입정렬 장단점

장점: 최선의 경우 O(N) > 빠름, 성능이 좋음

단점: 최악의 경우 O(N^2), 데이터에 따라 성능의 편차가 심함