alpyrithm_알파이리즘
기본 정렬 알고리즘(Sorting Algorithm) 정리 본문
정렬 알고리즘은 n개의 숫자를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다.
1. 선택 정렬(Selection Sort)
선택 정렬은 현재 위치에 들어갈 값을 찾아 정렬하는 알고리즘이다.
기본 로직
- 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.
- 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
- 다음 인덱스에서 위 과정을 반복해준다.
이 정렬 알고리즘은 n-1개, n-2개, ..., 1개씩 비교를 반복한다.
따라서 배열이 어떻게 되어있어도 전체 비교를 진행하므로 시간복잡도는 O(N^2)이다.
공간복잡도는 단 하나의 배열에서만 진행하므로 O(N)이다.
Python code
def selectionSort(arr):
n = len(arr)
for i in range(n-1):
tmp = i
for j in range(i+1, n):
if arr[tmp] >= arr[j]:
tmp = j
arr[i], arr[tmp] = arr[tmp], arr[i]
2. 삽입 정렬(Insertion Sort)
삽입 정렬은 현재 위치에서 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 알고리즘이다.
기본 로직
- 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.
- 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.
- 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.
- 만약 삽입 변수가 더 크면 비교 인덱스 +1에 삽입 변수를 저장한다.
이 정렬 알고리즘은 최악의 경우(역으로 정렬되어있을 경우) n-1개, n-2개, ..., 1개씩 비교를 반복하여 시간복잡도는 O(N^2)이다.
그러나 이미 정렬되어 있는 경우에는 한 번씩 밖에 비교를 하지 않아 시간복잡도는 O(N)이다.
공간복잡도는 단 하나의 배열에서만 진행하므로 O(N)이다.
Python code
def insertionSort(arr):
n = len(arr)
for i in range(1, n):
tmp = arr[i]
j = i-1
while j >= 0 and tmp < arr[j]:
arr[j], arr[j+1] = arr[j+1], arr[j]
j -= 1
arr[j+1] = tmp
3. 버블 정렬(Bubble Sort)
버블 정렬은 매번 연속된 두 개 인덱스를 비교하여, 정한 기준의 값을 뒤로 념겨 정렬하는 알고리즘이다.
오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 때 가장 큰 값이 맨 뒤에 저장된다.
맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에, 전체 배열의 크기-현재까지 순환한 바퀴 수 만큼 반복해주면 된다.
기본 로직
- 버블 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교한다.
- 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
- 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.
- 이를 전체 배열의 크기 - 현재까지 순환한 바퀴 수 만큼 반복한다.
이 정렬 알고리즘은 1부터 비교를 시작하여, n-1개, n-2개, ..., 1개씩 비교를 반복한다.
따라서 배열이 어떻게 되어있어도 전체 비교를 진행하므로 시간복잡도는 O(N^2)이다.
공간복잡도는 단 하나의 배열에서만 진행하므로 O(N)이다.
Python code
def bubbleSort(arr):
n = len(arr)
for i in range(n-1):
for j in range(1, n-i):
if arr[j-1] > arr[j]:
arr[j-1], arr[j] = arr[j], arr[j-1]
4. 합병 정렬(Merge Sort)
합병 정렬은 분할 정복(Divide and Conquer) 방식으로 설계된 알고리즘이다.
분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로 분할은 배열의 크기가 1보다 작거나 같을 때까지 반복한다.
입력으로 하나의 배열을 받고, 연산 중에 두 개의 배열로 계속 쪼개 나간 뒤, 합치면서 정렬해 최후에는 하나의 정렬을 출력한다.
합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나간다.
분할 과정의 기본 로직
- 현재 배열을 반으로 쪼갠다. 배열의 시작 위치와, 종료 위치를 입력받아 둘을 더한 후 2로 나눠 그 위치를 기준으로 나눈다.
- 이를 쪼갠 배열의 크기가 0이거나 1일 때까지 반복한다.
합병 과정의 기본 로직
- 두 배열 A, B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i, j로 가정하자.
- i에는 A배열의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.
- A[i]와 B[j]를 비교한다. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장한다.
- A[i]가 더 작다면 A[i]의 값을 배열 C에 저장해주고, i의 값을 하나 증가시켜준다.
- 이를 i나 j 둘 중 하나가 각자 배열의 끝에 도달할 때까지 반복한다.
- 끝까지 저장을 못한 배열의 값을 순서대로 전부 다 C에 저장한다.
- C 배열을 원래의 배열에 저장해준다.
이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.
이 정렬 알고리즘의 합병 과정은 두 배열 A, B를 정렬하기 때문에, A배열의 크기를 N1, B배열의 크기를 N2라고 할 경우, O(N1+N2)와 같다. 배열 A와 배열 B는 하나의 배열을 나눈 배열들이기 때문에 전체 배열의 길이가 N이라고 할 경우 N = N1 + N2이므로 O(N)이라고 할 수 있다.
이 정렬 알고리즘의 분할 과정은 lgN만큼 일어나는데, 이 이유는 간단한다. 크기가 N인 배열을 분할하면, 한 번 분할하면 N/2, N/2 2개이고 그 다음 분할하면 N/4, N/4, N/4, N/4 4개이다. 즉 분할 과정은 매번 반씩 감소하므로 lgN만큼 반복해야 크기가 1인 배열로 분할할 수 있다.
각 분할별로 합병을 진행하므로, 합병정렬의 시간복잡도는 O(NlgN)이다.
사용하는 공간은 정렬을 위해 배열을 하나 더 생성하므로 2N개 사용한다.
Python code
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
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
leftarr = arr[:mid]
rightarr = arr[mid:]
leftarr = mergeSort(leftarr)
rightarr = mergeSort(rightarr)
return merge(leftarr, rightarr)
5. 퀵 정렬(Quick Sort)
퀵 정렬도 분할 정복(Divide and Conquer) 방식으로 설계된 알고리즘이다.
Pivot point라고 기준이 되는 값을 하나 설정하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다.
이를 반복하여 분할된 배열의 크기가 1이 되면 배열이 모두 정렬된 것이다.
기본 로직
- pivot point로 잡을 배열의 값 하나를 정한다. 보통 맨 앞이나 맨 뒤, 혹은 전체 배열 값 중 중간값이나 랜덤 값으로 정한다.
- 분할을 진행하기에 앞서, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장하는 right 변수를 생성한다.
- right부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며 비교한 배열값이 pivot point보다 크면 right를 하나 감소시키고 비교를 반복한다.
- pivot point 보다 작은 배열 값을 찾으면 반복을 중지한다.
- 그 다음 left부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며 비교한 배열값이 pivot point 보다 작으면 left를 하나 증가시키고 비교를 반복한다.
- pivot point 보다 큰 배열 값을 찾으면 반복을 중지한다.
- left 인덱스의 값과 right인덱스의 값을 바꿔준다.
- 3, 4, 5 과정을 left < right가 만족할 때까지 반복한다.
- 위 과정이 끝나면 left의 값과 pivot point를 바꿔준다.
- 맨 왼쪽부터 left-1까지, left+1부터 맨 오른쪽까지로 나눠 퀵 정렬을 반복한다.
이 정렬 알고리즘은 분할 과정과 정렬 과정으 동시에 진행한다.
각 정렬은 배열의 크기 N만큼 비교하여, 이를 총 분할 깊이인 lgN만큼 진행하므로 총 비교횟수는 NlgN, 즉 시간복잡도는 O(NlgN)이다.
다만 퀵 정렬에는 최악의 경우가 존재하는데, 이는 배열이 이미 정렬 되어있는 경우이다. 이 경우 분할이 N만큼 일어나므로 시간복잡도는 O(N^2)이다.
이를 방지하기 위해 pivot point를 전체 배열의 중간값이나 랜덤 값으로 쓰기도 한다.
최악의 경우 때문에 합병 정렬보다 느린 알고리즘이라 생각하기 쉽지만, 발생하기 쉽지 않은 경우이고, 일반적으로 퀵 정렬이 합병 정렬보다 20% 이상 빠르다고 한다.
Python code
def quickSort(arr):
def sort(low, high):
if high <= low:
return
mid = partition(low, high)
sort(low, mid - 1)
sort(mid, high)
def partition(low, high):
pivot = arr[(low + high) // 2]
while low <= high:
while arr[low] < pivot:
low += 1
while arr[high] > pivot:
high -= 1
if low <= high:
arr[low], arr[high] = arr[high], arr[low]
low, high = low + 1, high - 1
return low
return sort(0, len(arr) - 1)
def quickSort(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 quickSort(lesser_arr) + equal_arr + quickSort(greater_arr)