버블 정렬(Bubble Sort)
인접한 데이터를 비교하며 자리를 바꾸는 방식으로, 구현은 쉽지만 속도는 느린 알고리즘이다. 시간 복잡도는 O(n²)이다.
자바 코드
public static void bubbleSort(int[] arr) {
for (int i = 1; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i; j++) {
if(arr[j] > arr[j + 1]){
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {3, 5, 2, 7, 1, 4};
bubbleSort(arr);
System.out.println("버블 정렬: " + Arrays.toString(arr));
}삽입 정렬(Insertion Sort)
앞의 데이터를 정렬하면서 삽입 위치를 찾아 정렬하는 방식이다. 삽입 정렬 역시 구현은 쉽지만 속도는 느리다. 시간 복잡도는 O(n²)이다.
자바 코드
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if(arr[j] < arr[j - 1]){
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
}else{
break;
}
}
}
}
public static void main(String[] args) {
arr = new int[]{3, 5, 2, 7, 1, 4};
insertionSort(arr);
System.out.println("삽입 정렬: " + Arrays.toString(arr));
}선택 정렬(Selection Sort)
최소 또는 최대값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식이다. 버블 정렬과 삽입 정렬과 마찬가지로 구현은 쉽지만 속도는 느리다. 시간 복잡도는 O(n²)이다.
자바 코드
private static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[min]){
min = j;
}
}
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
public static void main(String[] args) {
arr = new int[]{3, 5, 2, 7, 1, 4};
selectionSort(arr);
System.out.println("선택 정렬: " + Arrays.toString(arr));
}합병 정렬(Merge Sort)
배열을 계속 분할하여 정렬하고 합병하는 방식으로, 비교적 빠른 정렬 알고리즘 중 하나다. 시간 복잡도는 O(nlogn)이다.
자바 코드
import java.util.Arrays;
public class Main {
public static void mergeSort(int[] arr, int[] tmp, int left, int right) {
if(left < right){
int mid = (left + right) / 2;
mergeSort(arr, tmp, left, mid);
mergeSort(arr, tmp, mid + 1, right);
merge(arr, tmp, left, right, mid);
}
}
public static void merge(int[] arr, int[] tmp, int left, int right, int mid) {
int p = left;
int q = mid + 1;
int idx = p;
while(p <= mid || q <= right){
if(p <= mid && q <= right){
if(arr[p] <= arr[q]){
tmp[idx++] = arr[p++];
}else{
tmp[idx++] = arr[q++];
}
}else if(p <= mid && q > right){
tmp[idx++] = arr[p++];
}else{
tmp[idx++] = arr[q++];
}
}
for (int i = left; i <= right; i++) {
arr[i] = tmp[i];
}
}
public static void main(String[] args) {
int[] arr = {3, 5, 2, 7, 1, 4, 6};
int[] tmp = new int[arr.length];
mergeSort(arr, tmp, 0, arr.length - 1);
System.out.println("합병 정렬: " + Arrays.toString(arr));
}
}
힙 정렬(Heap Sort)
힙 자료구조를 사용하여 정렬하는 방식으로, 시간 복잡도가 O(nlogn)이다. 효율적인 정렬 알고리즘 중 하나다.
자바 코드
import java.util.Arrays;
public class Main {
public static void heapSort(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, 0, i);
}
}
public static void heapify(int[] arr, int parentIdx, int size) {
int leftIdx = 2 * parentIdx + 1;
int rightIdx = 2 * parentIdx + 2;
int maxIdx = parentIdx;
if(leftIdx < size && arr[maxIdx] < arr[leftIdx]){
maxIdx = leftIdx;
}
if(rightIdx < size && arr[maxIdx] < arr[rightIdx]){
maxIdx = rightIdx;
}
if(parentIdx != maxIdx){
swap(arr, maxIdx, parentIdx);
heapify(arr, maxIdx, size);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
// Test code
int[] arr = {3, 5, 2, 7, 1, 4, 6};
heapSort(arr);
System.out.println("힙 정렬: " + Arrays.toString(arr));
}
}
퀵 정렬(Quick Sort)
임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식이다. 평균적으로는 빠르지만 최악의 경우에는 시간 복잡도가 O(n²)이 될 수 있다.
자바 코드
import java.util.Arrays;
public class Main3 {
public static void quickSort(int[] arr, int left, int right) {
if(left >= right){
return;
}
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left;
int j = right;
while(i < j){
while(arr[j] > pivot && i < j){
j--;
}
while(arr[i] <= pivot && i < j){
i++;
}
swap(arr, i, j);
}
swap(arr, left, i);
return i;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {6, 2, 7, 9, 4, 5, 8};
quickSort(arr, 0, arr.length - 1);
System.out.println("퀵 정렬: " + Arrays.toString(arr));
}
}
트리 정렬(Tree Sort)
이진 탐색 트리를 사용하여 정렬하는 방식이다. 시간 복잡도는 O(nlogn)이다.
기수 정렬(Radix Sort)
낮은 자릿수부터 정렬하는 방식으로, 시간 복잡도는 O(dn)이다. 여기서 d는 최대 자릿수를 나타낸다.
자바 코드
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void radixSort(int[] arr) {
ArrayList<Queue<Integer>> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(new LinkedList<>());
}
int idx = 0;
int div = 1;
int maxLen = getMaxLen(arr);
for (int i = 0; i < maxLen; i++) {
for (int j = 0; j < arr.length; j++) {
list.get((arr[j] / div) % 10).offer(arr[j]);
}
for (int j = 0; j < 10; j++) {
Queue<Integer> queue = list.get(j);
while(!queue.isEmpty()){
arr[idx++] = queue.poll();
}
}
idx = 0;
div *= 10;
}
}
public static int getMaxLen(int[] arr){
int maxLen = 0;
for (int i = 0; i < arr.length; i++) {
int len = (int) Math.log10(arr[i]) + 1;
if(maxLen < len){
maxLen = len;
}
}
return maxLen;
}
public static void main(String[] args) {
int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
radixSort(arr);
System.out.println("기수 정렬: " + Arrays.toString(arr));
}
}
계수 정렬(Counting Sort)
숫자 간의 비교 없이 카운트를 세어 정렬하는 방식으로, 시간 복잡도는 O(n + k)이다. 여기서 k는 정렬 대상 데이터 중 최대값을 나타낸다.
자바 코드
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
public class Main2 {
public static void countingSort(int[] arr) {
// int max = Arrays.stream(arr).max().getAsInt();
// int[] cntArr = new int[max + 1];
//
// for (int i = 0; i < arr.length; i++) {
// cntArr[arr[i]]++;
// }
//
// int idx = 0;
// for (int i = 0; i < cntArr.length; i++) {
// while(cntArr[i] > 0){
// arr[idx++] = i;
// cntArr[i] -= 1;
// }
// }
HashMap<Integer, Integer> map = new HashMap<>();
for (int item : arr) {
map.put(item, map.getOrDefault(item, 0) + 1);
}
int idx2 = 0;
ArrayList<Integer> list = new ArrayList<>(map.keySet());
Collections.sort(list);
for (int i = 0; i < list.size(); i++) {
int cnt = map.get(list.get(i));
while(cnt > 0){
arr[idx2++] = list.get(i);
cnt--;
}
}
}
public static void main(String[] args) {
int[] arr = {10, 32, 10, 27, 32, 17, 99, 56};
countingSort(arr);
System.out.println("계수 정렬: " + Arrays.toString(arr));
}
}셸 정렬(Shell Sort)
삽입 정렬의 개선된 버전으로, 시간 복잡도는 평균적으로 O(nlogn)이다.
자바 코드
import java.util.Arrays;
public class Main3 {
public static void shellSort(int[] arr) {
int gap = arr.length / 2;
for (int g = gap; g > 0; g /= 2) {
for (int i = g; i < arr.length; i++) {
int tmp = arr[i];
int j = 0;
for (j = i - g; j >= 0; j -= g) {
if(arr[j] > tmp){
arr[j + g] = arr[j];
}else{
break;
}
}
arr[j + g] = tmp;
}
}
}
public static void main(String[] args) {
int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
shellSort(arr);
System.out.println("셸 정렬: " + Arrays.toString(arr));
}
}
발전하는 백엔드 개발자