- O() : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
- O(): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
거품정렬(bubble sort)
- 버블정렬은 가장 쉬운 정렬 알고리즘이지만 시간복잡도가 좋은 퍼포먼스를 내지 못해서 실제로는 잘 사용되지 않는다.
- idx0부터 시작하며 큰수가 나올때마다 기준점을 바꿔주면서 정렬됨
- 가장 큰수부터 작은 수 순으로 정렬됨
- 시간복잡도는 O(n²)이며 공간복잡도는 하나의 배열만 사용하여 정렬을 진행하기 때문에 O(n)이다.
def bubbleSort(num_list):
for loop_count in range(len(num_list)-1, 0, -1):
for idx in range(loop_count):
if num_list[idx] > num_list[idx+1]:
tmp = num_list[idx]
num_list[idx] = num_list[idx+1]
num_list[idx+1] = tmp
return num_list선택정렬(selection sort)
- 선택정렬은 시간복잡도가 O(n²)으로 버블정렬과 정렬하는 알고리즘이 버블정렬과 유사
- 한번 순회를 하면서 가장 작은 수를 찾아서 배열의 첫 위치와 교환한다.
= 한번 순회를 하면서 가장 큰 수를 찾아서 배열의 마지막 위치와 교환한다.
def selectionSort(num_list):
for idx in range(0,len(num_list)-1):
min_idx = idx
for num in range(idx+1, len(num_list)):
if num_list[num] < num_list[min_idx]:
min_idx = num
tmp = num_list[min_idx]
num_list[min_idx] = num_list[idx]
num_list[idx] = tmp
return num_list삽입정렬(insertion sort)
- 현재위치의 값을 현재위치보다 아래쪽으로 순회하며 알맞은 위치에 넣어주는 정렬알고리즘, 시간복잡도는 O(n²)
- index 0 인 경우는 순회할 아래쪽이 없으니 pass
- index 1 인 경우는 index0과 대소비교해서 위치 결정
- index 2 인 경우는 index1 => index0 순으로 한번씩 대소 비교해서 위치 결정
- 위 내용 반복
- 삽입정렬은 이미 정렬이 되어있다면 O(n)의 시간복잡도를 가지게되는데, 정렬이 되어있는 경우라면 한번 순회하며 체크만 하기 때문
def insertionSort(num_list):
for idx in range(1,len(num_list)):
present = num_list[idx]
position = idx
while position>0 and num_list[position-1]>present:
num_list[position]=num_list[position-1]
position = position-1
num_list[position]=present
return num_list병합정렬(merge sort)
- 시간복잡도는 최소 O(nlogn)을 보장하기때문에, 병합정렬은 가장 많이 쓰이는 정렬 알고리즘 중 하나이며
- 8개의 숫자(6,7,2,3,9,5,1,4)를 병합 알고리즘을 사용하여 오름차순으로 정렬 한다고 가정
- N=8인 배열을 한 개의 배열이 될 때까지 2로 나누면서(N/2) 분할
- 맨 아래에 한 개씩 분할 된 것을 N=8로 다시 만들어 주려면 어떻게 해야 할까요?
위에서 2로 나눈 것과 반대로 2씩 곱해줘야 합니다.
- 병합정렬은 정렬할 리스트를 반으로 쪼개나가며 좌측과 우측 리스트를 계속하여 분할해 나간 후 각 리스트내에서 정렬 후 병합(merge) 정렬 후 병합하는 과정을 통해 정렬하는 알고리즘이다.
def merge_sort(list):
if len(list) <= 1:
return list
mid = len(list) // 2
leftList = list[:mid]
rightList = list[mid:]
leftList = merge_sort(leftList)
rightList = merge_sort(rightList)
return merge(leftList, rightList)
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[0])
left = left[1:]
else:
result.append(right[0])
right = right[1:]
elif len(left) > 0:
result.append(left[0])
left = left[1:]
elif len(right) > 0:
result.append(right[0])
right = right[1:]
return result퀵 정렬(quick sort)
- 퀵정렬은 real-world 데이터에서 빠르다고 알려져 있어 가장 많이 쓰는 정렬알고리즘, pivot 개념이 핵심
- 퀵정렬은 pivot을 선정하여 pivot을 기준으로 좌측과 우측으로 pivot보다 작은값은 왼쪽 pivot보다 큰값은 오른쪽으로 재배치를 하고 계속하여 분할하여 정렬하는 알고리즘이다.
- 최악의 경우에는 O(n²)의 비교를 수행하지만 일반적으로 O(nlogn)의 시간복잡도를 가진다.
- 파이썬의 list.sort() 함수나 자바의 Arrays.sort()처럼 프로그래밍 언어 차원에서 기본적으로 지원되는 내장 정렬 함수는 대부분은 퀵 정렬을 기본으로 합니다.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
lesser_arr, equal_arr, greater_arr = [], [], []
for num in arr:
if num < pivot:
lesser_arr.append(num)
elif num > pivot:
greater_arr.append(num)
else:
equal_arr.append(num)
return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)힙 정렬(heap Sort)
- 힙 정렬(Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서,
- 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.
- 1) n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.
- 2) 최대 힙을 구성한다. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드(leaf node)를 자노드로 가진 부노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
- 3) 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
- 4) 2와 3을 반복한다.
(참고) 완전이진트리(complete binary tree)
- 이진 트리라고 하면, 자식의 갯수가 최대 2개인 Tree
- 완전 이진 트리(Complete Binary Tree)? 삽입할 때 왼쪽부터 차례로 추가하는 이진트리를 말합니다.
or 포화 이진 트리의 leaf들을 오른쪽에서부터 제거하여 얻어진 트리 - 포화 이진 트리? 모든 앞의 레벨이 동일한 이진트리이며, 잎이 아닌
내부 노드들은 모두 2개의 자식을 가지는 트리 - 완전 이진 트리 ⊃ 포화 이진 트리
References
oneofakindscene