정렬 알고리즘은 컴퓨터 과학에서 데이터를 특정 순서대로 정렬하는 방법을 의미합니다. 여기에서는 가장 널리 사용되는 몇 가지 정렬 알고리즘에 대해 알아보고, 각 알고리즘의 동작 방식과 예제를 살펴보겠습니다.
삽입 정렬(Insertion Sort)은 배열의 각 요소를 적절한 위치에 삽입하여 정렬하는 방식입니다. 작은 데이터셋에 대해 효율적이며 구현이 간단합니다.
알고리즘 수행 단계
1. 배열의 첫 번째 요소를 정렬된 부분으로 간주합니다.
2. 다음 요소를 정렬된 부분과 비교하여 적절한 위치에 삽입합니다.
3. 이 과정을 배열의 마지막 요소까지 반복합니다.
예를 들어 다음과 같은 배열을 삽입 정렬로 정렬할 경우 다음과 같이 수행됩니다.
정렬되지 않은 배열: [5, 2, 9, 1, 5, 6]
- 첫 번째 요소 5는 이미 정렬되어 있다고 가정합니다.
- 두 번째 요소 2를 정렬된 부분(5)과 비교하여 2가 더 작으므로 2와 5의 위치를 바꿉니다. [2, 5, 9, 1, 5, 6]
- 세 번째 요소 9는 정렬된 부분(2, 5)과 비교하여 자신의 자리를 유지합니다. [2, 5, 9, 1, 5, 6]
- 네 번째 요소 1은 정렬된 부분(2, 5, 9)과 비교하여 적절한 위치로 이동합니다. [1, 2, 5, 9, 5, 6]
- 다섯 번째 요소 5는 정렬된 부분(1, 2, 5, 9)과 비교하여 적절한 위치로 이동합니다. [1, 2, 5, 5, 9, 6]
- 마지막 요소 6은 정렬된 부분(1, 2, 5, 5, 9)과 비교하여 적절한 위치로 이동합니다. [1, 2, 5, 5, 6, 9]
선택 정렬(Selection Sort)은 배열에서 최솟값을 찾아 첫 번째 요소와 자리를 바꾸는 과정을 반복하여 정렬하는 방식입니다.
알고리즘 수행 단계
1. 배열에서 최솟값을 찾습니다.
2. 최솟값을 배열의 첫 번째 요소와 교환합니다.
3. 배열의 두 번째 요소부터 다시 이 과정을 반복합니다.
예를 들어 다음과 같은 배열을 삽입 정렬로 정렬할 경우 다음과 같이 수행됩니다.
정렬되지 않은 배열: [5, 2, 9, 1, 5, 6]
- 배열에서 최솟값 1을 찾아 첫 번째 요소와 교환합니다. [1, 2, 9, 5, 5, 6]
- 두 번째 요소부터 최솟값 2를 찾습니다. [1, 2, 9, 5, 5, 6]
- 세 번째 요소부터 최솟값 5를 찾아 세 번째 요소와 교환합니다. [1, 2, 5, 9, 5, 6]
- 네 번째 요소부터 최솟값 5를 찾아 네 번째 요소와 교환합니다. [1, 2, 5, 5, 9, 6]
- 다섯 번째 요소부터 최솟값 6을 찾아 다섯 번째 요소와 교환합니다. [1, 2, 5, 5, 6, 9]
버블 정렬(Bubble Sort)은 인접한 두 요소를 비교하여 필요시 자리를 바꾸는 과정을 반복하여 정렬하는 방식입니다.
알고리즘 수행 단계
1. 배열의 첫 번째 요소부터 인접한 요소를 비교합니다.
2. 두 요소를 비교하여 크기가 잘못되어 있으면 교환합니다.
3. 배열의 끝까지 이 과정을 반복하고, 필요시 다음 패스를 시작합니다.
예를 들어 다음과 같은 배열을 삽입 정렬로 정렬할 경우 다음과 같이 수행됩니다.
정렬되지 않은 배열: [5, 2, 9, 1, 5, 6]
- 첫 번째 요소 5와 두 번째 요소 2를 비교하여 교환합니다. [2, 5, 9, 1, 5, 6]
- 두 번째 요소 5와 세 번째 요소 9는 교환하지 않습니다.
- 세 번째 요소 9와 네 번째 요소 1을 비교하여 교환합니다. [2, 5, 1, 9, 5, 6]
- 네 번째 요소 9와 다섯 번째 요소 5를 비교하여 교환합니다. [2, 5, 1, 5, 9, 6]
- 다섯 번째 요소 9와 여섯 번째 요소 6을 비교하여 교환합니다. [2, 5, 1, 5, 6, 9]
- 첫 번째 패스가 끝난 후 두 번째 패스를 시작합니다. [2, 5, 1, 5, 6, 9]
- 이 과정을 배열이 정렬될 때까지 반복합니다.
퀵 정렬(Quick Sort)은 분할 정복 알고리즘을 사용하여 배열을 정렬하는 방식입니다. 피벗(Pivot)이라는 일종의 기준점을 선택하고, 피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 분할하여 재귀적으로 정렬합니다.
알고리즘 수행 단계
1. 배열에서 피벗 요소를 선택합니다.
2. 피벗보다 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 배치합니다.
3. 피벗을 기준으로 배열을 두 부분으로 나눕니다.
4. 각 부분을 재귀적으로 정렬합니다.
예를 들어 다음과 같은 배열을 삽입 정렬로 정렬할 경우 다음과 같이 수행됩니다.
정렬되지 않은 배열: [5, 2, 9, 1, 5, 6]
- 피벗 요소로 5를 선택합니다.
- 5보다 작은 요소들을 왼쪽으로, 큰 요소들을 오른쪽으로 배치합니다. [2, 1, 5, 9, 5, 6]
- 피벗 기준으로 배열을 나눕니다. [2, 1] [5] [9, 5, 6]
- 각 부분을 재귀적으로 정렬합니다.
- 왼쪽 부분 [2, 1]을 정렬합니다. [1, 2]
- 오른쪽 부분 [9, 5, 6]을 정렬합니다. [5, 6, 9]
- 최종 정렬된 배열: [1, 2, 5, 5, 6, 9]
병합 정렬은 분할 정복 알고리즘을 사용하여 배열을 반으로 나누고, 각 부분을 정렬한 다음 병합하여 정렬하는 방식입니다.
알고리즘 수행 단계
1. 배열을 절반으로 나눕니다.
2. 각 부분을 재귀적으로 정렬합니다.
3. 정렬된 두 부분을 병합합니다.
예를 들어 다음과 같은 배열을 삽입 정렬로 정렬할 경우 다음과 같이 수행됩니다.
정렬되지 않은 배열: [5, 2, 9, 1, 5, 6]
- 배열을 두 부분으로 나눕니다. [5, 2, 9] [1, 5, 6]
- 각 부분을 재귀적으로 정렬합니다. [2, 5, 9] [1, 5, 6]
- 정렬된 두 부분을 병합합니다.
- [2, 5, 9]과 [1, 5, 6]을 병합합니다. [1, 2, 5, 5, 6, 9]
힙 정렬은 힙 데이터를 이용하여 배열을 정렬하는 방식입니다. 최대 힙 또는 최소 힙을 구성하여 정렬합니다.
최대 힙과 최소 힙은 4장에서 설명합니다.
알고리즘 수행 단계
1. 배열을 힙으로 변환합니다.
2. 최대 힙의 루트 요소를 제거하고, 배열의 마지막 요소와 교환합니다.
3. 힙의 크기를 줄이고, 힙 속성을 유지합니다.
4. 배열이 정렬될 때까지 이 과정을 반복합니다.
예를 들어 다음과 같은 배열을 삽입 정렬로 정렬할 경우 다음과 같이 수행됩니다.
정렬되지 않은 배열: [5, 2, 9, 1, 5, 6]
- 배열을 최대 힙으로 변환합니다. [9, 5, 6, 1, 2, 5]
- 루트 요소 9를 제거하고 마지막 요소와 교환합니다. [5, 5, 6, 1, 2, 9]
- 힙의 크기를 줄이고 힙 속성을 유지합니다. [6, 5, 5, 1, 2, 9]
- 루트 요소 6을 제거하고 마지막 요소와 교환합니다. [2, 5, 5, 1, 6, 9]
- 힙의 크기를 줄이고 힙 속성을 유지합니다. [5, 2, 5, 1, 6, 9]
- 이 과정을 반복하여 배열을 정렬합니다. [1, 2, 5, 5, 6, 9]