✅

정렬

주로 많이 사용되는 정렬 7가지만 작성했으니 참고해주세요

버블 정렬(Bubble Sort)

# 시간복잡도 : O(N^2)
def bubble_sort(arr):
	for i in range(len(arr)):
		for j in range(len(arr)-1-i):
			if arr[j] > arr[j+1]:
				arr[j], arr[j+1] = arr[j+1], arr[j]
Python
복사

버블 정렬은 매번 연속된 두 인덱스를 비교합니다. 비교시마다 큰 값이 뒤로 교체되고 다음 인덱스로 이동합니다. 이후 계속 반복해서 비교하고 큰 값은 뒤로 교체됩니다. 한 바퀴 돌 때마다 가장 마지막에는 비교하는 수들 중 가장 큰 값이 저장되므로, 다음 바퀴를 돌 때에는 마지막 수는 제외하고 진행합니다.

선택 정렬(Selection Sort)

# 시간복잡도 : O(N^2)
def selection_sort(arr):
	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[min_index], arr[i] = arr[i], arr[min_index]
Python
복사

배열을 선형 탐색해서 최소값의 인덱스를 찾습니다. 최소값의 인덱스를 이용해 왼쪽 끝 인덱스의 값과 스왑하고 정렬을 완료합니다. 버블정렬과 비슷하지만 연속된 두 값을 매번 비교하는게 아니라 인덱스를 이용하다보니 버블 정렬보다 2배 정도 빠르다고 합니다.

삽입 정렬(Insertion Sort)

# 시간복잡도 : O(N^2)
def insertion_sort(arr):
	for i in range(len(arr)):
		key = arr[i]
		j = i-1
		
		# 오름차순 정렬 -> j인덱스의 값이 키보다 크면 계속 뒤로 넘기는 겁니다
		while j >= 0 and arr[j] > key:
			arr[j+1] = arr[j]
			j -= 1
		
		arr[j+1] = key # while문에서 계속 j-1을 하므로 키값은 j+1에 넣어줘야합니다
Python
복사

이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입하는 경우에 최선의 알고리즘입니다. 가장 앞 쪽에 있는 원소는 이미 정렬되어 있다고 가정하고 시작합니다(첫 시작에 i보다 작은 인덱스에서 확인할 요소가 없습니다).

병합 정렬(Merge Sort)

# 시간복잡도 : O(N * logN)
# 공간복잡도 : O(N)
def merge_sort(arr):
	# 기저 조건
	if len(arr) <= 1:
		return arr
	
	mid = len(arr) // 2
	# 재귀함수 실행
	left_arr = merge_sort(arr[:mid])
	right_arr = merge_sort(arr[mid:])
	
	# 재귀가 끝난 후, 병합하는 과정에서 값을 비교해 정렬한 형태로 만들고 반환
	merged_arr = []
	l = r = 0
	while l < len(left_arr) and r < len(right_arr):
		if left_arr[l] > right_arr[r]:
			merged_arr.append(left_arr[l])
			l += 1
		else:
			merged_arr.append(right_arr[r])
			r += 1
	
	# 남은 값들 이어붙이기
	merged_arr += left_arr[l:]
	merged_arr += right_arr[r:]
	
	return merged_arr
Python
복사

분할정복 & 재귀 알고리즘을 이용해 해결하는 정렬 알고리즘입니다. 배열을 두 개의 배열로 계속 분할하기 때문에 재귀의 기저 조건은 배열의 크기가 1보다 작거나 같은 경우입니다. mid 인덱스를 이용해 두 개의 배열로 분할하여 재귀함수를 실행합니다. 기저 조건에 의해 재귀가 종료되면, 병합하는 과정이 시작됩니다. 두 배열을 비교하며 작은 값을 앞쪽에 넣어주면 됩니다. 병합 과정도 끝나면 병합된 배열을 반환합니다.

예시를 하나 들어보자면, 이런 식으로 분할되고 병합됩니다 :

