나작코

셸 정렬(Shell Sort)이란 삽입 정렬의 약점을 보완한 정렬 방식입니다. 삽입 정렬은 오름차순 정렬 기준일 때 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환이 필요합니다. 셸 정렬은 이전의 모든 데이터와 비교하지 않고 일정 간격을 두고 비교합니다. 알고리즘 복잡도는 O(n^2)입니다. 간격 설정에 따라 최악의 경우 삽입 정렬과 동일할 수 있고, 일반적으로는 삽입 정렬보다 빠릅니다. 셸 정렬 구현 코드 public class Main { public static void shellSort(int[] array) { int gap = array.length / 2; for (int g = gap; g > 0; g /= 2) { for (int i = g; i < arra..

계수 정렬(Counting Sort)이란 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식입니다. 카운팅을 위한 메모리를 필요로 합니다. 알고리즘 복잡도는 O(n + k)입니다. k는 정렬 대상 데이터 중 최대 값을 의미합니다. 카운팅 테이블은 Array 자료구조로 되어 있습니다. 정렬되지 않은 데이터 10 32 10 27 32 17 99 56 ↓ 2 1 1 2 1 1 [0] […] [10] […] [17] […] [27] […] [32] […] [56] […] [99] ↓ 정렬이 끝난 데이터 10 10 17 27 32 32 56 99 계수 정렬 구현 코드 import java.util.Arrays; public class Main { public static void countingSort(int[]..

기수 정렬(Radix Sort)이란 낮은 자리 수부터 정렬하는 방식입니다. 각 원소 간 비교 연산을 하지 않아 빠른 대신에 기수 테이블을 위한 메모리를 필요로 합니다. 알고리즘 복잡도는 O(dn)입니다. d는 최대 자릿수를 의미합니다. 최악의 경우 원소의 개수보다 최대 자릿수가 더 클 수 있기 때문입니다. 기수 테이블은 queue 자료구조로 되어 있습니다. 정렬되지 않은 데이터 170 45 75 90 2 24 802 66 ↓ 170 90 2 802 24 45 75 66 ↓ 2 802 24 45 66 170 75 90 ↓ 정렬이 끝난 데이터 2 24 45 66 75 90 170 802 기수 정렬 구현 코드 import java.util.ArrayList; import java.util.LinkedList;..

퀵 정렬(Quick Sort)이란 임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식입니다. 알고리즘 복잡도는 기준 값이 최소값 또는 최대값으로 지정되는 경우에는 O(n^2)입니다. 그러나 평균적으로는 O(n log n)이며, 이보다 더 빠른 경우도 있습니다. 퀵 정렬 구현 코드 public class Main { public static void quickSort(int[] array, int left, int right) { if (left >= right) { return; } int pivot = partition(array, left, right); quickSort(array, left, pivot - 1); quickSort(array, pivot + 1, right);..

힙 정렬(Heap Sort)이란 힙 자료구조 형태의 정렬 방식입니다. 기존 배열을 최대 힙으로 구조 변경 후 정렬을 진행합니다. 알고리즘 복잡도는 O(n log n)입니다. 힙 정렬 구현 코드 public class Main { public static void heapSort(int[] array) { for (int i = array.length / 2 - 1; i >=0 ; i--) { heapify(array, i, array.length); } for (int i = array.length - 1; i > 0; i--) { swap(array, 0, i); heapify(array, 0, i); } } public static void heapify(int[] array, int parentIn..

합병 정렬(Merge Sort)이란 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식입니다. 알고리즘 복잡도는 O(n log n)입니다. 길이가 1인 배열 상태가 된 이후에는 인접한 부분끼리 값을 비교하여 정렬한 뒤 합칩니다. 데이터를 합치는 과정에서 이를 저장하는 메모리가 추가로 필요합니다. 그러나 속도는 이전의 버블 정렬, 삽입 정렬, 선택 정렬과 같은 정렬에 비해 빠릅니다. 과정은 다음 이미지과 같습니다. 합병 정렬 구현 코드 public class Main { public static void mergeSort(int[] array, int[] temp, int left, int right) { if (left < right) { int mid = (lef..

선택 정렬(Selection)이란 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식입니다. 알고리즘 복잡도는 O(n^2)입니다. 정렬되지 않은 데이터 15 11 1 3 8 ↓ 1 11 15 3 8 ↓ 1 3 15 11 8 ↓ 정렬이 끝난 데이터 1 3 8 11 15 선택 정렬 구현 코드(최솟값부터) pubilc class Main { public static void selectionSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { int min = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[min]) { min = j; } } int temp ..

삽입 정렬(Insertion Sort)이란 앞의 데이터를 정렬해가면서 삽입 위치를 찾아 정렬하는 방식입니다. 알고리즘 복잡도는 O(n^2)입니다. 앞의 원소부터 정렬하면서 비교하는 원소보다 클 경우에 비교를 중단하므로 버블 정렬보다는 빠른 편입니다. 정렬되지 않은 데이터 15 11 1 3 8 ↓ 11 15 1 3 8 ↓ 1 11 15 3 8 ↓ 1 3 11 15 8 ↓ 정렬이 끝난 데이터 1 3 8 11 15 삽입 정렬 구현 코드 pubilc class Main { public static void insertionSort(int[] array) { for (int i = 1; i 0; j--) { if (array[j] < a..

버블 정렬(Bubble Sort)이란 인접한 데이터를 비교하며 자리를 바꾸는 방식을 뜻합니다. 가장 큰 데이터를 맨 뒤로 보냅니다. 알고리즘 복잡도는 O(n^2)입니다. 정렬되지 않은 데이터 15 11 1 3 8 ↓ 11 1 15 3 8 ↓ 11 1 3 15 8 ↓ 11 1 3 8 15 ↓ 1 11 3 8 15 ↓ 1 3 11 8 15 ↓ 정렬이 끝난 데이터 1 3 8 11 15 버블 정렬 구현 코드 pubilc class Main { public static void bubbleSort(int[] array) { for (int i = 1; i ar..