현실적인 문제로 뛰어들기 전에 먼저 빅 오 세계에서 알고리즘 효율성을 표현하는 새로운 카테고리를 알아보자. 컴퓨터 과학 분야에서 대대로 이어져 내려온 고전 알고리즘 하나를 사용해 설명하겠다.

정렬 알고리즘은 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 지난 수년간 수십 개의 정렬 알고리즘이 개발돼 왔다. 이러한 알고리즘 모두 다음의 문제를 해결한다.

정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까?

4장과 5장에서 이러한 정렬 알고리즘을 많이 다룰 것이다. 먼저 “단순 정렬(simple sort)”이라 알려진 알고리즘 분류를 배워보겠다. 이해하기 쉬워서 이렇게 불리지만, 더 빠르다고 알려진 정렬 알고리즘보다 비효율적이다.

매우 기본적인 정렬 알고리즘인 버블 정렬(bubble sort)은 다음과 같은 단계를 따른다.

1. 배열 내에서 연속된 두 항목을 가리킨다(처음에는 배열의 첫 번째 원소부터 시작해서 처음 두 항목을 가리킨다). 첫 번째 항목과 두 번째 항목을 비교한다.

▲ 그림 4-1