[CS50] 알고리즘 - 정렬 알고리즘(Bubble Sort, Selection Sort)

 

리스트에 대해 여러번 탐색을 해야하는 경우,
정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적이다.
빠른 검색으로 장기적인 이득을 볼 수 있다. 

 

버블 정렬(Bubble Sort)

• 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬한다.
• 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.

 

버블 정렬 알고리즘 예시

마치 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식이다.

 

 

버블 정렬 의사코드

Repeat n–1 times : n-1번 반복

    For i from 0 to n–2 : n-1번 반복 (0부터니까 n-2)

        If i'th and i+1'th elements out of order

            Swap them

=> 바깥 반복문은 n-1번 반복하고 안쪽 반복문도 n-1번 반복한다.

 

 

 

버블 정렬 시간 복잡도 

$$(n-1)×(n-1)  =  n^2-2n+1$$

 

버블 정렬 실행 시간의 상한 : O(n²)

• 최고차항이 n²이므로 O(n²)이다.

 

버블 정렬 실행 시간의 하한 : Ω(n²) ※ 위의 의사코드를 기준으로 했을 때

• 정렬이 되어 있는지 여부에 관계없이 반복문을 실행하며 비교를 해야 하므로 Ω(n²)이다.

 

☆ 정렬된 숫자 리스트가 주어졌다면 의사코드는 다음과 같이 바꿀 수 있다.

Repeat until no swaps : 교환이 일어나지 않을 때까지만 반복

    For i from 0 to n–2 : n-1번 반복 (0부터니까 n-2)

        If i'th and i+1'th elements out of order

            Swap them

=> 최선의 경우, n-1번 실행하면 종료되기 때문에 버블 정렬 실행 시간의 하한이 Ω(n)이 된다.

 

 

선택 정렬(Selection Sort)

• 자료 안의 값 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식으로 정렬한다.
• 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

 

 

선택 정렬 알고리즘 예시

 

선택 정렬 의사코드

For i from 0 to n–1 : n번 반복

    Find smallest item between i'th item and last item : i번째부터 마지막 항목 중 가장 작은 항목을 찾기

    Swap smallest item with i'th item : 찾은 항목과 i번째 항목을 교환

=> 바깥 반복문은 n-1번 반복하고 안쪽 반복문에서는 가장 작은 값을 찾는다.

 

선택 정렬 시간 복잡도 

$$n+(n-1)+(n-2)+...+1  =  n(n-1)/2  =  n^2/2+n/2$$

 

선택 정렬 실행 시간의 상한 : O(n²)

• 최고차항이 n²이므로 O(n²)이다.

 

선택 정렬 실행 시간의 하한 : Ω(n²)

• 정렬이 되어 있는지 여부에 관계없이 반복문을 실행하며 비교를 해야 하므로 Ω(n²)이다.

 

think about

1) 버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적이게 될까요?

오름차순 또는 내림차순 등의 정렬이 필요한 경우에는 효율적이다. 

이미 정렬이 되어있는 배열인 경우에는 비효율적이다. 

 

2) 선택정렬을 좀 더 효율적으로 어떻게 바꿀 수 있을까요?

제일 작은 값과 제일 큰 값을 동시에 찾아서 양쪽 끝에 해당하는 값들을 찾는다면 더 효율적이지 않을까 생각한다.

또는 배열의 값을 자연수로만 제한하면 안쪽 반복문에서 진행하는 조건을 더 효율적으로 바꿀 수 있을거 같다. 

 

3) 선택 정렬의 실행 시간의 하한도 버블 정렬처럼 더 단축시킬 수 있을까요?

인접한 배열 값만 확인하는 버블 정렬과 달리 선택 정렬은 전체를 파악해야 하기때문에 실행 시간의 하한을 줄이기는 어렵다고 생각한다.

 

David J. Malan의 강의

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

Comparison Sorting Visualization

정렬 알고리즘 비교