python 정렬 알고리즘(선택/삽입/거품/합병)

#정렬 알고리즘

- selection sort(선택 정렬)

- insertion sort(삽입 정렬)

- bubble sort(거품 정렬)

- merge sort(합병 정렬)

사진 및 내용 출처 : 위키백과

* 문제가 될 시 바로 내리겠습니다.

#선택 정렬

- 제자리 정렬 알고리즘

① 주어진 리스트 중에 최솟값을 찾는다.

②그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).

③맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

     

선택 정렬 애니메이션

def selectionSort(x):
	length = len(x)
	for i in range(length-1):
	    indexMin = i
		for j in range(i+1, length):
			if x[indexMin] > x[j]:
				indexMin = j
		x[i], x[indexMin] = x[indexMin], x[i]
	return x

#삽입정렬

- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

- 배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.

- 선택 정렬이나 거품 정렬과 같은 같은 O(n²) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

삽입 정렬의 예

def insertSort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1]  = x[j]
			j = j - 1
		x[j+1] = key
	return x

#거품정렬

- 두 인접한 원소를 검사하여 정렬하는 방법

- 시간 복잡도가 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.

무작위 배열수의 거품 정렬 예

def bubbleSort(x):
	length = len(x)-1
	for i in range(length):
		for j in range(length-i):
			if x[j] > x[j+1]:
				x[j], x[j+1] = x[j+1], x[j]
	return x

#합병정렬

- 재귀의 아주 좋은 사례

- 분할 정복 기법

- 제자리 정렬이 가능

- 리스트를 반으로 쪼개면서 최소단위로 만든 후 정렬하면서 합병