[CS50] 선택 정렬

저번 포스팅의 버블 정렬은 직관적이긴 하지만 O(n^2)의 시간이 소요된다고 했습니다. 이번에는 다른 정렬 알고리즘인 선택 정렬에 대해 공부해보도록 하겠습니다.

 

선택정렬

각 자료를 비교하는 횟수는 증가하지만 교환 횟수를 최소화하는 정렬입니다. 배열 안의 자료 중 가장 작은 수(혹은 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식을 사용합니다.

버블 정렬과 마찬가지로 예를 들어 설명하자면

6 4 3 7 1 2 8 5 라는 정렬되지 않은 숫자가 있을 때 이를 선택 정렬을 이용해 오름차순으로 정리하는 방법은

우선 위의 수중에서 가장 작은 값을 찾습니다. (여기서 1)

1 4 3 7 6 2 8 5  // 1과 6의 위치를 바꿉니다.

그다음 1을 제외하고 4부터 시작해서 또 가장 작은값을 찾습니다. (여기서 2)

1 2 3 7 6 4 8 5  // 2와 4의 위치를 바꿉니다.

...                    // 이렇게 계속 교환하다 보면

1 2 3 4 5 6 7 8  // 결국 이렇게 오름차순으로 정렬됩니다.

이것을 의사 코드로 표현하자면

for i from 0 to n-1

	find smallist item between i`th item and last item
    
    Swap smallist item with i`th item

이런 식으로 표현이 가능합니다.

여기서도 2번의 루프를 돌아야 합니다.

바깥 루프는 숫자들을 처음부터 끝까지 살펴보고 안쪽 루프에서는 가장 작은 값을 찾아야 합니다.

따라서 소요시간은 버블 정렬과 마찬가지로 상한은 O(n^2), 하한 시간은 Ω(n^2)이 됩니다.

---

출처

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

 

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