철학과 학생의 개발자 도전기

1. 개요 계수 정렬은 비교를 사용하지 않는 정렬 알고리즘이다. 정렬해야 할 요소들의 값 범위가 제한적일 때 효과적이다. 정렬하려는 입력 배열에서 각 요소의 발생 횟수를 세고, 이 정보를 바탕으로 각 요소가 정렬된 배열에서 어디에 위치해야 하는지를 결정한다. 작은 정수를 정렬할 때 높은 성능을 보이며, 복잡한 비교 연산 없이 빠르게 정렬을 수행할 수 있다. 2. 특징 시간복잡도: O(n+k) n은 배열의 크기, k는 입력 데이터의 최대값 공간 복잡도: O(k) 각 입력 데이터의 발생 횟수를 저장하기 위한 배열 필요 3. 코드 import java.util.Arrays; public class CountingSortTest { public static void main(String[] args) { int..

1. 개요 숫자의 각 자릿수를 기준으로 정렬하는 비교 기반 정렬 알고리즘이 아닌, 분배식 정렬 방법이다. 데이터의 자릿수를 기준으로 순차적으로 정렬을 진행하며, 가장 낮은 자릿수(1의 자리)부터 시작하여 가장 높은 자릿수까지 차례대로 정렬하는 과정을 거친다. 데이터의 크기에 비해 상대적으로 자릿수가 작을 때 좋은 성능을 보인다. 2. 특징 시간복잡도: O(d(n+k)) n은 정렬할 요소의 개수, d는 자릿수의 개수, k는 기수(10진수인 경우 10) 공간 복잡도: O(n + k) 기수 정렬은 정렬을 위한 임시 배열 공간을 필요로 한다. 자릿수가 클수록 메모리 사용량이 많아진다. 3. 코드 import java.util.Arrays; public class RadixSortTest { public stat..

1. 개요 완전이진트리를 기반으로 하는 정렬 알고리즘이다. 최대 힙을 구성한 후, 최대값을 차례대로 뽑으면서 정렬한다. 퀵 정렬과 병합 정렬의 성능이 더 좋아서 자주 사용되지는 않는다. 2. 특징 불안정 정렬이다. 시간복잡도: O(NLogN) 3. 코드 import java.util.Arrays; public class HeapSortTest { public static void main(String[] args) { int[] nums = {3, 2, 7, 5, 11, 12, 1}; heapSort(nums); System.out.println(Arrays.toString(nums)); } private static void heapSort(int[] arr) { int n = arr.length; f..

1. 개요 분할 정복 전략을 사용한다. 배열을 절반씩 분할하고 정렬한다. 정렬된 부분 배열을 하나로 병합한다. 부분 배열에 추가적인 메모리를 할당한다. 2. 특징 속도가 빠르다. 안정 정렬이다. 시간복잡도: O(NLogN) 순차적인 비교를 하기 때문에 연결 리스트에서 사용하기 좋다. 용량이 큰 데이터를 정렬할 때, 메모리 문제가 발생할 수 있다. 3. 코드 import java.util.Arrays; public class MergeSortTest { public static void main(String[] args) { int[] nums = { 3, 2, 7, 5, 11, 12, 1 }; mergeSort(nums, 0, nums.length - 1); System.out.println(Arrays..

1. 개요 분할 정복 전략을 사용하는 알고리즘이다. 주어진 배열에서 pivot을 설정하고 두 개의 부분 배열로 나눈다. pivot보다 작은 값은 pivot의 왼쪽 배열에, pivot보다 큰 값은 pivot의 오른쪽 배열에 둔다. 각 배열에 대해 재귀적으로 정렬을 수행한다. pivot 선택 방식에 따라 속도가 달라질 수 있다. 2. 특징 속도가 빠르다. 불안정 정렬이다. 시간복잡도: 평균 O(NLogN) / 최악 O(N^2) 배열이 이미 정렬되어 있는 경우(역순 포함), pivot이 가장 크거나 작은 값이 선택된다. 이 경우, 배열 분할이 불균형하게 발생하여 O(N^2)의 시간복잡도를 가진다. 3. 코드 import java.util.Arrays; public class QuickSortTest { pub..

1. 개요 선택 정렬과 유사하지만 더 효율적인 알고리즘이다. 정렬할 원소를 선택하고 앞의 원소들과 비교하여 알맞은 위치에 삽입한다. 이미 정렬되어 있는 경우, O(N)의 시간복잡도를 가진다. 2. 특징 구현이 단순하다. 제자리 정렬이다. 안정 정렬이다. 시간복잡도: O(N^2) / 최선의 경우 O(N) 다른 O(N^2) 알고리즘에 비해 빠르다. 3. 코드 import java.util.Arrays; public class InsertionSortTest { public static void main(String[] args) { int[] nums = { 3, 2, 7, 5, 11, 12, 1 }; insertionSort(nums); System.out.println(Arrays.toString(num..

1. 개요 자리를 먼저 정하고 들어갈 원소를 탐색한다. 한 번의 사이클이 끝나면 맨 앞자리부터 값이 확정된다. 2. 특징 구현이 간단하다. 교환하는 방식이기 때문에 추가적인 메모리를 사용하지 않는다. => 제자리 정렬(in-place sorting) 거품 정렬에 비해 swap 연산 횟수가 적다. 불안정 정렬이다. 시간복잡도: O(N^2) 3. 코드 import java.util.Arrays; public class SelectionSortTest { public static void main(String[] args) { int[] arr = {3, 7, 2, 5, 1, 10}; selectionSort(arr); System.out.println(Arrays.toString(arr)); } public..

1. 개요 인접한 두 원소를 비교하여 필요한 경우 자리를 교환한다. 한 번의 사이클이 끝나면 가장 큰 원소가 맨 뒤로 간다. (오름차순 기준) 찾는 값이 거품처럼 나온다고 해서 거품 정렬이다. 2. 특징 구현이 간단하다. 교환하는 방식이기 때문에 추가적인 메모리를 사용하지 않는다. => 제자리 정렬(in-place sorting) 안정 정렬(Stable Sort)이다. => 중복된 값을 입력 순서와 동일하게 유지 시간복잡도: O(N^2) 3. 코드 import java.util.Arrays; public class BubbleSortTest { public static void main(String[] args) { int[] arr = {3, 7, 2, 5, 1, 10}; bubbleSort(arr);..