정리해 두면 찾는 일이 빨라진다
정렬은 뒤에 오는 일을 위한 준비일 때가 많습니다.
책장이 뒤죽박죽이면 책 한 권을 찾으려고 꽂힌 것을 전부 살펴봐야 합니다. 번호 순으로 꽂혀 있으면 눈으로 대충 살펴도 금방 손이 갑니다. 정리하는 일 자체는 귀찮지만, 한 번 정리해 두면 그 뒤로 찾는 일이 빨라집니다.
정렬(sorting)
데이터를 어떤 기준에 따라 순서대로 늘어놓는 것입니다.
정렬을 하려면 기준을 먼저 정해야 합니다. 같은 책이라도 번호로 늘어놓을 수도, 제목의 가나다순으로 늘어놓을 수도 있습니다. 사진첩을 찍은 날짜순으로 볼 수도 있고, 음악 목록을 제목순으로 바꿀 수도 있습니다. 기준이 달라지면 결과도 달라집니다.
오름차순(ascending)
작은 것부터 차례로 놓습니다.
8, 17, 35, 42, 63 / 가, 나, 다, 라
내림차순(descending)
큰 것부터 차례로 놓습니다.
63, 42, 35, 17, 8 / 라, 다, 나, 가
오늘 정리할 다섯 권
학급 문고 다섯 권이 번호와 상관없이 놓여 있습니다. 이 다섯 권을 번호 오름차순으로 꽂는 것이 오늘의 문제입니다. 앞으로 세 가지 방법을 볼 텐데, 셋 다 이 다섯 권으로 해 봅니다. 같은 문제를 풀어야 방법끼리 나란히 놓고 볼 수 있기 때문입니다.
지금 꽂혀 있는 순서
우리가 만들려는 순서
왜 정렬하는 방법이 여러 개나 있을까
우리는 다섯 권을 한눈에 보고 곧바로 「8, 17, 35, 42, 63」이라고 말할 수 있습니다. 하지만 컴퓨터는 그렇게 하지 못합니다. 여기서 볼 세 방법에서 컴퓨터가 하는 일은 「두 값 중 어느 쪽이 큰가」를 묻는 것과 값의 위치를 옮기는 것, 이 둘뿐입니다. 그렇다면 어느 두 값을, 어떤 차례로 볼 것인가를 정해 주어야 합니다. 여기서 정렬 방법이 여러 가지로 나뉩니다.
내 휴대 전화나 컴퓨터에서 무언가가 순서대로 늘어서 있는 화면을 하나 떠올려 보세요. 그 화면은 무엇을 기준으로, 오름차순과 내림차순 중 어느 쪽으로 늘어서 있나요?
버블 정렬 — 바로 옆에 있는 것과만 비교한다
멀리 볼 필요 없이, 바로 옆만 보면 됩니다.
가장 단순한 규칙부터 생각해 봅시다. 바로 옆에 놓인 두 권의 번호를 비교하고, 앞의 것이 더 크면 두 값을 교환합니다. 그리고 한 칸 오른쪽으로 옮겨 가 같은 일을 반복합니다. 이렇게 이웃한 값끼리만 비교하며 위치를 정해 가는 방법을 버블 정렬(bubble sort)이라고 합니다.
버블 정렬의 규칙
- 맨 왼쪽에서 시작해 이웃한 두 값을 본다.
- 앞의 값이 더 크면 두 값을 교환한다. 아니면 그대로 둔다.
- 한 칸 오른쪽으로 옮겨 1~2를 반복한다. 끝에 닿으면 한 회전이 끝난다.
- 회전이 끝날 때마다 맨 뒤 한 칸이 확정된다. 남은 칸으로 다시 회전한다.
1회전을 한 걸음씩
분홍색이 지금 번호를 보고 있는 두 권입니다.
한 회전을 마치면 가장 큰 63이 반드시 맨 뒤에 도착합니다. 한번 만난 큰 값은 계속 오른쪽으로 밀려가기만 하기 때문입니다. 그래서 다음 회전부터는 맨 뒤 칸을 볼 필요가 없습니다.
회전이 끝날 때마다 뒤에서부터 위치가 확정된다
같은 일을 반복하면 청록색 칸이 뒤에서부터 한 칸씩 늘어납니다.
남은 칸이 하나뿐이면 비교할 상대가 없으므로 정렬이 끝납니다. 여기까지 비교 10번, 교환 6번이 있었습니다.
좋은 점
- 규칙이 네 줄이면 설명이 끝날 만큼 단순합니다.
- 값을 원래 책장 안에서 교환만 하므로 값을 옮겨 놓을 빈 책장이 따로 필요 없습니다.
걸리는 점
- 값이 이웃끼리 한 칸씩만 움직입니다. 8처럼 멀리 가야 하는 값은 여러 회전에 걸쳐 조금씩 옮겨 갑니다.
- 그래서 교환이 잦습니다.
8이 맨 앞까지 가는 데 세 번의 회전이 걸렸습니다. 왜 한 번에 앞으로 가지 못했을까요? 버블 정렬의 규칙 가운데 어느 항목 때문인지 확인해 보세요.
선택 정렬 — 남은 것 중 가장 작은 것을 데려온다
멀리 있어도 한 번에 알맞은 위치로 옵니다.
버블 정렬에서 8이 앞까지 오는 데 애를 먹은 이유는 한 칸씩만 움직였기 때문입니다. 그렇다면 아예 아직 위치가 확정되지 않은 것 전부를 순차 탐색(앞에서부터 하나씩 차례로 확인하는 것)으로 살펴 가장 작은 값을 찾아 곧바로 맨 앞으로 데려오면 어떨까요? 이렇게 위치를 확정해 가는 방법이 선택 정렬(selection sort)입니다.
선택 정렬의 규칙
- 아직 확정되지 않은 칸을 전부 순차 탐색해 가장 작은 값을 찾는다.
- 그 값을 확정되지 않은 칸의 맨 앞에 있는 값과 교환한다. 이미 맨 앞에 있으면 그대로 둔다.
- 맨 앞 한 칸이 확정된다. 남은 칸으로 1~2를 반복한다.
회차마다 앞에서부터 위치가 확정된다
노란색이 그 회차에 찾아낸 가장 작은 값입니다.
마지막 한 칸은 남은 것이 하나뿐이라 저절로 알맞은 위치에 있습니다. 여기까지 비교 10번, 교환 2번이 있었습니다.
2회와 4회에서는 교환이 한 번도 일어나지 않았습니다. 찾아낸 가장 작은 값이 이미 알맞은 위치에 있었기 때문입니다. 선택 정렬은 한 회차에 많아야 한 번만 교환하므로, 다섯 권을 정렬하는 동안 교환이 아무리 많아도 네 번을 넘지 않습니다.
좋은 점
- 교환이 아주 적습니다. 값을 옮기는 데 힘이 많이 드는 상황에서 유리합니다.
- 많아야 몇 번 교환할지 미리 알 수 있습니다. 회차 수를 넘지 않기 때문입니다.
걸리는 점
- 가장 작은 값을 찾으려면 남은 칸을 하나도 빠짐없이 봐야 합니다.
- 그래서 이미 순서가 맞아 있어도 비교 횟수가 줄지 않습니다.
다섯 권이 이미 번호 오름차순으로 꽂혀 있다면, 선택 정렬은 비교를 몇 번 할까요? 교환은 몇 번 할까요?
삽입 정렬 — 손에 든 카드를 정리하듯
이미 정리된 쪽에 새 것을 끼워 넣습니다.
카드놀이를 할 때 손에 든 카드를 정리하는 모습을 떠올려 보세요. 우리는 카드를 통째로 늘어놓고 살펴보지 않습니다. 새로 받은 카드 한 장을 들고, 이미 정리해 둔 카드 사이에서 알맞은 위치를 찾아 끼워 넣습니다. 이 방식이 그대로 삽입 정렬(insertion sort)입니다.
삽입 정렬의 규칙
- 맨 앞 한 권은 이미 정리된 것으로 본다. 한 권뿐이면 순서가 어긋날 수가 없기 때문이다.
- 그다음 권을 집어 들고, 정리된 쪽의 오른쪽 끝부터 왼쪽으로 번호를 비교해 나간다.
- 집어 든 것보다 큰 값은 한 칸씩 오른쪽으로 밀어 들어갈 공간을 만든다.
- 자기보다 작은 값을 만나거나 맨 앞에 닿으면, 그 위치에 끼워 넣는다.
한 권씩 끼워 넣기
청록색이 이미 정리된 쪽, 노란색이 지금 집어 든 권입니다.
집어 들 권이 남지 않으면 정렬이 끝납니다. 여기까지 비교 8번, 밀어내기 6번이 있었습니다.
63을 끼워 넣을 때를 보세요. 바로 왼쪽의 42와 한 번 비교하고 곧바로 멈췄습니다. 이미 42보다 크다는 것을 알았으니 그 왼쪽은 볼 필요가 없기 때문입니다. 순서가 어느 정도 맞아 있으면 비교가 일찍 멈춘다는 것이 삽입 정렬의 가장 큰 특징입니다.
같은 다섯 권이라도 처음 순서에 따라 달라집니다
| 처음 꽂혀 있던 순서 | 비교 | 밀어내기 | 왜 그런가 |
|---|---|---|---|
| 8 17 35 42 63 (이미 오름차순) |
4번 | 0번 | 집어 든 권마다 왼쪽 이웃 하나와 비교하면 바로 멈춥니다. |
| 42 17 63 8 35 (우리가 푼 것) |
8번 | 6번 | 8처럼 멀리 가야 하는 값에서 밀어내기가 몰립니다. |
| 63 42 35 17 8 (거꾸로 꽂혀 있음) |
10번 | 10번 | 집어 든 권이 언제나 맨 앞까지 가야 해서 정리된 쪽을 전부 밀어냅니다. |
그래서 「삽입 정렬이 빠르다」고 잘라 말할 수 없습니다. 어느 정도 정리되어 있는 데이터에서 빠르다고 해야 맞습니다.
좋은 점
- 순서가 이미 웬만큼 맞아 있으면 비교가 금방 끝납니다.
- 정렬해 둔 것에 새 값 하나를 추가할 때 그 값만 끼워 넣으면 됩니다.
걸리는 점
- 들어갈 공간을 만들려면 큰 값들을 한 칸씩 밀어야 합니다.
- 순서가 많이 흐트러져 있으면 밀어내는 일이 크게 늘어납니다.
이미 정리된 8 17 35 42 63에 번호 20인 책이 새로 들어왔습니다. 삽입 정렬의 규칙대로라면 몇 번 비교하고 몇 권을 밀어야 할까요?
세 방법을 나란히 놓고 세어 보기
결과는 같습니다. 다른 것은 거기까지 가는 길입니다.
세 방법 모두 같은 다섯 권을 8 17 35 42 63으로 만들었습니다. 결과만 보면 셋을 구별할 수 없습니다. 구별되는 것은 거기까지 가면서 몇 번 비교했고 몇 번 값을 옮겼는가입니다.
| 정렬 방법 | 비교 | 값 옮기기 | 눈에 띄는 점 |
|---|---|---|---|
| 버블 정렬 | 10번 | 교환 6번 | 이웃끼리만 보므로 규칙이 가장 단순합니다. 대신 값이 한 칸씩만 움직입니다. |
| 선택 정렬 | 10번 | 교환 2번 | 교환이 회차마다 많아야 한 번입니다. 대신 남은 칸을 늘 전부 순차 탐색합니다. |
| 삽입 정렬 | 8번 | 밀어내기 6번 | 순서가 맞아 있으면 비교가 일찍 멈춥니다. 대신 들어갈 공간을 만들려고 밀어냅니다. |
「값 옮기기」 칸의 숫자는 서로 같은 기준이 아닙니다
세는 단위가 다르기 때문입니다. 버블과 선택의 교환 한 번은 두 값이 서로 위치를 바꾸는 일이고, 삽입의 밀어내기 한 번은 한 값이 옆 칸으로 옮겨 가는 일입니다. 그래서 「교환 6번」과 「밀어내기 6번」은 같은 양의 일이 아닙니다. 비교 횟수는 셋 다 같은 기준이므로 그대로 나란히 놓아도 됩니다.
표의 숫자는 이 다섯 권을 이 순서로 꽂아 두었을 때 나온 값입니다. 처음 순서가 달라지면 숫자도 달라집니다. 실제로 삽입 정렬은 같은 다섯 권으로도 비교 횟수가 4번에서 10번 사이를 오갔습니다. 한 번 세어 본 값으로 「이 방법이 더 낫다」고 결론짓지 않도록 조심해야 합니다.
그러면 어느 것을 쓸까
언제나 옳은 하나는 없습니다. 데이터가 어떻게 생겼는지, 그리고 비교와 옮기기 중 어느 쪽에 힘이 더 드는지를 보고 고릅니다.
규칙을 가장 쉽게 설명해야 한다면
버블 정렬. 이웃 둘만 보면 되므로 처음 배우는 사람에게 설명하기 쉽습니다.
값을 옮기는 데 힘이 많이 든다면
선택 정렬. 옮기는 횟수가 회차 수를 넘지 않아 많아야 몇 번인지 미리 셀 수 있습니다.
이미 웬만큼 정리되어 있다면
삽입 정렬. 비교가 일찍 멈추고, 새 값을 하나 추가할 때도 편합니다.
여기서는 다섯 권을 놓고 손으로 세어 보는 것까지만 합니다. 다섯 권이 아니라 수만 권이 된다면 이 숫자들이 어떻게 불어나는지가 궁금해질 텐데, 그것은 세는 방법을 따로 마련해야 답할 수 있는 물음입니다.
더 알아보기
정렬 알고리즘 시뮬레이터의 「알고리즘 비교」 탭에서 버블 정렬 · 선택 정렬 · 삽입 정렬만 선택하면, 데이터를 8개에서 1,000개까지 늘려 가며 측정한 작업량 곡선으로 세 방법의 일이 어떻게 불어나는지 볼 수 있습니다.
책 대신 아주 무거운 상자 다섯 개를 번호순으로 놓는다고 해 봅시다. 번호를 읽는 것은 쉽지만 상자를 옮기는 것은 힘듭니다. 세 방법 중 무엇을 고르겠습니까?
핵심 정리
정렬
sorting
- 데이터를 어떤 기준에 따라 순서대로 늘어놓는 것
- 작은 것부터면 오름차순, 큰 것부터면 내림차순
- 세 방법 모두 두 값 비교와 값 옮기기만으로 정렬하고, 어느 두 값을 어떤 차례로 보느냐에서 나뉜다
버블 정렬
bubble sort
- 이웃한 두 값만 보고 순서가 어긋나면 교환한다
- 한 회전마다 가장 큰 값이 맨 뒤에 확정된다
- 규칙이 단순한 대신 교환이 잦다
선택 정렬
selection sort
- 남은 칸에서 가장 작은 값을 찾아 맨 앞과 교환한다
- 교환이 회차마다 많아야 한 번
- 이미 정렬돼 있어도 비교 횟수는 줄지 않는다
삽입 정렬
insertion sort
- 정리된 쪽의 알맞은 위치에 끼워 넣는다 — 손에 든 카드 정리와 같다
- 들어갈 공간을 만들려고 큰 값들을 한 칸씩 밀어낸다
- 어느 정도 정리되어 있을 때 비교가 일찍 멈춘다
확인 퀴즈
배운 내용을 확인해 봅시다.
버블 정렬로 한 회전을 마쳤을 때 반드시 위치가 확정되는 값은?
선택 정렬에서 교환이 한 번도 일어나지 않는 회차가 생기는 까닭은?
세 정렬 방법에 대한 설명으로 옳지 않은 것은?