![]()
팀 정렬 (Tim Sort) 팀 정렬은 Java의 객체 배열을 정렬할 때 사용하는 알고리즘 입니다. 팀 정렬은 삽입 정렬과 병합 정렬의 강점을 결합했습니다. 삽입 정렬의 작은 데이터 세트에 대해 효율적인 면과 병합 정렬의 큰 데이터 세트에 효율적인 면을 합친 것입니다. 팀 정렬은 배열을 여러 부분으로 나눕니다. 이렇게 나누어진 부분을 run이라고 하며 각 run에서는 삽입 정렬로 정렬합니다. 정렬된 run들은 병합 정렬로 합치면서 정렬합니다. 이런 식으로 작은 부분에는 삽입 정렬을 큰 부분에서는 병합 정렬을 이용해 각 정렬들의 강점을 활용하여 정렬합니다. 시간 복잡도 평균 경우 : O(n log n) 최악 경우 : O(n log n) 평균, 최악 모두 O(n log n)으로 일정한 성능을 보입니다. 또한..
![]()
듀얼 피벗 퀵 정렬 (Dual Pivot Quick Sort) 듀얼 피벗 퀵 정렬은 Java의 Arrays.sort() 정렬 메소드에 사용되며 원시 타입(primitive type, int[], long[]) 배열을 정렬할 때 사용합니다. 퀵 정렬 보다 더 효율적이며, 두 개의 피벗을 사용하여 배열을 세 부분으로 나누어 정렬합니다. 시간 복잡도 : O(n log n) 최악의 경우 O(n^2) 듀얼 피벗 퀵소트는 원시 타입의 배열을 정렬할 때 사용합니다. 객체 타입일 때는 팀소트를 사용합니다. 원시 타입 배열 특징 원시 타입은 메모리 크기가 작아서 값 복사나 이동이 빠릅니다. 이로 인해 값의 비교가 빠릅니다. 원시 타입 배열들은 메모리에 연속적으로 저장하여 메모리에 빠르게 접근할 수 있습니다. 듀얼 피벗 ..
![]()
힙 정렬 (Heap Sort) 힙 정렬은 효율적인 비교 기반 정렬 알고리즘입니다. 힙 정렬은 최대 힙, 최소 힙이라는 자료구조를 사용합니다. 힙은 완전 이진 트리의 일종으로, 힙의 모든 부모 노드는 그 자식 노드보다 크거나 같은 값을 가지는 특성을 가집니다. 이 특성을 이용하여 배열을 힙으로 구성하여 최소값을 찾고 남은 배열을 또 힙 구조로 만들어 최소값을 찾아서 정렬을 완성합니다. 시간 복잡도 평균 : O(n log n) 최악의 경우 : O(n log n) 힙에서 자료의 추가, 삭제는 O(log n)입니다. 이를 배열을 순회하면서 일어납니다. 배열의 순회는 O(n)으로 최종적으로 시간 복잡도는 O(n log n)이 됩니다. 장점 일정한 성능 : 데이터의 분포에 상관없이 일정한 성능을 보장합니다. O(n..
![]()
병합 정렬 (Merge Sort) 병합 정렬은 분할 정복 알고리즘으로 평균적으로 효율적인 정렬 방법입니다. 병합 정렬은 배열을 더 이상 나눌 수 없을 때까지 반으로 나눕니다. 나눈 배열을 정렬하고 병합하면서 전체 배열의 정렬을 완성합니다. 시간 복잡도 : O(n log n) 반으로 나누면서 진행하기 때문에 시간 복잡도는 O(n log n)입니다. 최악의 상황에서도 O(n log n)입니다. 평균적인 속도는 퀵 정렬 > 힙 정렬 > 병합 정렬 입니다. 장점 안정적인 정렬 : 같은 값의 요소가 정렬 후에도 순서를 유지합니다. 일정한 시간 복잡도 : 모든 경우에 대해 O(n log n)입니다. 데이터에 관계없이 일정한 성능을 보장합니다. 대규모 데이터에 효율적 : 크기가 큰 데이터에서 효율적입니다. 단점 추가..
![]()
퀵 정렬 Quick Sort 퀵 정렬은 평균적으로 매우 빠른 성능을 보이는 비교 기반 정렬 알고리즘 입니다. 분할 정복 전략을 사용하여 피벗(Pivot)을 기준으로 범위를 나누어 가면서 정렬을 진행합니다. 배열의 한 요소를 기준이 되는 피벗으로 삼아 피벗을 기준으로 작은 것과 큰 것을 정렬합니다. 나누어진 두 부분에 또 피벗을 잡고 정렬을 하고 이 과정을 반복하여 정렬을 완성합니다. 시간 복잡도 : O(n log n), 최악의 경우는 O(n^2) 입니다. 퀵 정렬은 빠른 정렬 알고리즘으로 일반적인 상황일 때 속도는 다음과 같습니다. 퀵 정렬 > 힙 정렬 > 병합 정렬 이 순서는 평균적인 상황이고 데이터 특성과 구현 방식에 따라 달라질 수 있습니다. 장점 제자리 정렬(in-place sorting) : 원..
![]()
기수 정렬 Radix Sort 기수 정렬은 숫자나 문자에서 각 자릿수 별로 정렬하여 비교 없이 정렬하는 알고리즘입니다. 자릿수 별로 정렬을 하며, 낮은 자릿수부터 높은 자릿수까지 정렬하여 정렬을 완성합니다. 기수 정렬은 같은 값의 요소들의 순서가 정렬 후에도 유지되는 안정적인 정렬입니다. 시간 복잡도 : O(k(n + k)) n : 배열의 길이, k : 숫자의 최대 자릿수(기수) 장점 빠른 속도 : 데이터의 크기가 크고 자릿수가 많아질수록 효율적입니다. 안정적인 정렬 : 정렬 후에도 순서가 유지됨 단점 메모리 사용량 증가 : 정렬을 할 때, 추가 메모리가 필요하며 자릿수가 크고 배열이 클수록 메모리 사용량이 큽니다. 제한된 사용 조건 : 자릿수가 없는 것은 정렬할 수가 없습니다. (부동 소수점) 작동 원..
![]()
계수 정렬 (Counting Sort) 계수 정렬은 요소들을 직접 비교하지 않고 정렬하는 알고리즘으로 정수 정렬 알고리즘 중 하나입니다. 배열의 각각의 요소들의 수를 센 다음 조건에 맞춰 수를 배열하는 정렬하는 방식입니다. 원소들의 값이 특정 범위 내에 있을 때 효율적으로 작동할 수 있습니다. 시간 복잡도 : O(n + k) n : 배열의 크기, k : 가장 큰 수 장점 시간 복잡도가 빠를 수 있다. 특정한 상황에서는 비교 기반 정렬 방법보다 빠를 수 있습니다. 안정적인 정렬이다. 동일한 값을 가진 원소들의 상대적 순서가 유지됩니다. 단점 공간 복잡도가 높다. 추가적인 공간이 필요하기 때문이다. (카운트 배열과 정렬된 배열) 제한 조건 : 원소들이 정수여야 하며 작은 범위여야 효과적이다. 계수 정렬을 사..
![]()
삽입 정렬 (Insertion Sort) 기초적인 정렬 방법 중 하나 입니다. 인덱스의 값이 왼쪽보다 작다면 위치를 교환합니다. 이 과정을 왼쪽보다 클 때까지 반복합니다. 이 과정을 반복하면 왼쪽에 정렬된 부분이 생깁니다. 정렬된 부분에 새로운 값이 삽입되므로 삽입 정렬이라 합니다. 삽입된 값은 왼쪽이 자기보다 작을 때까지 교환합니다. 이 과정을 통해 자기 자리를 찾아 정렬을 완성합니다. 시간 복잡도는 O(N^2) 입니다. 버블 정렬, 선택 정렬 보다 평균적인 정렬 속도가 빠릅니다. 평균적인 정렬 속도 : 버블 < 선택 < 삽입 삽입 정렬은 작은 데이터셋에서 효율적입니다. 또한, 동일한 요소가 있을 경우 정렬한 후에 순서가 지켜져 안정적입니다. 삽입 정렬은 이후에 팀소트(TimSort)에서 작은 크기로 ..
![]()
선택 정렬 (Selection Sort) 기초적인 정렬 방법 중 하나입니다. 배열에서 가장 작은 값을 찾아서 맨 앞에 숫자와 교환합니다. 이 작업을 반복하여 앞에서부터 작은 값을 채워 정렬을 완성합니다. 가장 작은 값을 선택해서 선택 정렬 입니다. 시간 복잡도는 O(N^2) 입니다. 버블 정렬 보단 빠르고 삽입 정렬 보단 느립니다. 평균적인 정렬 속도 : 버블 < 선택 < 삽입 선택 정렬은 이해하기 쉽고 구현하기 간단하지만 효율성은 낮은 편입니다. 각 요소를 나머지 모든 요소와 비교해야 하기 때문입니다. 대규모 데이터셋에는 효과적이지 않고 작은 데이터셋에서 사용합니다. 동작 과정 시간 복잡도 : O(n^2) 1. 최소값 탐색 : 주어진 배열에서 최소값을 찾습니다. 2. 최소값과 교환: 배열의 첫 번째 위..
![]()
버블 정렬 (Bubble Sort) 기초적인 정렬 방법 중 하나입니다. 큰 값이 끝으로 가는 것이 거품처럼 피어오른다고 해서 버블 정렬이라고 합니다. 시간 복잡도는 O(N^2) 이고 느린 편에 속합니다. 버블 정렬은 선택 정렬, 삽입 정렬 보다 느립니다. 평균적인 정렬 속도 : 버블 < 선택 < 삽입 버블 정렬은 구현이 간단하지만 효율성이 낮은 편입니다. 각 요소가 평균적으로 여러 번 비교되고 이동해야 하기 때문입니다. 동작 과정 시간 복잡도 : O(n^2) 1. 비교화 교환 : 배열을 순회하면서 현재 인덱스의 값과 다음 인덱스의 값을 비교하여 오른쪽이 큰 값이 오도록 교환합니다. 2. 반복 : 이 과정을 한 번 수행하면 가장 큰 값이 배열의 끝으로 버블링(상승)하게 됩니다. 이 과정을 반복합니다. 3...
![]()
정렬이란? 정렬이란 데이터를 특정 기준에 따라 순서대로 나열한 것 입니다. 정렬이 중요한 이유는 데이터를 정렬하면 이진 탐색을 할 수 있게 되기 때문입니다. 이진 탐색은 절반씩 탐색하므로 전체를 탐색하는 선형 탐색 보다 압도적으로 빠르게 원하는 자료를 찾을 수 있습니다. 대신, 이진 탐색은 정렬된 배열에서만 사용할 수 있습니다. 이로 인해, 정렬 알고리즘이 중요해졌고 다양한 정렬 알고리즘이 등장했습니다. 정리 정렬이란 데이터를 특정 기준에 따라 순서대로 나열한 것 정렬을 하면 이진 탐색이 가능해져 검색 속도를 올릴 수 있다. 정렬 알고리즘의 종류 정렬 알고리즘의 종류는 다양하며, 각각의 알고리즘은 그 특성과 성능이 다르므로 주어진 환경에 맞게 적절한 알고리즘을 선택하는게 중요합니다. 다음은 정렬 알고리즘..
