버블정렬(Bubble Sort) 개선 코드

https://en.wikipedia.org/wiki/Bubble_sort 보통 c언어 책에서 소개되는 기본적인 버블정렬의 시간복잡도는 O(n^2)이다. best, worst, average 모두 O(n^2)으로 표현되지만, 정렬 상태를 체크하는 flag를 넣어줌으로써 best의 경우 O(n)으로 개선시킬 수 있다. 버블 정렬 best case가 O(n)인 이유: 교수님의 알쓸신잡 지식 void bubble_sort(int list[], int n) { int flag = 1; for (int i = n-1; flag > 0; i--) { flag = 0; for (int j = 0; j < i; j++) if (list[j] > list[j + 1] { swap(&list[j], &list[j + 1]); flag = 1; } } } 이미 정렬이 된 상태라면, 외부for문 1바퀴 돌고만 돌고 끝나게 된다.

성능 차이 비교 기존 코드 vs 개선된 코드 내부 반복문이 얼마나 반복되는지...