Adaptivity
Coddy의 버블 정렬 코스 레슨 — 11개 중 6번째.
우리는 버블 정렬 알고리즘의 시간 복잡도가 O(n2) 라는 점에 대해 논의했습니다. 하지만 만약 배열이 이미 정렬되어 있다면 어떨까요? 그 경우에도 여전히 O(n2)의 실행 시간이 소요될 것입니다.
적응성(Adaptivity)이란 무엇일까요?
적응형 알고리즘은 주어진 입력 시퀀스에 따라 동작을 변경하는 알고리즘입니다.
그렇다면, 버블 정렬은 적응형일까요?
네, 우리는 버블 정렬 알고리즘을 적응형으로 만들 수 있습니다. 버블 정렬 알고리즘이 적응형이 되도록 최악의 경우 실행 시간은 O(n2)이고, 최선의 경우는 O(n)이 되도록 작성해야 합니다. 여기서 최선의 경우란 배열이 이미 정렬되어 있는 경우를 의미합니다.
우리는 불리언(boolean) 플래그 변수를 사용하여 while 루프를 제어함으로써, 배열이 이미 정렬되었다면 알고리즘이 조기에 종료되도록 할 것입니다.
while(flag)
{
//code
}
배열이 정렬될 때까지 패스(pass)를 반복해야 합니다. 우리는 이미 스왑(swap) 횟수를 세는 방법을 배웠으므로, 플래그를 구현하여 해당 패스에서 스왑이 필요하지 않은지 확인한 다음 루프를 중단할 수 있습니다.
챌린지
중급배열과 배열의 크기를 인자로 받는 ad_bubblesort라는 이름의 함수를 생성하세요. 적응형 버블 정렬(adaptive bubble sort) 알고리즘을 수행하세요. 교환 여부를 확인하기 위해 flag라는 이름의 변수를 사용하는 것을 잊지 마세요.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// 여기에 코드를 작성하세요
*returnSize = n;
return arr;
}
버블 정렬의 모든 레슨
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm