버블 정렬 (Bubble Sort)
"""
1. 개념 설명:
버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.
인접한 두 원소를 비교하여 순서가 잘못되어 있으면 서로 교환하는 방식으로 동작합니다.
2. 처리 과정 순서:
1) 첫 번째 원소와 두 번째 원소를 비교하여 필요시 교환
2) 두 번째 원소와 세 번째 원소를 비교하여 필요시 교환
3) 위 과정을 끝까지 반복
4) 한 번의 순회가 끝나면 가장 큰 원소가 마지막 위치로 이동
5) 정렬이 완료될 때까지 1~4 과정을 반복
3. 코드 예제
"""
# Python
def bubble_sort(arr):
n = len(arr)
# 전체 원소에 대해 반복
for i in range(n):
# 각 회전에서 인접한 원소 비교
for j in range(0, n-i-1):
# 현재 원소가 다음 원소보다 크면 교환
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
// C
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n-1; i++) {
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
// Java
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
"""
4. 주의사항:
- 시간복잡도가 O(n²)로 매우 비효율적입니다
- 큰 데이터셋에는 적합하지 않습니다
- 안정 정렬(Stable sort)입니다
- 구현이 간단하여 교육용으로는 좋지만 실제 사용은 권장되지 않습니다
"""
선택 정렬 (Selection Sort)
"""
1. 개념 설명:
선택 정렬은 해당 위치에 들어갈 값을 찾아 정렬하는 알고리즘입니다.
배열 전체에서 최솟값을 찾아 첫 번째 위치와 교환하는 방식으로 동작합니다.
2. 처리 과정 순서:
1) 주어진 배열에서 최솟값을 찾음
2) 최솟값을 맨 앞 위치의 값과 교환
3) 맨 앞 위치를 제외한 나머지 배열에서 최솟값을 찾음
4) 위 과정을 반복
3. 코드 예제
"""
# Python
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
# 최솟값 찾기
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 최솟값을 현재 위치로 교환
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
// C
void selectionSort(int arr[], int n) {
int i, j, min_idx;
for (i = 0; i < n-1; i++) {
min_idx = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// Java
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
}
"""
4. 주의사항:
- 시간복잡도가 O(n²)로 비효율적입니다
- 버블 정렬보다는 성능이 좋지만 여전히 큰 데이터셋에는 부적합합니다
- 불안정 정렬(Unstable sort)입니다
- 메모리 사용이 효율적입니다(추가 메모리 필요 없음)
"""
삽입 정렬 (Insertion Sort)
"""
1. 개념 설명:
삽입 정렬은 각 원소를 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 알고리즘입니다.
카드를 정렬하는 방식과 유사하게 작동합니다.
2. 처리 과정 순서:
1) 두 번째 원소부터 시작
2) 현재 원소와 이전 원소들을 비교
3) 현재 원소가 이전 원소보다 작으면 이전 원소를 뒤로 이동
4) 알맞은 위치에 현재 원소를 삽입
5) 위 과정을 배열 끝까지 반복
3. 코드 예제
"""
# Python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
# key보다 큰 원소들을 뒤로 이동
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
// C
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// Java
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
}
"""
4. 주의사항:
- 평균적으로 O(n²) 시간복잡도를 가집니다
- 거의 정렬된 배열에 대해서는 매우 효율적입니다(O(n))
- 안정 정렬(Stable sort)입니다
- 작은 데이터셋에서는 퀵 정렬보다 더 효율적일 수 있습니다
- 온라인 정렬 알고리즘으로, 데이터가 하나씩 입력되는 경우에 유용합니다
"""
병합 정렬 (Merge Sort)
"""
1. 개념 설명:
병합 정렬은 분할 정복(divide and conquer) 방법을 사용하는 정렬 알고리즘입니다.
배열을 작은 부분으로 분할하고, 정렬하면서 병합하는 방식으로 동작합니다.
2. 처리 과정 순서:
1) 배열을 절반으로 분할
2) 분할된 배열을 재귀적으로 정렬
3) 정렬된 두 배열을 병합
4) 위 과정을 더 이상 분할할 수 없을 때까지 반복
3. 코드 예제
"""
# Python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
// C
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Java
public class MergeSort {
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
private static void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
}
"""
4. 주의사항:
- 시간복잡도는 O(n log n)으로 효율적입니다
- 안정 정렬(Stable sort)입니다
- 추가 메모리 공간이 필요합니다 (O(n))
- 연결 리스트의 정렬에 매우 효율적입니다
퀵 정렬 (Quick Sort)
"""
1. 개념 설명:
퀵 정렬은 분할 정복(divide and conquer) 방법을 사용하는 매우 효율적인 정렬 알고리즘입니다.
피벗(pivot)을 선택하고 피벗을 기준으로 작은 값과 큰 값을 분할하여 정렬하는 방식입니다.
2. 처리 과정 순서:
1) 배열에서 피벗 선택(보통 첫 번째, 마지막, 또는 중간 요소)
2) 피벗보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 분할
3) 분할된 부분 배열에 대해 재귀적으로 퀵 정렬 수행
4) 정렬된 부분 배열들을 결합
3. 코드 예제
"""
# Python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 다른 방식의 Python 구현 (in-place)
def quick_sort_inplace(arr, low, high):
def partition(low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
if low < high:
pi = partition(low, high)
quick_sort_inplace(arr, low, pi - 1)
quick_sort_inplace(arr, pi + 1, high)
// C
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
"""
4. 주의사항:
- 평균 시간복잡도는 O(n log n)이지만, 최악의 경우 O(n²)입니다
- 불안정 정렬(Unstable sort)입니다
- 피벗 선택이 성능에 큰 영향을 미칩니다
- 이미 정렬된 배열에 대해서는 비효율적일 수 있습니다
- 무작위로 피벗을 선택하면 최악의 경우를 피할 수 있습니다
- 실제로 많이 사용되는 효율적인 정렬 알고리즘입니다
- 대부분의 프로그래밍 언어의 내장 정렬 함수는 퀵 정렬을 기반으로 합니다
"""