[2주차] 정렬 알고리즘 - 버블, 선택, 삽입 정렬

스터디가 어느덧 2주차에 접어들었다.

이번 주차에서는 정렬 알고리즘만을 다루는데,

오늘의 포스팅에서는 정렬 알고리즘 중에서도 시간 복잡도가 O(n^2)인 비교 정렬 알고리즘 세 개에 대해서 다룬다. 

 

---

정렬의 기본 골자

정렬이 필요한 이유

 

컴퓨터 과학과 수학에서의 정렬 알고리즘의 정의는 아래와 같다.

원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.
출처 : 위키백과 - 정렬 알고리즘
(https://ko.wikipedia.org/wiki/%EC%A0%95%EB%A0%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

 

그렇다면 정렬은 왜 필요한 것일까?

 

데이터를 정렬해야 하는 이유는 오로지 '탐색'을 위해서다.

컴퓨터는 보통 백만 개 단위 혹은 그 이상의 단위량의 데이터를 다뤄야 하는데, 탐색할 대상 데이터가 정렬되어 있지 않다면 순차 탐색만이 유일한 방법인데, 순차 탐색의 경우 최악의 경우의 시간 복잡도가 O(n)이다. 데이터의 양이 많아지면 많아질수록 순차 탐색에 소요되는 시간은 늘어날 수밖에 없다. 운이 좋아 배열의 맨 첫 요소가 우리가 찾는 값이 아니라면 말이다.

 

하지만, 정렬이 보장된 데이터의 나열이라면 어떤 값을 임의로 선택했을 때, 해당 값의 좌측에는 반드시 그것보다 작거나 같은 값이 있으며 우측에는 그것보다 크거나 같은 값이 있음이 보장된다. 따라서 우리가 찾아야 할 목표값을 찾을 때, 임의로 선택한 어떤 값이 목표값보다 작다면 그 왼쪽은 쳐다볼 필요도 없다.

 

즉, 정렬이 보장된 데이터에서는 이진 탐색 알고리즘이라는 강력한 알고리즘의 적용이 가능하다는 것이다.

이진 탐색 알고리즘의 경우 43억 개의 정렬된 자료에서 어떠한 값을 찾아야 할 때 최악의 비교횟수 마저도 32회에 불과하다.

이진 탐색은 추후 주차가 몇 주 더 지나야 공부하게 되겠지만, 정렬은 어떻게 보면 이진 탐색만을 위한 것이라고 해도 무방하다.

 

 

비교 정렬

 

정렬 알고리즘은 그 특징에 따라 몇 가지로 분류할 수 있는데, 비교 정렬, 제자리 정렬, 온라인 정렬이 있다.

그 중에서 오늘 다룰 정렬은 비교 정렬이다.

 

비교 정렬은 원소들을 정렬할 때 원소들의 순서에만 의존한다.

더 쉽게 설명하면, 우리 인간이 값을 정렬하는 방식을 흉내낸 정렬 방식이라고 생각하면 된다.

기본적으로 우리 인간이 5개의 무작위 숫자 카드를 정렬한다고 했을 때, 처음에는 카드 두 개를 집어 두 카드의 값을 비교한 뒤에 순서대로 나열한다. 이러한 방식을 이야기한다.

 

우리는 이 포스팅에서 비교 정렬에서 가장 기본적이고 유명한 세 가지 정렬을 알아본다.

 

1. 버블 정렬 (Bubble sort)

시각화된 버블 정렬 알고리즘

 

 

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 정렬이라고 지어진 이 정렬 방법은

시간 복잡도가 O(n^2)으로 상당히 느리지만 코드가 단순하고 컴퓨터의 정렬 방식에 대해 이해하기 쉽기 때문에 자주 이용된다.

비교 정렬임과 동시에 배열의 내부에서만 원소의 교환이 이루어지므로 제자리 정렬 (In-place Sort) 이다.

 

버블 정렬은 기본적으로 배열의 두 수를 선택한 뒤, 만약 그 두 수가 정렬 되었다면 (오름차순, 내림차순 등 사용자가 정한 조건에 부합하는 순서대로 원소가 위치한 경우) 그대로 두고, 정렬되지 않았다면 그 두 수의 위치를 변경하는 방식으로 진행된다. 이를 배열의 처음부터 끝까지, 배열에 아무 변화가 없을 때까지 반복한다.

 

[7, 2, 0, 1, 5, 6, 4] 원소를 가진 배열을 버블 정렬로 오름차순 정렬하는 예를 알아보자.

 

처음으로는 배열의 첫 두 숫자 (7, 2)를 비교한다. 7 > 2 이므로 정렬되지 않은 상태이니 두 수를 교체한다

 

위와 같은 비교를 배열의 첫 요소부터 끝까지 작업한다면 아래와 같은 상태가 된다.

 

즉, 한 번의 배열 순회와 비교에서 최대값이 배열의 가장 끝에 위치하게 된다.

빨간색 수는 배열 끝으로 위치하게 된 최대값을, 파란색은 최대값이 아닌 정렬이 완료된 수를 의미한다.

 

이 순회를 배열의 변화가 없을 때까지 반복을 수행한다.

 

3번의 배열 순회 끝에 데이터가 정렬 되었고, 다시 순회를 하여도 배열의 상태에는 변화가 없다.

즉 이 상태는 배열이 모두 정렬된 상태로 정의할 수 있다.

 

이렇듯 버블 정렬은 한 번의 배열 순회로 배열이 정렬되지 않는다.

배열의 변화가 없을 때까지 지속적으로 배열 순회가 이뤄져야 하며, 시간 복잡도는 지수로 늘어날 수밖에 없다.

 

 

2. 선택 정렬 (Selection Sort)

 

 

선택 정렬은 버블 정렬과 동일하게 비교 정렬임과 동시에 제자리 정렬이다.

주어진 배열에서 최소값을 찾아 그 값을 맨 앞에 위치한 값과 교체하며 맨 처음 위치를 뺀 나머지 배열의 요소를 같은 방법으로 교체한다.

최악, 최선, 평균 모두 값의 비교에 O(n^2)의 시간 복잡도, 교환에 O(n)의 시간 복잡도를 갖지만 버블 정렬보다 2배 빠른 속도를 보장한다.

 

[9, 1, 6, 8, 4, 3, 2] 배열을 선택 정렬로 정렬하는 예시를 알아보자.

 

초기 상태에서 전체 배열에서 최소값 1을 찾는다. 그리고 맨 앞의 9와 자리를 바꿔준다.

 

 

그리고 1을 제외한 나머지 요소들에서 최소값을 찾아 맨 앞의 값과 변경해가며 정렬을 수행한다.

 

 

버블 정렬은 최댓값을 가장 뒤로 보낸다면, 선택 정렬은 최소값을 맨 앞으로 보내는 방법이 차이로 다가올 수 있을 것 같다.

 

3. 삽입 정렬 (Insertion Sort)

 

 

삽입 정렬 역시 시간 복잡도가 O(n^2)인 비교 정렬 알고리즘이다.

이 역시 제자리 정렬이고, 이 포스팅에서는 추가적으로 다루지는 않았지만, 안정 정렬이다. 

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 방식으로 정렬이 이뤄진다.

 

삽입 정렬에서는 정렬할 자료가 두 개로 나뉘는데,

정렬된 앞 부분의 요소를 부분집합 S, 정렬되지 않은 나머지 요소들은 부분집합 U다.

U에서 요소를 하나씩 꺼내 S를 순회하며 비교하며 위치를 찾아 삽입해서 삽입 정렬이라 불린다.

정렬을 수행할 수록 S의 요소는 1개씩 늘고, U의 요소는 한개씩 줄어든다.

U가 공집합이 될 때까지 반복한다. 

 

아래는 [31, 25, 12, 22, 11, 14, 16] 의 배열을 삽입 정렬로 정렬해보는 예제다.

 

배열의 맨 처음 요소는 부분 집합 S, 나머지 요소는 부분 집합 U로 둔다.

값의 비교는 U의 첫 번째 요소 25부터 시작한다.

 

25를 S의 값들을 순회하며 비교하여 적절한 위치에 삽입한다. 25는 31보다 작으므로 31의 왼쪽에 삽입된다.

 

 

그 다음 12를 S를 순회하며 가장 적절한 위치에 삽입한다. 25 보다 작으므로 25의 왼쪽에 삽입된다.

 

 

다음은 22를 꺼내 S를 순회하며 적절한 위치인 12와 25 사이에 삽입한다.

 

 

다음의 11 또한 같은 방법으로 반복한다. 이처럼 S의 길이는 늘려나가고 U의 길이는 줄여가며 U가 공집합이 될 때까지 반복하면

 

정렬이 완료되는 모습을 볼 수 있다.

 

삽입 정렬은 이 GIF 이미지로 파악하는게 좋을 것 같아 한 번 더 보시라고 가져왔다.

 

학습 자료 출처

위키 백과 - 정렬 알고리즘 : https://ko.wikipedia.org/wiki/%EC%A0%95%EB%A0%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

나무위키 - 정렬 알고리즘 : https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

위키 백과 - 버블 정렬 : https://ko.wikipedia.org/wiki/%EB%B2%84%EB%B8%94_%EC%A0%95%EB%A0%AC

위키백과 - 선택 정렬 : https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

삽입 정렬이란? : https://ssdragon.tistory.com/112