[알고리즘] 다양한 정렬 알고리즘(Sort Algorithm)
Reference
이것이 취업을 위한 코딩 테스트다 with 파이썬, 한빛미디어, 나동빈 지음
📌 정렬 알고리즘 개요
- 정렬(sorting): 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
- 오름차순: 기준에 따라 작은 순서대로 나열
- 내림차순: 기준에 따라 큰 순서대로 나열
- 정렬 알고리즘은 이진 탐색(Binary Search)의 전처리 과정으로 많이 쓰인다.
📌 정렬의 조건과 특성
정렬의 조건
- 정렬은 기준이 되는 조건이 필요하다.
- 비교할 데이터
- 오름차순:
return this.x - other.x;- 음수이면 내가 먼저, 양수이면 other이 먼저
- 내림차순:
return other.x - this.x; - 자바에서는 Comparable의
compareTo()메서드를 이용하면 편함- 기준 값과 비교대상이 동일한 값일 경우 0
- 기준 값이 비교대상 보다 작은 경우 (음수)
- 기준 값이 비교대상 보다 큰 경우 (양수)
- In-place(제자리) / Stable(안정성) 여부
- 정렬 알고리즘이
In-place(제자리)한가? 정렬하는 과정에서 N(원소의 개수)에 비해 충분히 무시할 만한 개수의 메모리만큼만 추가적으로 사용하는가?- 10만개의 원소를 정렬할 때 추가적으로 100개의 메모리를 사용: In-place하다.
- 10만개의 원소를 정렬할 때 추가적으로 10만개의 메모리를 사용: In-place하지 않다.
- 정렬 알고리즘이
Stable(안정)한가? 동등한 위상의 원소들의 순서 관계가 보존되는가?- 안정 정렬(Stable Sort): 먼저 등장한 같은 값은 먼저 오도록 순서 관계가 보장된다.
- 불안정 정렬(Unstable Sort): 동등한 위상의 원소들의 순서 관계가 보존되지 않는다.
- 정렬 알고리즘이
정렬의 특성
- 같은 정보들은 인접해 있을 것이다.
- 각 원소마다 가장 비슷한 순서의 다른 원소는 자신의 양 옆
📌 버블 정렬(Bubble Sort)
- 버블 정렬(Bubble Sort): 서로 인접한 두 원소의 대소를 비교해 조건에 맞지 않으면 자리를 교환하는 정렬 알고리즘
- 기준에 맞는 값들이 위로 떠오르는 모습이 거품이 수면위로 올라가는 것과 비슷해 버블 정렬로 명명됨
- (0, 1), (1, 2), (2, 3) … (N - 3, N - 2), (N - 2, N - 1) 차례대로 비교해 조건에 맞지 않으면 교환하는 방식
- 오름차순 정렬 기준 한 번 순회할 때 마다 가장 큰 값이 가장 맨 뒤로 가게 된다. 즉, 1회 순회마다 마지막 위치에 제일 큰 값이 오고 마지막 값은 다음 순회에서 제외된다.
public class BubbleSort {
static void bubbleSort(int[] arr) {
int temp = 0;
for (int i = 0; i < arr.length; i++) { // 제외될 원소의 갯수, i번째 순회가 끝나면 i + 1번째 순회때 i개가 제외
for (int j = 1; j < arr.length - i; j++) { // j는 현재 원소를 가리키고, j - 1은 이전 원소
if (arr[j - 1] > arr[j]) { // 현재 원소와 이전 원소를 비교, 만약 이전 원소가 더 크면 교환
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println("정렬 완료: " + Arrays.toString(arr));
}
}
버블 정렬의 시간 복잡도와 공간 복잡도
시간 복잡도
- 평균 시간 복잡도: O(N^2)
- (N - 1) + (N - 2) + … + 2 + 1 = N * (N - 1) / 2
- 무조건 2개씩 비교하며 순회하기 때문에 최선, 최악의 경우도 모두 O(N^2)의 시간 복잡도를 가짐
공간 복잡도
- 주어진 배열 안에서 swap을 통해 연산이 수행된다.
- 총 공간 복잡도: O(N), 배열의 크기
- 크기가 100인 int 배열이 주어지면 400 bytes의 메모리가 필요
버블 정렬의 장점과 단점
- 장점
- 구현이 간단하고 직관적인 구현
- 주어진 자료만 사용해 정렬을 진행, 다른 메모리 공간이 필요하지 않음(In-place Sort, 제자리 정렬)
- 안정 정렬(Stable Sort): 동등한 위상의 원소들의 순서 관계가 보존됨
- 단점
- 최선, 최악, 평균 모두 O(N^2)으로 비효율적인 정렬 방법
- 교환 연산이 매우 많이 일어남
📌 선택 정렬(Selection Sort)
데이터가 무작위로 여러 개 나열되 있을 때, 이중 가장 작은 데이터를 선택해 제일 앞에 있는 데이터와 바꾸고, 맨 앞은 제외하고 그 다음부터 가장 작은 데이터를 선택해 맨 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것이 선택 정렬(Selection Sort) 알고리즘이다.
- 선택 정렬(Selection Sort): 데이터를 순회하며 가장 작은 데이터를 선택해 차례대로 정렬하는 알고리즘
- 오름차순 기준
- 해당 순서에 원소를 넣을 위치는 이미 정해져 있음
- 크기가 N인 배열이 있을 때, 1번째 순회는 1번째 자리, N - 1번째 순회는 N - 1번째 자리
- N - 1번째 까지 정렬 했으면 마지막 원소는 자연스럽게 가장 큰 값이 남는다.
- 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1 번 반복하면 정렬이 완료
public class SelectionSort {
static void selectionSort(int[] arr) {
int indexMin, temp;
for (int i = 0; i < arr.length - 1; i++) { // 위치를 선택, i번째 순회에서는 i번째 자리를 선택
indexMin = i;
for (int j = i + 1; j < arr.length; j++) { // i + 1번째 자리부터 순회 시작
if (arr[j] < arr[indexMin]) { // 현재 선택한 i번째 숫자보다 작은 숫자가 존재하면
indexMin = j; // 해당 인덱스를 저장(선택, Selection)
}
}
// swap
temp = arr[indexMin]; // 작은 값을 임시 값에 저장하고
arr[indexMin] = arr[i]; // 현재 i번째 자리에 있는 값을 작은 값이 존재하는 위치와 바꾸고
arr[i] = temp; // 작은 값을 i번째 자리에 넣는다.
}
System.out.println("정렬 완료: " + Arrays.toString(arr));
}
}
선택 정렬의 시간 복잡도와 공간 복잡도
시간 복잡도
정렬해야 하는 데이터의 개수가 N개(arr[N])라 가정한다.
- N - 1번 만큼 가장 작은 수를 찾아서(선택) 맨 앞으로 보낸다
- 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다
- 비교 연산의 경우 O(1) 시간이기 때문에 없다고 봐도 무방하다.
- 1번째 순회: arr[0] 선택한 후 arr[1] 부터 arr[N - 1] 까지 탐색
- 2번째 순회: arr[1] 선택한 후 arr[2] 부터 arr[N - 1] 까지 탐색
- N - 1번째 순회: arr[N - 2] 선택한 후 arr[N - 1]이 arr[N - 2] 보다 작은지 비교
- 총 N * (N - 1) / 2 번의 연산을 수행
- 총 시간 복잡도: O(N^2)
- 최선, 최악, 평균 모두 O(N^2) 시간 복잡도를 가진다.
공간 복잡도
- 주어진 배열 안에서 swap을 통해 연산이 수행된다.
- 총 공간 복잡도: O(N), 배열의 크기
- 크기가 100인 int 배열이 주어지면 400 bytes의 메모리가 필요
선택 정렬의 장점과 단점
- 장점
- 단순한 알고리즘 (구현이 쉬움)
- 비교 연산이 많지만 상수의 시간복잡도를 가지기 때문에 실제로 비교 연산의 시간은 적고, 버블 소트에 비해 교환하는 횟수가 적음. 즉, 많은 교환이 일어나야 하는 상태(랜덤으로 생성된 자료와 같은)에서 효율적
- 주어진 자료만 사용해 정렬을 진행, 다른 메모리 공간이 필요하지 않음(In-place Sort, 제자리 정렬)
- 단점
- 최선, 최악, 평균 모두 O(N^2)의 시간 복잡도를 가져 다른 정렬 알고리즘에 비해 비효율적
- Unstable Sort: 동등한 위상의 원소들의 순서 관계가 보존되지 않음
- [0, 3, 1, 4, 1] 이 주어졌을 때 정렬 시 2번 인덱스의 1이 4번 인덱스의 1보다 먼저 나온다는 보장이 없음
📌 삽입 정렬(Insertion Sort)
- 삽입 정렬(Insertion Sort): 특정한 데이터를 정렬 기준에 맞는 적절한 위치에 삽입하는 정렬 알고리즘
- 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입(Insert)
- 적절한 위치에 맞는 값을 찾을 때 이전 위치들은 모두 정렬되어 있다고 가정
- 선택 정렬처럼 직관적으로 이해하기 쉽지만 구현이 어려움, 다만 좀 더 효율적인 정렬 알고리즘
- 필요할 때만 위치를 swap 하므로 데이터가 거의 정렬되어 있을 때 효율적
- 최선의 경우(거의 정렬되어 있을 때) O(N)의 시간복잡도를 가짐
- 두 번째 데이터부터 시작해 앞의 원소들과 비교해 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입
public class InsertionSort {
static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) { // 2 번째 데이터 부터 시작
int temp = arr[i]; // 현재 위치의 값을 저장
int prev = i - 1; // 현재 위치의 이전 인덱스
while ( (prev >= 0) && (temp < arr[prev])) { // 이전 인덱스가 0 이상이고, 현재 위치의 값이 이전 인덱스보다 작으면
arr[prev + 1] = arr[prev]; // 이전 인덱스의 값을 오른쪽으로 한칸 이동
prev--; // 더 이전 위치로 이동
}
arr[prev + 1] = temp; // prev 에 위치한 값보다 크므로 prev + 1번 자리에 값을 삽입
}
System.out.println("정렬 완료: " + Arrays.toString(arr));
}
}
삽입 정렬의 시간 복잡도와 공간 복잡도
시간 복잡도
- 최악의 경우(오름차순 정렬을 원하지만 데이터가 내림차순으로 정렬되어 있을 때): O(N^2)
- 연산 횟수: (N - 1) + (N - 2) + … + 2 + 1 = N * (N - 1) / 2
- 최선의 경우(모두 오름차순으로 정렬되어 있을 때): O(N)
- 차례대로 한번씩 만 비교하기 때문에
- 평균: O(N^2)
공간 복잡도
- 주어진 배열 안에서 swap을 통해 연산이 수행된다.
- 총 공간 복잡도: O(N), 배열의 크기
- 크기가 100인 int 배열이 주어지면 400 bytes의 메모리가 필요
삽입 정렬의 장점과 단점
- 장점
- 알고리즘이 직관적으로 이해하기 쉬움
- 최선의 경우, 즉 기준에 맞게 정렬되어 있는 데이터가 많을수록 최고의 효율
- 주어진 자료만 사용해 정렬을 진행, 다른 메모리 공간이 필요하지 않음(In-place Sort, 제자리 정렬)
- Stable sorting, 안정 정렬: 동등한 위상의 원소들의 순서 관계가 보존됨
- 단점
- 최악의 경우 시간 복잡도가 O(N^2) 으로 비효율적
- 배열의 길이가 길어질수록, 즉 데이터의 크기가 클수록 비효율적
📌 퀵 정렬(Quick Sort)
- 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)은 대부분의 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. → 최악, 최선, 평균적인 경우 모두에서 종합적으로 다른 정렬 알고리즘에 비해 효율적
- 자바의 기본(primitive)타입 배열을 정렬하는
Arrays.sort()는 두개의 기준값(pivot)을 설정해 세 개의 영역으로 나누어 정렬하는 Dual-Pivot Quick Sort를 사용한다.
- 자바의 기본(primitive)타입 배열을 정렬하는
- 퀵 정렬(Quick Sort): 기준값(Pivot)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작하는 정렬 알고리즘
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?
- 분할 정복(Divide and Conquer)방법을 통해 정렬을 한다
- 호어 분할(Hoare Partition)방식을 기준으로 퀵 정렬
- 첫 번째(가장 왼쪽) 데이터를 기준값(Pivot)으로 설정한다.
- 왼쪽에서부터 pivot 보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
5 7 9 0 3 1 6 2 4 8
pivot = 5
0. 5 7 9 0 3 1 6 2 4 8
1. 5 4 9 0 3 1 6 2 7 8
2. 5 4 2 0 3 1 6 9 7 8
3. 1 4 2 0 3 | 5 | 6 9 7 8 -> 분할, 피봇을 기준으로 탐색했을 때 구간이 엇갈림
왼쪽 공간의 pivot = 1, 오른쪽 공간의 pivot = 6
4. 0 1 2 4 3 | 5 | 6 8 7 9
5. 0 1 2 3 4 | 5 | 6 7 8 9
import java.util.Arrays;
public class QuickSort {
static void quickSort(int[] arr, int start, int end) {
if (start >= end) { // 원소가 1개 이면 early return
return;
}
int pivot = start; // 첫 번째 원소를 피봇으로 설정
int left = start + 1; // 피봇 다음 데이터가 왼쪽 구간의 시작
int right = end; // 마지막 데이터가 오른쪽 구간의 시작
while (left <= right) {
while (left <= end && arr[left] <= arr[pivot]) { // 피봇보다 큰 데이터를 찾기
left++; // 왼쪽 구간 탐색 -> 피봇보다 큰 데이터 찾기
}
while (right > start && arr[right] >= arr[pivot]) { // 피봇보다 작은 데이터를 찾기
right--; // 오른쪽 구간 탐색 -> 피봇보다 작은 데이터 찾기
}
if (left > right) { // 구간이 엇갈렸다면 작은 데이터와 피봇을 교체
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
} else { // 구간이 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
// 피봇을 기준으로 분할 이후 왼쪽 공간과 오른쪽 공간 정렬
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
System.out.println(Arrays.toString(arr));
}
}
/*
[15, 93, 63, 70, 11, 94, 89, 13, 69, 82] // 처음 상태
[11, 13, 15, 70, 63, 94, 89, 93, 69, 82]
[11, 13, 15, 63, 69, 70, 89, 93, 94, 82]
[11, 13, 15, 63, 69, 70, 82, 89, 93, 94]
[11, 13, 15, 63, 69, 70, 82, 89, 93, 94]
[11, 13, 15, 63, 69, 70, 82, 89, 93, 94]
[11, 13, 15, 63, 69, 70, 82, 89, 93, 94] // 정렬 결과
*/
퀵 정렬의 시간 복잡도와 공간 복잡도
시간 복잡도
- 평균 시간 복잡도: O(N log N)
- 비교 횟수: O(log N), 데이터의 개수가 N개일 때 N을 2^k 라고 가정한다. 만약 N이 16이면 2^4 이고, 2^4 → 2^3 → 2^2 → 2^1 → 2^0 순으로 줄어들어 순환 호출(재귀 호출)의 깊이가 4임을 알 수 있다. 이 식을 일반화하면 K = log N 임을 알 수 있다.
- 각 순환 호출의 비교 연산: O(N), 각 순환 호출에서 전체 데이터를 대부분 비교해야 하므로 평균 N번의 비교가 이루어진다.
- 총 시간 복잡도 = 비교 횟수 * 비교할 때 드는 시간 = O(N) * O(log N) = O(N log N)
- 최악의 경우: O(N^2)
- 이미 정렬되어 피봇이 되는 맨 앞의 데이터가 가장 큰 수이거나 가장 작은 수 일때 최악의 경우가 발생한다.
- 비교 횟수: O(N)
- 각 순환 호출의 비교 연산: O(N)
- 총 시간 복잡도 = 비교 횟수 * 비교할 때 드는 시간 = O(N) * O(N) = O(N^2)
공간 복잡도
- 주어진 배열 안에서 swap을 통해 연산이 수행된다.
- 총 공간 복잡도: O(N), 배열의 크기
- 크기가 100인 int 배열이 주어지면 400 bytes의 메모리가 필요
퀵 정렬의 장점과 단점
- 장점
- 다른 정렬 알고리즘과 비교해 효율적이다. (평균 시간 복잡도 O(N log N))
- 배열 안에서 교환하는 방식으로 다른 메모리 공간이 필요하지 않다
- 단점
- 불안정 정렬(Unstable Sort): 동등한 위상의 원소들의 순서 관계가 보존되지 않는다.
- 이미 정렬된 데이터가 입력되었을 때 매우 비효율적이다.
📌 계수 정렬(Count Sort)
- 계수 정렬(Count Sort): 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
- 데이터의 크기가 N, 최대값이 K일 때 최악의 경우에도 O(N + K)를 보장
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용(실수형 데이터는 사용할 수 없는 정렬 알고리즘)
- 가장 큰 데이터와 가장 작은 데이터의 차이가 10^6을 넘어가지 않을때 효과적
- why? 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문에 백만개가 넘어가면 메모리 낭비가 심함
- 데이터의 처음부터 마지막 까지 각 값을 확인하며 생성한 배열에 갯수를 count해 준다.
- [3, 1, 9, 3, 2, 1] 이면 cnt[1] = 2, cnt[2] = 1, cnt[3] = 2, cnt[9] = 1
public class CountSort {
static int getMax(int[] arr) {
int max = -1;
for (int num : arr) {
max = Math.max(max, num);
}
return max;
}
static void countSort(int[] arr) {
int max = getMax(arr); // 주어진 데이터의 최대값을 찾는다
int[] cnt = new int[max + 1]; // 갯수를 저장할 배열, cnt[i]는 숫자 i의 갯수
for (int i = 0; i < arr.length; i++) { // 데이터를 순회하며 갯수를 count
cnt[arr[i]] += 1;
}
System.out.print("정렬 완료: [");
for (int i = 0; i <= max; i++) { // 0 부터 최대값 까지 차례대로
for (int j = 0; j < cnt[i]; j++) { // 그 갯수만큼 출력
System.out.print(i + ", ");
}
}
System.out.print("]");
}
}
계수 정렬의 시간 복잡도와 공간 복잡도
시간 복잡도
- 총 시간 복잡도: O(N + K)
- N은 데이터의 크기, K는 데이터의 최대값
- 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작
공간 복잡도
- 총 공간 복잡도: O(N + K)
- 주어진 배열 O(N) + 생성한 배열 O(K) = O(N + K)
댓글남기기