<알고리즘> 버블정렬과 선택정렬

 

1. 버블 정렬

 - 버블 정렬은 두 개의 인접한 데이터를 비교하면서 서로의 위치를 교환하며 정렬해나간다.

 

 - 임의의 숫자의 나열 7 5 6 8 1 3 을 보자.

 

 - 오름차순으로 나열하기 위해 버블정렬을 한다면 가장 먼저 7과 5가 비교된다.

 

 - 7 5 6 8 1 3 => 5 7 6 8 1 3

 

 - 7이 더 크므로 5와 위치가 교환된다. 다음은 두 번째 위치값과 세 번째 위치값이 비교된다.

 

 - 5 7 6 8 1 3 => 5 6 7 8 1 3

 

 - 7과 6중 7이 더 크므로 위치가 교환된다. 

 

 - 마찬가지로 진행하면 세 번째와 네 번째, 네 번째와 다섯 번째, 다섯 번째와 여섯 번째를 비교하면 다음과 같이 교환된다.

 

 - 5 6 7 8 1 3 => 5 6 7 8 1 3 => 5 6 7 1 8 3 => 5 6 7 1 3 8

 

 - 아직 완전한 정렬은 되지 않았다. 따라서 다시 처음부터 동일한 과정을 반복한다.

 

 - 그렇게 되면 결국 1 3 5 6 7 8 로 오름차순 정렬이 완성된다.

 

 - 위와 같은 방식을 버블 정렬이라 한다. 마치 거품이 터지면서 위로 올라오는 방식과 비슷해서 지어진 이름이다. 이를 의사코드로 나타내보자.

 

n - 1 번 반복
  i는 0부터 n-1
    만약 i번째 숫자가 i+1 숫자보다 크다면
      교환한다

 

 - 반복이 2개 존재하는 중첩루프이다. 각 루프는 n-1번, n-1번이므로 (n-1)(n-1) 번의 비교 및 교환이 필요하다.

 

 - 즉 버블 정렬 실행시간의 상한은 O(n^2) 이다. 정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 하므로 위 코드의 실행 하한은 Ω(n^2) 이다.

 

 - 여기서 버블정렬은 사실 개선점이 있다. 위에서 작성했던 의사코드에서 멈추는 기능을 넣어주는 것이다. 

 

교환이 없을 때까지 반복
  i는 0부터 n-1
    만약 i번째 숫자가 i+1 숫자보다 크다면
      교환한다

 

 - 한번 루프를 돌때 교환이 한 번도 일어나지 않으면 교환을 멈추도록 하면 하한이 바뀌게 된다. 만일 모든 숫자가 이미 정렬되어 있다면, i번째와 i+1번째의 숫자를 한바퀴 비교하고는 중지가 될 것이다. 즉 n번의 검색후 종료된다.

 

 

2. 선택정렬

 - 선택정렬은 배열 안의 데이터 중 가장 작은 수 또는 가장 큰 수를 탐색하고, 첫번째 위치 또는 마지막 위치의 수와 교환하는 방식이다.

 

 - 교환횟수를 최소화할 수는 있지만 비교하는 횟수가 늘어난다는 단점이 있다. 게다가 동일한 값에 대해 기존의 순서가 유지되지 않는 불안정 정렬이다.

 

 - 7 5 6 8 1 3 을 오름차순으로 정렬해보자.

 

 - 먼저 가장 작은 값을 찾는다. 1 을 찾게 되었으므로 첫번째 위치의 7과 교환한다.

 

 - 1 5 6 8 7 3

 

 - 다음 작은 값을 찾는다. 3을 찾게 되었으므로 두 번째 위치의 5와 교환한다.

 

 - 1 3 6 8 7 5

 

 - 이를 반복하면 1 3 5 6 7 8 과 같이 오름차순 정렬된다.

 

 - 위를 의사 코드 형식으로 나타내면 다음과 같다.

 

i는 0부터 n-1
  i부터 n-1까지
    가장 작은 값을 찾는다.
      i번째 수와 교환한다.

 

 - 선택정렬 또한 버블정렬과 마찬가지로 중첩루프가 발생한다. 즉 O(n^2) 이며, 하한도 Ω(n^2)이다. 그러나 최악의 경우에서 선택정렬이 버블정렬에 비해 연산횟수는 적을 것이다.

 

 

 

 

---

 

 

 

 

참고

 

 

 이 글은 하버드 대학교 David Malan 교수의 CS50 강의를 수강 후 정리하며 쓴 글입니다. 코드는 C언어로 작성되었으며, 개발환경은 CS50 IDE에 최적화되어 있습니다. 일부 라이브러리는 다른 환경에서 별도의 설정이 필요할 수 있습니다.

 

 

 

CS50 공식사이트

CS50

 

부스트코스

다 함께 배우고 성장하는 부스트코스

 

CS50 IDE

CS50 IDE