[CS50] 알고리즘: 정렬 알고리즘의 실행시간
❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.
여태까지 배운 선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실행시간은 각각 어떻게 되는지 정리해 보겠습니다.
여기서 버블 정렬을 좀 더 잘 할 수 있는 방법을 알아보겠습니다.
만약 정렬이 모두 되어 있는 숫자 리스트가 주어진다면 어떨까요?
원래 의사 코드는 아래와 같습니다.
Repeat n–1 times // ✅
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
여기서 안쪽 루프에서 만약 교환이 하나도 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황일 것입니다.
따라서 바깥쪽 루프를 ‘교환이 일어나지 않을때’까지만 수행하도록 다음과 같이 바꿀 수 있습니다.
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)이 됩니다.
상황에 따라서는 선택 정렬보다 더 빠른 방법이 되는 것이죠.
생각해보기
선택 정렬의 실행 시간의 하한도 버블 정렬처럼 더 단축시킬 수 있을까요?
- 선택 정렬의 하한은 단축시킬 수 없습니다
💥 선택정렬에서 'Repeat until no swaps'를 적용할 수 없는 이유는?
n회전때 swap이 일어나지 않았다는 의미는,
n번째 원소가 [n-1, 끝] 구간에서 최솟값이라는 의미일 뿐(-> 전체가 정렬되었다고는 볼 수 없다)이므로 버블정렬과 같은 방법을 적용하기는 어렵다.
(ex. 1 9 8 7 -> 1회전때 swap 없지만 전체 정렬이 아님)
💛 개인 공부 기록용 블로그입니다. 👻