d라이브러리

여러분의 책장을 살펴 보세요. 책이 잘 정리되어 있나요? 만약 책이 들쑥날쑥, 엉망진창으로 널려 있다면 한 번 정리해 보세요. 가장 작은 책이 왼쪽에, 가장 큰 책이 오른쪽에 오도록 두는 건 어떨까요? <;어린이과학동아>;처럼 원래 순서가 정해진 경우라면, 가지고 있는 어과동 중 가장 먼저 나온 책을 왼쪽에 두고 그 후 책이 나온 월 순으로 정리할 수 있을 거예요.

이처럼 어떤 데이터를 순서대로 늘어놓는 걸 ‘정렬’이라고 해요. 이때 순서는 크기, 알파벳, 레벨 등 다양하게 선택할 수 있지요. 복잡하고 큰 데이터를 다루는 컴퓨터에서는 정렬 알고리즘이 필수적으로 쓰여요.

정렬 알고리즘 중에 가장 널리 쓰이는 것은 ‘퀵 정렬 알고리즘’이에요. 기준이 되는 데이터를 하나 뽑은 뒤, 이 데이터보다 크기가 작은 것과 큰 것을 찾아 정렬하는 방식이에요. ‘퀵(quick)’, 즉 ‘빠르다’라는 이름이 붙은 만큼 매우 빠른 시간 동안 많은 양의 데이터를 정리할 수 있
답니다.

3, 5, 4, 1, 2 순으로 들쑥날쑥하게 꽂혀 있는 책들을 1~5까지의 오름차순으로 정리해 볼까요? 먼저 가장 왼쪽에 있는 3을 기준으로 둘게요. 그리고 왼쪽부터 오른쪽 방향으로 기준보다 큰 숫자를 찾고, 오른쪽부터 왼쪽 방향으로는 기준보다 작은 숫자를 찾아요. 이렇게 필요한 숫자를 찾는 점을 각각 ‘low’와  'high’라고 해요.

가장 왼쪽에 있는 3은 기준이니 넘어가고, 그 다음에 있는 숫자 중 3보다 큰 것은 5예요. 그럼 low는 5에서 멈춰요. 그리고 오른쪽에 있는 숫자 2가 3보다 작기 때문에 high는 2에서 머무르지요. 그럼 5과 2의 자리를 서로 맞바꿔서 3, 2, 4, 1, 5로 만들어요.





이런식으로 한번 더 바꿔서 3, 2, 1, 4, 5가 됐어요. 그런데 그 결과low가 high보다 더 오른쪽에 와 버렸네요? 이럴 땐 기준이 되는 숫자와 high의 값을 서로 맞바꿔야 해요. 즉 1, 2, 3, 4, 5라는 결과가 나오며 정렬 완료! 만약 이보다 데이터가 많으면 기준 값 양 옆을 다시 한 번 정렬해 줘야 해요. 이런 식으로 기준인 데이터를 다른 값들과 바꿔 가며 데이터들을 작게 나누고, 그 데이터를 빠르게 정렬하는 것이 퀵 정렬의 특징이랍니다.

거품 정렬 알고리즘도 많이 쓰여요. 첫 번째 데이터부터 옆의 것과 크기를 비교해 가는 방식이지요. 이번에도 책이 3, 5, 4, 1, 2 순이라고 해요. 그럼 먼저 3과 5를 비교해서 5가 더 크니까 그대로 두지요. 다음은
5와 4를 비교해 크기가 작은 4를 5 앞으로 옮겨요. 5와 1, 5와 2 역시 크기가 작은 것이 더 오른쪽에 있기 때문에 각각 왼쪽으로 옮기지요. 그럼 결과는 3, 4, 1, 2, 5가 되죠? 더 이상 옮길 숫자가 없을 때까지 같은 과정을 계속 진행하면 1, 2, 3, 4, 5로 정렬된답니다.

거품 정렬 알고리즘은 단순한 코드로도 만들 수 있어요. 데이터에 따라서는 퀵보다 더 빠른 정렬을 보여 주기도 해요. 하지만 데이터의 수가 늘어날수록 정렬에 걸리는 시간도 기하급수적으로 늘어난답니다.