반응형
- 비효율 : 선택 정렬, 버블 정렬, 삽입 정렬
- 효율 : 합병 정렬, 퀵 정렬, 힙 정렬
선택 정렬
넣을 위치는 정해져있고 어떤 원소를 넣은지 선택하는 알고리즘
- 시간 복잡도: O(N^2)
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int tmp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = tmp;
}
}버블 정렬
인접한 두 원소를 검사하여 정렬하는 알고리즘, 마지막 인덱스부터 큰 수들을 나열합니다.
- 시간 복잡도: O(N^2)
public static void bubbleSort(int[] arr) {
int tmp = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length - i; j++) {
if (arr[j - 1] > arr[j]) {
tmp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = tmp;
}
}
}
}삽입 정렬
2번째 원소부터 시작하여 앞 원소들과 비교하여 삽입하는 정렬 알고리즘
- 시간 복잡도
- 최선: O(N)
- 평균,최악: O(N^2)
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i - 1;
//앞에 원소들 보다 삽입하려는 원소가 작으면 해당 원소들을 뒤로 미룬다.
while (0 <= j && tmp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
/**
* 반복문을 빠져나왔다는 것은 삽입하려는 원소가 앞에 원소들보다 크다는 것
*/
arr[j + 1] = tmp;
}
}합병 정렬
요소를 이분 분할하고, 다시 합병시키는 정렬 알고리즘
- 시간 복잡도: O(NlogN)
- 안정 정렬 (중복된 원소의 순서가 정렬 후에도 동일한 정렬)
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int leftIndex = left;
int rightIndex = (mid + 1);
int index = left;
/* *
* 분할한 배열들을 비교하며 더 작은 수를 sorted 배열에 채워넣는다.
* 한쪽 배열이 빌 때까지 반복
*/
while (leftIndex <= mid && rightIndex <= right) {
if (arr[leftIndex] < arr[rightIndex]) {
sorted[index++] = arr[leftIndex++];
}
else{
sorted[index++] = arr[rightIndex++];
}
}
/* *
* 왼쪽 부분 배열이 전부 비었으면
* 오른쪽 부분 배열의 나머지 원소들을 새 배열에 채워준다.
* 오른쪽 부분 배열이 전부 비었으면
* 왼쪽 부분 배열의 나머지 원소들을 새 배열에 채워준다.
*/
if (mid < leftIndex) {
while(rightIndex <= right) {
sorted[index++] = arr[rightIndex++];
}
} else {
while(leftIndex <= mid) {
sorted[index++] = arr[leftIndex++];
}
}
//분할된 배열을 담기 위한 임시 배열인 sorted를 원본 배열인 arr에 옮겨줍니다.
//이 부분은 merge안에 선언할 필요없이 마지막에 해주셔도 됩니다.
for (int i = left; i <= right; i++) arr[i] = sorted[i];
}퀵 정렬
분할 정복 방법을 통해 주어진 배열을 정렬하는 알고리즘
좀 더 자세하게 설명하자면 배열에서 하나의 원소(피벗이라 칭함)를 기준으로 배열의 길이가 1이 될때 까지 두 개의 부분 배열로 계속 나눈 후에 인접 부분 배열끼리 합치는 방식입니다.
이때 피벗을 무엇으로 선택하냐에 따라 구현 방법이 약간 달라집니다.(원리는 같아서 차이는 거의 없음)
피벗을 선택하는 경우의 수는 총 3가지로 가장 왼쪽 혹은 가장 오른쪽 원소를 피벗으로 선택하는 경우, 중간에 있는 원소를 피벗으로 선택하는 경우가 있습니다. 만약 퀵 정렬을 적용할 배열이 이미 오름차순 혹은 내림차순 정렬되어 있다면 가장 왼쪽 혹은 가장 오른쪽 원소를 피벗으로 선택한 경우 O(N^2) 시간복잡도를 갖게 될 것입니다. 때문에 중가 피벗을 선호합니다. 여기도 중간 피벗을 선택한 경우로 예제 코드를 작성하겠습니다.
- 시간 복잡도
- 평균, 최선: O(NlogN)
- 최악: O(N^2)
- 불안정 정렬, 단순 비교 정렬
- 합병 정렬과 달리 배열을 비균등하게 분할합니다.
- 특정 조건이 아닌 경우 같은 시간 복잡도(O(NlogN))을 갖는 정렬 알고리즘에 비해 빠릅니다. (ex. 합병 정렬)
public static void quickSort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int low, int high) {
if (low >= high) return;
int mid = partition(arr, low, high);
sort(arr, low, mid - 1);
sort(arr, mid, high);
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[(low + high) / 2];
while (low <= high) {
//pivot 왼쪽 원소들 중 pivot 보다 큰 요소
while (arr[low] < pivot) low++;
//pivot 오른쪽 원소들 중 pivot 보다 작은 요소
while (arr[high] > pivot) high--;
//low와 high이 교차하거나 넘지 않았다면 둘의 위치를 바꿔줍니다.
if (low <= high) {
if (low != high) {
swap(arr, low, high);
}
low++;
high--;
}
}
//분할 기준점 index 반환
return low;
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}힙 정렬
완전 이진 트리 형태인 힙 자료구조를 기반으로 한 정렬 알고리즘
힙 정렬로 만든 다음에 최대값을 순서대로 정렬하는 것이다. 기존에 있는 힙 자료구조를 통해 저장한 뒤 반환하면 될텐데 왜 따로 구현할까? 바로 추가적인 메모리를 생성하지 않고 바로 배열 안에서 정렬하기 위함입니다. 때문에 힙 정렬은, 최대 힙을 구현한 다음에 최대값(루트 노드)을 배열에 채워넣고 삭제하며 정렬하는 방법입니다.
- 시간 복잡도: O(NlogN)
public static void heapSort(int[] arr) {
int n = arr.length;
// 주어진 배열 최대힙으로 만들기
// 부모 노드 인덱스만 탐색!!
for (int i = (n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 최대값(루트노드)을 제외하고 최대힙 만들기
// 루트노드를 마지막 노드와 바꾸고 힙의 사이즈를 하나 낮춰서 최대힙 만듦
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
int curNode = i; // 현재 노드
int leftNode = i * 2 + 1; // 왼쪽 자식 노드.
int rightNode = i * 2 + 2; // 오른쪽 자식 노드.
// 왼쪽 자식 -> 오른쪽 자식 순으로 현재 노드를 비교하여 현재 노드보다 크면 swap
if (leftNode < n && arr[curNode] < arr[leftNode]) curNode = leftNode;
if (rightNode < n && arr[curNode] < arr[rightNode]) curNode = rightNode;
if (i != curNode) {
swap(arr, curNode, i);
// 현재 노드가 자식 노드보다 클때까지 반복
heapify(arr, n, curNode);
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}반응형