[CS50] 정렬 알고리즘의 실행시간

지금까지 정렬 알고리즘이나 검색 알고리즘을 공부하면서 실행 시간의 상한과 하한도 함께 배워봤습니다. 오늘은 각각의 실행시간을 비교해보면서 그 시간을 단축시킬 수 있는 방법이 있는지에 대해 공부해보도록 하겠습니다.

 

지금까지 선형 검색(탐색), 이진 검색(탐색), 버블 정렬, 선택 정렬의 실행시간을 Big-O와 Big-Ω로 나눠보면

 

- 실행시간의 상한

O(n^2) : 선택 정렬, 버블 정렬

O(n log n)

O(n) : 선형 검색

O(log n) : 이진 검색

O(1)

- 실행시간의 하한

Ω(n^2) : 선택 정렬, 버블 정렬

Ω(n log n)

Ω(n)

Ω(log n)

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

로 나눠볼 수 있습니다.

 

그런데 여기서 실행시간을 단축시킬수 있는 게 있을까요?? 생각해봅시다.

 

버블 정렬의 경우 지난 포스팅에서 정리했듯이 의사 코드로 표현하자면

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 swap 
	for i from 0 to n-2 
	if i`th and i+1`th elements out of order 
		Swap them

이렇게 교환이 일어나지 않을 때 즉 정렬이 완료된 상태일 때 버블 정렬의 하한은 Ω(n)이 됩니다.

상황에 따라서는 선택 정렬보다 더 빠른 방법이 될 수 있다는 것입니다.

상황에 따라서는

- 실행시간의 하한

Ω(n^2) : 선택 정렬

Ω(n log n)

Ω(n) : 버블 정렬

Ω(log n)

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

이 될 수 있습니다.

 

선택 정렬의 실행시간의 하한도 더 단축시킬 수 있을까요?

개인적인 생각이지만 선택 정렬은 교환 횟수는 최소화시켜주지만 처음부터 끝까지 모든 값들을 비교하며 최솟값을 계속 찾아야 하기 때문에 실행시간의 하한은 변함없이 Ω(n^2)이 될 것 같습니다.

혹시 방법이 있다면 댓글로 달아주시면 더 찾아보고 공부하겠습니다. ㅎㅎ

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.