정렬(sorting) 알고리즘
무언가를 정리하는 방법으로, 예를 들면 수를 큰 수에서 작은 수로 정렬할 수도 있고 문자를 알파벳 A부터 Z까지 정렬할 수도 있다.
1. 버블 정렬 (Bubble Sort)
버락 오바마가 대통령 후보 자격으로 구글에 방문했을 때 구글 CEO였던 에릭 슈미트와 이야기를 나눈 내용 중 하나이다. 32비트 정수 100만개를 정렬하는 효율적인 방법이 무엇이냐는 질문에 대답한 모습이다.
이처럼 버블정렬은 이해하기에 쉬운 알고리즘이지만 정렬 알고리즘 중에서 가장 퍼포먼스가 좋지 않아 많이 사용하지 않는 정렬 방식이다.
✏️ 기본 개념 & 과정
두 개의 인접한 데이터를 비교하여 크기순으로 swap하는 과정을 반복한다.
(오름차순으로 정렬인 경우)
1. 서로 가까이 있는 숫자 두 개를 비교하여, 작은 수는 앞으로 큰 수는 뒤로 이동한다.
2. 이걸 계속 반복한다.
n개의 데이터가 있을 때, 이웃하는 두 개를 비교하는 과정은 한 스텝 당 n-1번 필요하다. 이를 총 n-1번 진행하기 때문에 시간복잡도는 O(n^2)이다.
🖥️ 코드 (python)
def bubble_sort(array):
n = len(array)
for i in range(0, n-1):
for j in range(0, n-1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]2. 선택 정렬 (Selection Sort)
✏️ 기본 개념 & 과정
정렬되지 않은 데이터에서 가장 작은 원소를 찾아, 맨 앞 원소와 swap을 이어 나가는 방식
오름차순 정렬인 경우
1. 원소의 개수가 n개인 정렬되지 않은 데이터에서 가장 작은 원소를 찾는다.
2. 맨 앞의 원소와 자리를 바꾼다. (맨 앞은 정렬 완료)
3. 나머지 정렬되지 않은 데이터에서 1, 2 과정을 n-1번 반복한다. (= 모든 원소가 정렬될때까지 반복한다)
🖥️ 코드 (python)
def selection_sort(array):
n = len(array)
for i in range(n-1):
mini = array[i]
idx = i
for j in range(i+1, n):
if array[j] < mini:
mini = array[j]
idx = j #최소값과 인덱스 위치를 저장
array[i], array[idx] = array[idx], array[i]
print(array)
3. 삽입 정렬 (Insertion Sort)
✏️ 기본 개념 & 과정
2번째 데이터부터 시작해서, 나보다 더 큰 수를 안 만날때까지 자리를 바꾸는 과정
오름차순 정렬인 경우
1. 2번째 원소부터 시작하여 왼쪽 원소들을 하나씩 비교한다.
2. 나보다 더 큰 수를 만나면 swap 한다.
3. 나보다 작은 수를 만날 때 까지 2번을 반복한다.
4. 3번에서 멈추었으면, 3번째 원소부터 시작하여 다시 1번부터 진행한다.
5. 이 과정을 반복한다. n번째 원소까지
🖥️ 코드 (python)
def insertion_sort(array):
n = len(array)
for i in range(1, n):
for j in range(i, 0, -1):
if array[j-1] > array[j]: #left > right인 경우 swap
array[j-1], array[j] = array[j], array[j-1]
else: #left < right인 경우 종료
break
print(array)4. 퀵 정렬(Quick Sort)
이름에서부터 알 수 있듯이 정렬 알고리즘 중에서 가장 효율이 좋다. (시간복잡도 O(nlogn)) 하지만 최악의 상황에서는 O(n^2) 의 시간 복잡도를 보일 수 있다. (최악의 상황 = 이미 배열이 정렬 완료된 상태)
✏️ 기본 개념 & 과정
기본 개념
오름차순인 경우
1. 배열에서 임의의 원소 하나를 골라 피벗(Pivot)을 설정한다.
2. 피벗 기준 왼쪽에는 피벗보다 값이 작은 배열을, 오른쪽에는 피벗보다 값이 큰 배열을 만든다.
3. 피벗 기준으로 배열을 두 개 나눈다.
4. 나뉜 두 개의 배열에 1,2,3 과정을 적용한다.
✅ 그림으로 퀵정렬 이해하기
🖥️ 코드 (비재귀, python)
def quick_sort(array):
n = len(array)
stack = [[0,n-1]]
while stack:
start, end = stack.pop()
left, right = start, end
pivot = array[(left+right)//2]
while array[left] < pivot:
left += 1
while array[right] > pivot:
right -= 1
if left <= right:
array[left], array[right] = array[right], array[left]
left += 1
right -= 1
if start < right:
stack.append([start, right])
if left < end:
stack.append([left, end])
print(stack, array)
print(array)🖥️ 코드 (재귀, c++)
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>>
using namespace std;
int arr[] = { 6, -8, 1, 12, 8, 3, 7, -7 };
int n = 10;
void quick_sort(int st, int en)
{
int left = st+1;
int right = en - 1;
int pivot = arr[st];
if (en - st <= 1) return;
while (1)
{
while (left <= right && arr[left] < pivot) left++;
while(left <= right && arr[right] > pivot) right--;
if (left > right) break;
swap(arr[left], arr[right]);
}
swap(arr[right], arr[st]);
quick_sort(st, right);
quick_sort(left, en);
}
int main(void)
{
quick_sort(0, 10);
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
}5. 합병 정렬 (Merge Sort)
배열을 쪼갠 뒤에 다시 합병하면서 정렬해나가는 과정을 말한다. 퀵소트처럼 빠르고 안정적이며 시간복잡도는 O(NlogN)이다.
✏️ 기본 개념 & 과정
오름차순 정렬인 경우
1. 배열을 더 이상 쪼갤 수 없을 때까지 계속 분할한다.
2. 인접한 두 개의 배열 원소 크기를 비교하여, 크기순으로 배열을 합친다.
3. 2번 과정을 전체 배열 사이즈가 될 때 까지 반복한다.
🖥️ 코드 (c++)
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>>
using namespace std;
int arr[] = { 6, -8, 1, 12, 8, 3, 7, -7 };
int tmp[10]; //두 리스트를 합친 결과를 임시 저장하는 공간
int n = 10;
//합치는 함수
void merge(int st, int en)
{
int mid = (st + en) / 2;
int left = st;
int right = mid;
for (int i = st; i < en; i++)
{
if (right == en) tmp[i] = arr[left++];
else if (left == mid) tmp[i] = arr[right++];
else
{
if (arr[left] <= arr[right]) tmp[i] = arr[left++];
else tmp[i] = arr[right++];
}
}
for (int i = st; i < en; i++)
{
arr[i] = tmp[i];
}
}
//분할하는 함수
void merge_sort(int st, int en)
{
if (en - st == 1) return; //길이가 1이라면 더 분할할 게 없음
int mid = (st + en) / 2;
merge_sort(st, mid);
merge_sort(mid, en);
merge(st, en);
}
int main(void)
{
merge_sort(0, 10);
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
}🖥️ 코드 (python)
array = [27, 10, 12, 20, 25, 13]
def merge_sort(array):
if len(array) <= 1:
return array
#크기가 1 이하면 반환
mid = len(array) // 2
left = array[:mid]
right = array[mid:]
#리스트를 2분할
left_ = merge_sort(left)
right_ = merge_sort(right) #2분할한 리스트를 다시 merge_sort 진행
return merge(left_, right_)
def merge(left, right):
i, j = 0, 0
sorted_list = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_list.append(left[i])
i += 1
else:
sorted_list.append(right[j])
j += 1
while i < len(left):
sorted_list.append(left[i])
i += 1
while j < len(right):
sorted_list.append(right[j])
j += 1
return sorted_list
print(merge_sort([27, 10, 12, 20, 25]))