정렬 알고리즘 종합 정리: 동작 원리와 구현 예시
1. 버블 정렬 (Bubble Sort)
이 알고리즘은 반복적으로 인접한 요소를 비교하고, 필요 시 교환하여 최댓값(또는 최솟값)을 배열의 끝으로 이동시킨다. 각 단계마다 하나의 정렬된 요소가 확정되며, 전체적으로 정렬된 상태가 되기까지 O(n²)의 시간 복잡도를 가진다. 최적화된 경우, 이미 정렬된 배열에 대해 O(n)까지 가능하지만, 추가적인 플래그 변수를 사용해야 한다.
...
10월 8일 13:10에 게시됨
정수 배열 정렬 및 선택 알고리즘 구현
O(n) 시간 복잡도로 정렬하기
주어진 배열은 1부터 n까지의 서로 다른 정수로 구성되어 있으며, 각 요소는 1 ≤ a[i] ≤ n 범위에 있다. 이 조건을 활용하여, 보조 배열에 직접 위치를 매핑함으로써 O(n) 시간 내에 오름차순 정렬을 수행할 수 있다.
void sortToPosition(int src[], int size, int dest[]) {
for (int idx = 0; idx < size; idx++) {
dest[ ...
6월 24일 23:23에 게시됨