정렬

Bubble sort

• 인정합 두 원소를 검사하여 정렬하는 방법
• n^2의 시간 복잡도로 상당히 느리지만 코드가 단순해서 자주 사용한다.

def bubble_sort(array):
	n = len(array)
	for _ in range(n - 1):
		for j in range(n - 1):
			if array[j] > array[j + 1]:
				array[j], array[j + 1] = array[j + 1], array[j]

	return array

print(bubble_sort([6,4,7,9,1])) 

Selection sort

• 처리할 대상 범위에서 최소값을 찾은 후 그 값을 대상 범위의 맨 앞에 있는 값으로 바꾸는 과정을 반복한다.

def selection_sort(array):
	n = len(array)
	for i in range(n - 1):
		for j in range(i + 1, n):
			if array[i] > array[j]:
				array[i], array[j] = array[j], array[i]
	return array
print(selection_sort([4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]))

Insertion sort

• 삽입 정렬은 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리를 찾아 삽입한다.

def insertion_sort(array):
	n = len(array)
	for i in range(1, n):
		j = i - 1
		while j >= 0 and array[j+1] < array[j]:
			array[j+1], array[j] = array[j], array[j+1] 
			j -= 1
	return array
print(insertion_sort([4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]))

Merge sort

• 리스트를 중간 지점인 mid를 중심으로 두 개의 리스트로 분리한다 .그 이후에 이 작업을 재귀적으로 적용한다. 분리된 두개의 리스트를 크기 순으로 정렬하면서 합친다.

def merge(left, right):
	result = []
	while len(left) > 0 or len(right) > 0:
		if len(left) > 0 and len(right) > 0:
			if left[0] <= right[0]:
				result.append(left.pop(0))
			else:
				result.append(right.pop(0))
		elif len(left) > 0:
			result.append(left.pop(0))
		elif len(right) > 0:
			result.append(right.pop(0))
	return result
    
def merge_sort(array):
	n = len(array)
	if n <= 1:
		return array
	mid = n // 2
	left = array[:mid]
	right = array[mid:]
	left = merge_sort(left)
	right = merge_sort(right)
	return merge(left,right)
print(merge_sort([4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]))

Quick sort

• 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘.

def quick_sort(array):
	n = len(array)
	if n <= 1:
		return array
	pivot = array[n // 2]
	left, equal, right = [], [], []
	for a in array:
		if a < pivot:
			left.append(a)
		elif a > pivot:
			right.append(a)
		else:
			equal.append(a)
	return quick_sort(left) + equal + quick_sort(right)

print(quick_sort([4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]))