모두를 위한 컴퓨터 과학(CS50) - 정렬 알고리즘

지난 글에서 검색 알고리즘을 알아봤습니다.

서랍을 예시로 들면서 서랍 안에 내용물이 정리되어 있다면?

정리되어 있지 않다면?으로 나눠서 문제를 해결해봤습니다.

 

그렇다면 정렬은 어떤 방식으로 수행될까요?

 

 

버블 정렬

버블 정렬은 정렬 알고리즘 중 하나입니다.

버블 정렬의 개념부터 먼저 말하자면

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 인덱스를 변경하는 방식입니다.

 

다음과 같은 리스트를 예로 들어보겠습니다.

 

a라는 리스트에 담긴 값은 순서대로

4 3 1 5 2

입니다.

 

이 값을 버블 정렬의 개념을 이용해서 오름차순으로 정렬해볼까요?

 

일단 첫 두자리를 비교합니다.

4 3 1 5 2

 

첫 번째 숫자가 두 번째 숫자보다 크기 때문에 두 숫자의 위치를 변경합니다.

3 4 1 5 2

 

자 이제 다음 두 수를 비교해봅니다.

4는 1보다 크기 때문에 두 숫자의 위치를 변경합니다.

3 1 4 5 2

 

자 이제 다시 다음 두 수입니다.

4는 5보다 작기 때문에 두 수의 위치는 변경하지 않습니다.

3 1 4 5 2

 

이제 마지막으로 5와 2를 비교합니다.

5는 2보다 크기 때문에 두 수의 위치를 변경해줘야 합니다.

3 1 4 2 5

 

자 그럼 우리가 원하는 답이 나왔나요?

아직 정답은 아니지만 처음 주어진 

[4 3 1 5 2]에 비하면 정답에 가까운 형태가 됐습니다.

 

방금 수행한 과정을 더 이상 위치 변경이 되지 않을 때까지 정렬하는 것

이것이 바로 버블 정렬입니다.

 

이 과정을 파이썬 코드로 한 번 나타내 보겠습니다.

 

 

실행 결과는 다음과 같습니다.

 

버블 정렬의 소요 상한 시간은 O(n^2)입니다.

 

 

 

 

선택 정렬

이번엔 다른 정렬인 선택 정렬을 알아보겠습니다.

선택 정렬은 우선 배열 안에서 가장 작은 수를 찾습니다.

 

위에 선언했던 리스트를 다시 가져와 보겠습니다.

4 3 1 5 2

자 우선 첫 번째 숫자가 제일 작은 수로 기억됩니다.

 

그다음으로 넘어가서 숫자를 봅니다.

3이네요.

4보다 작으니 이제 제일 작은 수는 3입니다.

4 3 1 5 2

 

또다시 다음 숫자를 확인해보겠습니다.

이번에는 1이네요.

3보다 작으니 이제 제일 작은 숫자입니다.

4 3 1 5 2

 

이제 다음 두 숫자를 순차적으로 비교해도 최종적으로는 1이 가장 작은 숫자입니다.

그렇다면 이제 가장 작은 수를 찾은 셈입니다.

 

이제 정렬을 하려면 어떻게 할까요?

오름차순 정렬이라고 가정할 때

가장 간단한 방식은 아마 첫 번째 위치와 찾은 숫자의 위치를 변경하는 것일 겁니다.

 

이러한 방식을 선택 정렬이라고 합니다.

 

설명한 과정을 파이썬을 이용해 확인해보겠습니다.

 

위와 같은 코드를 실행하면

선택 정렬이 일어나는 과정을 확인할 수 있습니다.

 

결과는 다음과 같습니다.

처음에 1과 4의 위치가 바뀌고,

그다음으로는 2와 3의 위치가 바뀝니다.

또 4와 3의 위치가 바뀌고

최종적으로는 4와 5의 위치가 바뀌면서 정렬이 완료되는 것을 확인할 수 있습니다.

 

선택 정렬의 소요 상한 시간은 버블 정렬과 마찬가지로 O(n^2)입니다.

 

 

 

---

출처 : 네이버 edwith, 부스트코스 [모두를 위한 컴퓨터 과학]