4: 알고리즘-6(정렬 알고리즘의 실행시간)

앞에 Big Ω 표기에서 버블정렬의 하한은 Ω(n^2)이지만 이것을 개선할 여지가 있음

원래 버블 정렬의 의사코드

 

Repeat n–1 times       For i from 0 to n–2         If i'th and i+1'th elements out of order             Swap them

여기서 안쪽 루프에서 만약 교환이 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황

따라서 바깥쪽 루프를 ‘교환이 일어나지 않을 때’까지만 수행하도록 조건을 바꿀 수 있음

"만약 아무런 swap이 없다면 동작을 멈춘다"

 

Repeat until no swaps       For i from 0 to n–2         If i'th and i+1'th elements out of order             Swap them

이렇게 되면 버블정렬은 n-1번의 과정만 필요하게 됨 그래서 최선의 경우 버블 정렬의 하한선은 Ω(n)이 됨

---

실행시간을 나타내기 위해 사용되는 Big Ω 표기

 

Ω(n^2): 선택정렬

Ω(n log n)

Ω(n): 버블정렬

Ω(log n)

Ω(1):선형검색, 이진검색

 

https://everysmallstep.tistory.com/27

4: 알고리즘-4(버블 정렬:Bubble Sort)

https://www.boostcourse.org/cs112/joinLectures/41307

모두를 위한 컴퓨터 과학 (CS50 2019)