[Week1] 정렬 1/2
거품정렬 (Bubble Sort)
정의
서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘
거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 거품 정렬이라고 이름 지어짐
Process
1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째와 세 번째 원소를 ... 이런 식으로 (마지막 - 1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
2. 1회전을 수행하고 나면가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제회된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
자바 코드
void bubbleSort(int[] arr) {
int temp = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length - i; j++) {
if (arr[j - 1] > arr[j]) {
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
1. i는 제외될 원소의 갯수를 의미. 1회전이 끝난 후, 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 하나씩 증가시켜준다.
2. 두번째 for문의 j는 비교할 index를 의미. j는 현재 인덱스는 현재 원소, j - 1은 이전 원소를 가리킨다.
3. arr[j] 와 arr[j - 1]을 비교해서 이전원소가 더 크면 자리를 교환해준다.
시간복잡도
(n - 1) + (n - 2) + ... + 2 + 1 → n(n - 1)/2 이므로 O(n^2)
정렬이 되어있든 안되어있든 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)로 같다.
공간복잡도
주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n)이다.
장점
- 구현이 매우 간단하고, 소스코드가 직관적이다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않는다. (제자리 정렬, in-place sorting)
- 안정 정렬이다. (Stable Sort)
※ 안정 정렬 : 중복된 값을 입력 순서와 동일하게 정렬하는 정렬 알고리즘 (삽입정렬, 병합정렬, 버블정렬)
불안정 정렬 : 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘 (퀵정렬, 선택정렬, 계수정렬)
단점
- 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로 비효율적이다.
- 정렬을 위해 교환 연산이 많이 일어난다.
선택정렬 (Selection Sort)
정의
Bubble Sort와 유사한 알고리즘으로,
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
※Selection Sort vs Insertion Sort
Selection Sort : 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것.
Insertion Sort : 원소를 선택하고 자리를 탐색하여 삽입하는 것.
Process
- 주어진 배열 중에 최솟값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
자바 코드
void selectionSort(int[] arr) {
int indexMin, temp;
for (int i = 0; i < arr.length - 1; i++) { // 1.
indexMin = i;
for (int j = i + 1; j < arr.length; j++) { // 2.
if (arr[j] < arr[indexMin]) { // 3.
indexMin = j;
}
}
// 4. swap(arr[indexMin], arr[i])
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
System.out.println(Arrays.toString(arr));
}
- 우선, 위치 (index)를 선택
- i + 1 번째 원소부터 선택한 1번에서 선택한 위치의 값과 비교
- 선택한 자리에 있는 값보다 arr[j]가 작으면, indexMin 값 갱신
- 2번 반복문이 끝난 뒤에는 indexMin값과 위치에 있는 값을 교환해준다.
시간복잡도
데이터의 개수가 n개라고 했을 때,
- 첫 번째 회전에서의 비교횟수 : 1 ~ (n - 1)
- 두 번째 회전에서의 비교횟수 : 2 ~ (n - 1)
- ...
- (n - 1) + (n - 2) + .. → n(n - 1)/2
n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다.
최선, 평균, 최악의 경우에도 모두 비교해야 하므로 시간복잡도는 동일하다.
공간복잡도
주어진 배열 안에서 교환을 통해 정렬 → O(n)
장점
- 알고리즘이 단순하다.
- Bubble Sort에 비해 교환 횟수가 적다.
- 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. (제자리 정렬, in-place sorting)
단점
- 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로 비효율적이다.
- 불안정 정렬이다.
삽입정렬 (Insertion Sort)
정의
손 안의 카드를 정렬하는 방법과 유사함
Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘
2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입
최선의 경우 O(n)이라는 빠른 효율성을 가짐 (→ 다른 정렬 알고리즘의 일부로 사용되기도 함)
Process
- 두 번째 위치의 값을 temp에 저장한다.
- temp 이전에 있는 원소들과 비교하며 삽입해나간다.
- 다음 위치의 값을 temp에 저장하고 반복한다.
자바 코드
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){ // 1.
int temp = arr[index];
int prev = index - 1;
while( (prev >= 0) && (arr[prev] > temp) ) { // 2.
arr[prev+1] = arr[prev];
prev--;
}
arr[prev + 1] = temp; // 3.
}
System.out.println(Arrays.toString(arr));
}
- 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에 두 번째 위치부터 탐색 시작
temp에 임시로 해당 위치 값을 저장하고 prev에는 이전 위치 값을 저장한다. - 이전 위치(인덱스)를 가리키는 prev가 음수가 되지 않고, temp 보다 크다면,
서로 값을 교환해주고 prev를 하나씩 앞으로 옮겨준다. - 2번에서 반복문이 끝나고 난 뒤, prev에는 현재 temp 값보다 작은 값들 중 제일 큰 값의 위치를 가르키게 된다.
따라서 prev + 1 자리에 temp 값을 삽입해준다.
시간복잡도
최악의 경우 Selection Sort 와 마찬가지로
(n - 1) + (n - 2) + ... → n(n - 1)/2
즉, O(n^2)의 시간복잡도를 가진다.
하지만, 모두 정렬이 되어있는 최적의 경우 한 번씩만 비교하게 되므로 O(n)의 시간복잡도를 가진다.
또한 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 탐색을 제외한 오버헤드가 매우 적기 때문에
현실적으로 최고의 정렬 알고리즘이 된다.
공간복잡도
주어진 배열 안에서 교환을 통해 정렬 → O(n)
장점
- 알고리즘이 단순하다.
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적이다.
- 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. (제자리 정렬, in-place sorting)
- 안정 정렬이다.
- 선택정렬이나 버블정렬 알고리즘에 비교하여 상대적으로 빠르다.
단점
- 시간복잡도가 최악, 평균의 경우 O(n^2)으로 비효율적이다.
- 배열의 길이가 길어질수록 비효율적이다.
퀵 정렬 (Quick Sort)
정의
분할 정복 방법을 통해 주어진 배열을 정렬
※ 분할 정복 (divide and conquer)
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
또한, Merge Sort와 달리 배열을 비균등하게 분할한다.
Process
- 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 배열을 나눈다.
이렇게 배열을 나누는 것을 분할 (Divide) 라고한다.
분할을 마친 뒤에 피벗을 더 이상 움직이지 않는다. - 분할 된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.
자바 코드
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int start, int end) {
// start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
if (start >= end)
return;
// 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
int pivot = start;
int lo = start + 1;
int hi = end;
// lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
// 서로 엇갈리게 될 경우 while문 종료
while (lo <= hi) {
while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
lo++;
while (hi > start + 1 && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
hi--;
if (lo > hi) // 엇갈리면 피벗과 교체
swap(arr, hi, pivot);
else
swap(arr, lo, hi); // 엇갈리지 않으면 lo, hi 값 교체
}
// 엇갈렸을 경우,
// 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
quickSort(arr, start, hi - 1);
quickSort(arr, hi + 1, end);
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Quick Sort 개선
피벗 값이 최소나 최대값으로 지정되어 파티션이 나누어지지 않았을 때, O(n^2)에 대한 시간복잡도를 가진다.
즉, 정렬된 알고리즘에서 O(n^2)의 시간복잡도를 가진다.
이때, 배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간복잡도 O(n log2 n)으로 개선할 수 있다.
하지만, 이 방법으로 개선한다고해도 최악의 시간복잡도가 O(n log2 n)이 되는 것은 아니다.
시간복잡도
최선의 경우 : O(n log2 n)
- 비교 횟수 (log2 n)
레코드의 개수 n이 2의 거듭제곱이라고 가정 했을 때, n = 2^3의 경우, 2^3 → 2^2 → 2^1 → 2^0의 순으로 줄어들어
순환 호출의 깊이가 3임을 알 수 있다. - 각 순환 호출 단계의 비교 연산 (n)
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.
따라서, 최선의 시간복잡도는
순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = n log2 n 이 된다.
최악의 경우 : O(n^2)
- 비교 횟수 (n)
레코드의 개수 n이 2의 거듭제곱이라고 가정했을 때, 순환 호출의 깊이는 n - 각 순환 호출 단계의 비교 연산 (n)
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.
따라서, 최악의 시간복잡도는
순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = n^2 이다.
평균의 경우 : O(n log2 n)
공간복잡도
주어진 배열 안에서 교환을 통해 정렬 → O(n)
장점
- 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라,
한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에
시간 복잡도가 O(n log2 n)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다. - 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. (제자리 정렬, in-place sorting)
단점
- 불안정 정렬이다.
- 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.