이코테 강의 정리 - 정렬 알고리즘

정렬 알고리즘

• 정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

정렬 알고리즘으로 데이터를 정렬하면 이진탐색이 가능해진다.

선택 정렬(Selection Sort)

→ 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

# 선택 정렬 
arr = [7, 8, 0, 5, 9, 3, 2, 4, 1, 6]

for i in range(len(arr)): 
	min_index = i # 가장 작은 원소의 인덱스 
	for j in range(i + 1, len(arr)): 
		if arr[min_index] > arr[j]: 
			min_index = j 
	arr[i], arr[min_index] = arr[min_index], arr[i] # 스와프 

print(arr) 

💡 스와프(Swap)란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 의미한다.

• 선택정렬의 시간 복잡도 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. $O(N^2)$
  

삽입정렬(Insertion Sort)

→ 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

선택정렬에 비해 구현 난이도가 높지만 실행시간 측면에서 더 효율적이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 더 효율적이다.

삽입 정렬은 첫 번째 데이터는ㄴ 그 자체로 정렬되어 있다고 판단하므로 두 번째 데이터부터 시작한다.

삽입 정렬은 정렬이 이루어진 원소는 항상 정렬된 상태라는 특징이 있다.

# 삽입 정렬 

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

for i in range(1, len(arr)): 
	for j in range(i, 0, -1): #(start, end, step) 
		if arr[j] < arr[j -1]: # 한 칸씩 왼쪽으로 이동 
			arr[j], arr[j -1] = arr[j -1], arr[j] 
		else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤 
			break

• 삽입 정렬의 시간 복잡도 $O(N^2)$ 선택정렬과 마찬가지로 $O(N^2)$ 이지만 리스트가 거의 정렬되어 있는 상태에서는 매우 빠르게 동작하고 최선의 경우 $O(N)$의 시간 복잡도를 가진다.
  

퀵 정렬(Quick Sort)

→ 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이며 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)으로 설정한다.

# 퀵 정렬 

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

def quick_sort(arr, start, end): 
	if start >= end: # 원소가 1개인 경우 종료 
		return 
	pivot = start
	left = start + 1
	right = end
	while left <= right: 
		# 피벗보다 큰 데이터를 찾을 때까지 반복 
		while left <= end and arr[left] <= arr[pivot]: 
			left += 1 
		# 피벗보다 작은 데이터를 찾을 때까지 반복 
		while right > start and arr[right] >= arr[pivot]: 
			right -= 1 
		if left > tight: # 엇갈렸다면 작은 데이터와 피벗을 교체 
			arr[left], arr[pivot] = arr[pivot], arr[right] 
		else: #엇갈라지 않았다면 작은 데이터와 큰 데이터를 교체 
			arr[right], arr[left] = arr[left], arr[right] 
	# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행 
	quick_sort(arr, start, right -1) 
	quick_sort(arr, right + 1, end) 

quick_sort(arr, 0, len(arr)-1) 

• 파이썬의 장점을 살린 퀵 정렬

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

def quick_sort(arr): 
	# 리스트가 하나 이하의 원소만을 담고 있다면 종료 
	if len(arr) <= 1: 
	return arr 
	
	picot = arr[0]
	tail = arr[1:]
	left_sid = [x for x in tail if x <= pivot]
	right_side = [x for x in tail if x > pivot]

	return quick_sort(left_side) + [pivot] + qick_sort(right_side) 

• 퀵 정렬의 시간 복잡도 퀵정렬의 평균 시간 복잡도는 $O(NlogN)$이다. 단 최악의 경우 $O(N^2)$게
  

계수 정렬(Count Sort)

→ 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘으로 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.

# 모든 원소의 값이 0보다 크거나 같다고 가정
arr = [7, 8, 0, 5, 9, 3, 2, 4, 1, 6]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화) 
count = [0] * (max(arr) + 1) 

for i in range(len(arr)): 
	count[arr[i]] ++ 1 # 각 데이터에 해당하는 인덱스의 값 증가 

for i in rnage(len(count)): 
	for j in rnage(count[i]): 
		print(i, end=' ') 

• 계수 정렬의 시간 복잡도 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 $O(N + K)$를 보장한다.
  
• 계수 정렬의 공간 복잡도 계수 정렬은 경우에 따라 심각한 비효율성을 초래할 수 있다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니며 동일한 값을 가지는 데이터가 여러개 등장할 때 적합하다. 공간복잡도: $O(N + K)$
  

정렬 알고리즘 비교하기

• 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 $O(NlogN)$을 보장하도록 설계되어 있음

파이썬의 정렬 라이브러리

파이썬의 기본 정렬 라이브러리인 sorted() 함수는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다. 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 $O(NlogN)$을 보장한다는 장점이 있다. sort() 함수는 별도의 정렬된 리스트를 반환하지 않고 내부 원소가 바로 정렬된다.

sorted(), sort() 함수를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.