힙 정렬 (Heap Sort)힙 정렬은 힙(Heap) 자료구조를 이용한 정렬 알고리즘으로, 완전 이진 트리의 특성을 활용하여 데이터를 정렬. 힙 정렬은 선택 정렬의 확장으로 볼 수 있으며, 데이터를 효율적으로 정렬하기 위해 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 사용.동작 원리힙 생성 (Heapify):주어진 배열을 최대 힙(부모가 자식보다 크거나 같음) 또는 최소 힙(부모가 자식보다 작거나 같음)으로 변환.정렬:힙의 루트(최댓값 또는 최솟값)를 배열의 끝으로 이동하고, 힙 크기를 줄인다.줄어든 힙에 대해 다시 힙 구조를 유지하도록 정렬(Heapify).이 과정을 힙 크기가 1이 될 때까지 반복.특징시간 복잡도:최선/평균/최악: O(nlog⁡n)힙 구성: O(n), 삭제 및 정렬: ..

병합 정렬 (Merge Sort)병합 정렬은 분할 정복(Divide and Conquer) 알고리즘을 사용하는 정렬 기법으로, 배열을 재귀적으로 두 부분으로 나누고, 각각을 정렬한 뒤 병합(Merge)하여 정렬된 배열을 만드는 방식. 안정적이며, 정렬 성능이 O(nlog⁡n)으로 일정한 점에서 효율적.동작 원리분할 (Divide):배열을 두 개의 하위 배열로 분할.하위 배열의 크기가 1이 될 때까지 재귀적으로 반복.정복 (Conquer):두 개의 정렬된 하위 배열을 병합하여 하나의 정렬된 배열로 만든다.병합 (Merge):병합 과정에서 두 배열을 비교하며 작은 값을 먼저 결과 배열에 추가.특징시간 복잡도:최선/평균/최악: O(nlog⁡n) (데이터 분할 O(log⁡n), 병합 O(n))공간 복잡도: O(..

퀵 정렬 (Quick Sort)퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘의 한 종류로, 배열을 특정 기준(Pivot)을 중심으로 두 부분으로 나누고, 각각의 부분을 재귀적으로 정렬하는 방식. 일반적으로 매우 빠르고 효율적이기 때문에, 실무와 코딩 테스트에서 자주 사용.동작 원리배열에서 하나의 요소를 Pivot으로 선택.Partitioning:Pivot보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치.Pivot을 기준으로 왼쪽과 오른쪽 서브 배열을 나눈다.왼쪽과 오른쪽 서브 배열에 대해 재귀적으로 퀵 정렬을 수행.모든 배열이 정렬될 때까지 반복.특징시간 복잡도:평균: O(nlog⁡n)최선: O(nlog⁡n) (Pivot이 항상 중앙값일 때)최악: O(n^2) (Pivot이 최솟값 ..

삽입 정렬 (Insertion Sort)삽입 정렬은 정렬되지 않은 데이터를 하나씩 선택하여 이미 정렬된 부분에 적절한 위치를 찾아 삽입하는 방식으로 동작하는 간단한 정렬 알고리즘.동작 원리두 번째 요소부터 시작하여, 정렬된 부분의 적절한 위치에 삽입.모든 요소를 처리할 때까지 이 과정을 반복.특징시간 복잡도:최악/평균: O(n^2) (정렬되지 않은 배열의 경우)최선: O(n) (이미 정렬된 배열의 경우)공간 복잡도: O(1) (추가 메모리 사용 없음)안정적 정렬: 같은 값의 상대적인 순서가 유지.효율성: 데이터가 거의 정렬된 상태일 때 매우 효율적.예제 코드 (C++)오름차순 삽입 정렬#include #include using namespace std;void insertionSort(vector& ar..

선택 정렬 (Selection Sort)선택 정렬은 정렬되지 않은 데이터 중에서 가장 작은 값(또는 큰 값)을 선택하여 정렬된 부분의 맨 뒤에 추가하는 방식으로 동작하는 정렬 알고리즘. 간단하지만 비효율적이기 때문에 작은 데이터셋에서 주로 사용.동작 원리배열의 첫 번째 요소부터 마지막 요소까지 순차적으로 접근.현재 범위에서 가장 작은 값(또는 큰 값)의 인덱스를 찾는다.해당 값을 현재 범위의 첫 번째 요소와 교환.위 과정을 배열 전체에 대해 반복.특징시간 복잡도:최악/평균/최선: O(n^2)공간 복잡도: O(1) (추가 메모리 사용 없음)비교 횟수: 항상 n(n−1)/2번의 비교가 발생.비교 기반 정렬: 데이터의 크기를 비교하여 정렬.비안정적 정렬: 동일한 값의 상대적인 순서가 바뀔 수 있다.예제 코드 ..

버블 정렬 (Bubble Sort)버블 정렬은 가장 간단한 정렬 알고리즘 중 하나. 인접한 두 데이터를 비교하여 크기 순서에 맞지 않으면 자리를 바꾸는 방식으로, 가장 큰 값(또는 가장 작은 값)이 거품처럼 배열의 끝으로 올라간다고 해서 버블 정렬이라고 불린다.동작 원리배열의 첫 번째 요소부터 시작하여 인접한 두 값을 비교.두 값이 정렬 기준(오름차순 또는 내림차순)에 맞지 않으면 교환(swap).한 번의 반복이 끝나면 가장 큰 값(또는 가장 작은 값)이 배열의 맨 끝에 위치.위 과정을 배열의 크기만큼 반복하며, 매번 비교 범위는 하나씩 줄어든다.특징시간 복잡도:최악/평균: O(n^2)최선 (이미 정렬된 경우): O(n)공간 복잡도: O(1) (추가 메모리 사용 없음)안정적 정렬: 값이 같을 경우 원래의..