Python
복사

퀵 정렬(Quick Sort)

# 시간복잡도 : 평균적으로는 O(N * logN), 최악의 경우엔 O(N^2)
def quick_sort(arr):
	if len(arr) <= 1:
		return arr
	
	pivot = arr[len(arr) // 2]
	smaller_arr, equal_arr, bigger_arr = [],[],[]
	
	for num in arr:
		if num < pivot:
			smaller_arr.append(num)
		elif num == pivot:
			equal_arr.append(num)
		else:
			bigger_arr.append(num)
	
	return quick_sort(smaller_arr) + eqaul_arr + quick_sort(bigger_arr)
Python
복사

병합 정렬처럼 분할 정복 기법과 재귀 알고리즘을 이용하는 정렬 알고리즘입니다. 재귀의 기저 조건은 병합 정렬과 마찬가지로 배열의 크기가 1보다 작거나 같은 경우입니다. 그리고 퀵 정렬은 pivot이라는 임의의 기준값을 이용해 배열을 분할합니다. 이때, pivot 값을 중앙값, 평균값 등등 여러 방법으로 설정할 수 있습니다(임의니까요). pivot 값을 설정하고나면, pivot보다 작은 값과 큰 값으로 배열을 분리합니다. 분리한 두 배열은 다시 퀵 정렬을 재귀적으로 수행합니다.

분할 과정을 다음과 같이 그려볼 수 있습니다(병합 과정은 그저 이어붙이는 거니까 생략) :

[2, 6, 3, 9, 9]
├── pivot = 3
│   ├── less: [2]
│   ├── equal: [3]
│   └── greater: [6, 9, 9]
│       ├── pivot = 9
│       │   ├── less: [6]
│       │   ├── equal: [9, 9]
│       │   └── greater: []
Python
복사

퀵 정렬에서 pivot을 설정할 때는 조심할 필요가 있습니다. 만약 너무 큰 값이나 작은 값으로 pivot을 설정하게 된다면, 한 쪽 배열에 쏠리게 됩니다. 그러면 최악의 상황에는 모든 배열을 계속 다시 정렬해야겠죠?

힙 정렬(Heap Sort)

import heapq

# 시간복잡도 : O(N * logN)
# 파이썬의 힙 모듈은 기본적으로 최소힙(minHeap)이라서 이 코드는 오름차순 정렬입니다
def heap_sort(arr):
	heap = []
	for num in arr:
		heapq.heappush(heap, num)
		
	result = []
	while heap:
		result.append(heapq.heappop(heap))
	
	return result
Python
복사

import heapq

# 다음과 같이 음수로 값을 저장해서 최대힙처럼 사용할 수 있습니다.
def max_heap_sort(arr):
    heap = []
    for num in arr:
        heapq.heappush(heap, -num)  # 음수로 저장해서 최대 힙처럼 사용

    result = []
    while heap:
        result.append(-heapq.heappop(heap))  # 꺼낼 때 다시 양수로

    return result
Python
복사

계수 정렬(Counting Sort)

# 시간복잡도 : O(N + K)
# N: 데이터 개수, K: 데이터 중 최댓값
def counting_sort(arr):
	max_val = max(arr)
	count = [0] * (max_val + 1)
	
	for num in arr:
		count[num] += 1
	
	result = []
	for i in range(len(count)):
		result.extend([i] * count[i])
	
	return result
Python
복사

여러 원소가 들어있는 배열을 정렬할 때, 각 숫자의 개수를 카운팅하는 배열을 하나 만들고 원소값에 해당하는 인덱스의 카운트를 1증가 시킵니다. count 배열을 순회하면서 인덱스를 카운트 횟수만큼 반복해서 result에 넣어주면 됩니다. 카운트하는 배열을 원소의 최대값까지의 범위로 만드는 만큼 공간 복잡도는 큰 편이므로, 계수 정렬은 정수 값의 범위가 좁을 때 효과적입니다.