정렬 알고리즘은 목록의 요소를 특정 순서대로 넣는 알고리즘이다. 대게 숫자식 순서와 사전식 순서로 정렬한다.

정렬은 알고리즘의 꽃이다. 정렬 알고리즘을 구성하는 논리는 다른 코딩을 하는 데도 많은 도움이 된다.

버블 정렬(Bubble Sort)

배열의 처음부터 끝까지 살펴보며 아이템 2개의 순서가 잘못되어 있는 것을 발견하면, 두 아이템을 맞바꾼다.

배열 전체를 쭉 살펴보는 것을 n번 하기 때문에 시간 복잡도는 O(n^2) 이다.

매우 비효율적이고 가장 느린 정렬 알고리즘.

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

병합 정렬(Merge Sort)

폰 노이만이 고안한 알고리즘으로, 분할 정복하는 방식으로 구성.

시간 복잡도가 최선과 최악 모두 O(n logn) 으로, 안정 정렬(Stable Sort) 이다.

배열을 두 부분으로 분할하여 더 이상 쪼갤 수 없을 때까지 분할 → 분할이 끝나면 정복(정렬)시작

퀵소트(Quick Sort)

피벗을 기준으로 좌우를 나누는 특징 때문에 파티션 교환 정렬이라고도 불리운다.