고니의 잡동사니 :: 기초부터 차근차근 ‘정렬 알고리즘’

기초부터 차근차근 ‘정렬 알고리즘’

고니의사진방 2007/06/08 00:36

기초부터 차근차근 ‘정렬 알고리즘’
저 자 : 진희정

살아가면서 알게 모르게 우리는 정렬(sorting)이라는 방법을 참 많이 사용하고 있습니다. 우리가 학교를 다닐 때 매달 치르는 시험 끝엔 꼭 반 등수, 전교 등수가 나왔고, TV를 보다가도 “저 사람들 중에서 누가 제일 멋있어?” 혹은 “누가 제일 맘에 드니?”라는 질문에 다들 자신의 기준에 맞게 “세 번째 사람이 제일 멋있고, 그 다음은 다섯 번째 사람”, 이런 식의 질문과 대답은 누구나 한번쯤은 해 보았을 것입니다. 이렇게 정렬이라는 건 우리가 알게 모르게 많이 사용하고 있는 것으로, 컴퓨터 알고리즘에서 가장 기본적이면서도 중요한 하나의 분야라고 볼 수 있습니다. 아마 알고리즘에 관련된 책을 본다면 정렬 알고리즘이 하나의 큰 장으로 분류되어 있는 것을 볼 수 있습니다.
컴퓨터로 뭔가를 만들려고 했을 때 처음 얼마동안 필자도 그랬었지만 필자가 가르치는 학생들을 보면 알고리즘을 설명하고 예를 들어주면 머리 속이나 손으로는 문제를 해결할 수 있는데, 직접 코딩을 해서 프로그램으로 만들어 보라고 하면 어떻게 시작을 해야 하는지를 모르는 경우가 많습니다. 그래서 이번 연재에서는 노래 가사에서도 있듯이 어렵고 생소하고 복잡한 알고리즘으로 호기심을 자극하는 글을 쓸 수도 있었지만, 기본적인 알고리즘을 통하여(물론 정렬 알고리즘도 깊이 들어가면 복잡하고 어려운 방법론들이 많이 있습니다) 처음 시작하는 학생들에게 도움이 되고자 합니다. 이번 연재를 통해서 앞으로 자신이 이해한 알고리즘은 직접 코딩해서 사용할 수 있는 능력에 조금이라도 보탬이 되었으면 합니다.

정렬? 정렬이란!
서두에서도 이야기를 했지만, 정렬이라는 것은 우리의 일상에서 아주 많이 사용되는 것입니다. 그럼 이번 장에서는 정렬 알고리즘을 배우기 위한 첫 단계로, 정렬의 의미와 종류에 대해서 알아보도록 하겠습니다. 알고리즘 책들을 살펴보면 아마도 “정렬이란 주어진 자료를 특정한 순서대로 나열하는 것을 말한다. 가장 쉬운 정렬은 숫자를 크기 순으로 나열하는 것이다. 그러나 숫자와는 다르게 그 순서가 다르게 정의되는 것은 다르게 정렬되어야 한다.”는 식의 정의를 볼 수 있을 겁니다. 그럼 이 의미는 뭘까요? 바로 이해가 되나요? 초등학교 문제같지만 우선 쉬운 걸로 예를 들어 볼까요?
필자가 좋아하는 보드 게임 중에 루미쿠브(Rummikub)라는 것이 있는데, 자신이 가지고 있는 숫자 조각을 모두 먼저 없애야 이기는 게임으로, 가장 먼저 조각을 모두 없애는 사람이 나오면 게임은 중단되고 나머지 사람들은 자신이 가지고 있는 숫자 조각들의 합을 계산해서 제일 작은 사람부터 2등, 3등이 가려집니다. 영희, 순희, 철이, 영철, 아랑이가 이 게임을 하는데, 영희가 가장 먼저 숫자 조각을 모두 없애고 나머지 사람들의 점수가 앞의 이름순으로 48점, 12점, 53점, 9점이었습니다. 만약 독자 여러분이 게임을 하고 있다면 점수를 듣는 즉시 “아랑, 철이, 영희, 영철”의 순이라는 것을 알 수 있을 겁니다. 방금 우리가 순서를 정한 것. 이것이 바로 정렬이 되고 순서를 정해야 하는 것들이 모두 숫자였으므로 숫자의 크기에 따라 정렬을 할 수 있었던 겁니다.
만약 “영희, 순희, 철이, 영철, 아랑이 있는데 이 사람들을 정렬하시오”라는 문제가 주어진다면, 우리가 가장 먼저 해야 하는 일은 “어떤 기준으로 정렬하죠?”라는 것을 물어야 하는 것입니다. 따라서 앞의 정렬 정의의 마지막에 나와 있듯이 정렬해야 하는 기준이 숫자가 아니라면, 그 순서가 다르게 정의가 되어야 하는 것입니다. 이를 다시 이야기하면 다음과 같이 이야기할 수 있습니다.

◆ 정렬은 자료의 정렬 순서에 따라서 오름차순(increasing order) 또는 내림차순(decreasing order)으로 나누어지고, 비순차적인 자료의 경우에는 위상 정렬(topological sorting)이라는 특별한 방법을 사용해서 정렬을 한다.

오름차순이나 내림차순이라는 말은 모두 알고 있죠? 그럼 위상 정렬이라는 건 뭘까요? 예를 들어 필자가 오늘 성적표를 받은 후 성적이 나빠 기분이 좋지 않다고 하면, 가장 나중에 생긴 일은 기분이 좋지 않다고 합시다. 이때 기분이 좋지 않은 건 성적이 나빠서고, 성적이 나쁘다는 것은 성적표를 봤기 때문에 알았던 것입니다. 그럼 성적표는 왜 받았죠? 바로 시험을 봤기 때문이죠. 그리고 그 이전에 결과의 원인이었던 공부를 하지 않은 겁니다. 이를 정리하면 다음과 같습니다.

① 공부를 하지 않는다.
② 시험을 치다.
③ 성적표를 받다.
④ 성적이 나쁘다.
⑤ 기분이 좋지 않다.

이처럼 일어난 일의 순서대로 정렬하는 것, 이를 위상 정렬이라 볼 수 있습니다.
그렇다면 어떤 정렬이 좋은 정렬이라고 볼 수 있을까요? 우선 생각해보면 사람이 손으로 하나하나 할 수 있지만, 컴퓨터를 사용해서 하는 만큼 일의 수행시간을 적게 하는 것이므로 빨라야 할 것 같은 생각이 들 것입니다. 그렇다면 무조건 빠르기만 하면 좋을까요? 우리가 사용하는 컴퓨터는 제한된 메모리에서 동작합니다. 따라서 메모리를 많이 사용해야 빨리 수행되는 것이라면, 그만한 메모리를 사기 위해서 많은 돈이 필요하겠죠? 그러면 적은 기억 장소를 사용하는 알고리즘이 좋은 것이라고 말할 수도 있겠군요. 그러나 자료가 아주 많아서 한번에 기억장소 모두에 올라올 수 없는 경우도 있습니다.
이렇게 자료 모두가 외부장소(디스크 또는 테이프)에 있을 경우 이를 정렬하는 알고리즘의 성능은 다르게 표시됩니다. 그럼 얼마나 빠르고 얼마나 적은 기억 장소를 사용해야 좋은 알고리즘일까요? 세상에 모든 경우의 정렬에서 가장 좋은 정렬 알고리즘이라는 것은 존재하지 않습니다. 따라서 우리가 “이 알고리즘이 좋다”라고 말하기 위해서는 “어떤 조건일 경우 이 알고리즘이 가장 뛰어나다”라는 식으로 말을 바꾸어야 합니다. “가장 뛰어나다”라는 식의 성능을 분석할 때에는 알고리즘의 직접 수행시간을 측정하는 방법(실측)과 이론적으로 성능을 측정(알고리즘의 성능 분석)하는 방법을 통해서 성능의 정도를 나타내게 됩니다.
지금까지 정렬이란 무엇이고, 어떠한 정렬이 좋은 것인지에 대해서 알아보았는데 그럼 정렬은 왜 하는 걸까요? 우리가 어떠한 문제를 해결하려고 할 때 그 문제를 왜 해결해야 하는가를 정확히 알고 있어야 올바른 문제 해결 방법을 제시할 수 있겠죠? 정렬을 사용하는 목적은 다음과 같이 3가지로 생각해 볼 수 있습니다.

① 탐색을 위한 자료구조 구성
② 효율적인 자료 정리
③ 자료의 상이성, 중복성을 탐색

첫 번째에 나와 있는 탐색을 위한 자료구조의 구성 의미가 뭘까요? 독자 여러분이 아주 많은 데이터, 예를 들어 전국의 땅에 관한 데이터를 관리하는 사람이라고 할 때 전국에서 가장 비싼 땅의 데이터를 알려달라는 요청이 들어왔습니다. 이러한 경우 가장 쉬운 방법으로 전체 데이터를 한번씩 읽으면서 제일 비싼 땅을 찾아 결과를 줄 수 있습니다. 그런데 10분 뒤에 다시 가장 비싼 땅과 가장 싼 땅의 데이터를 달라고 하고, 잠시 뒤 가장 비싼 상위 100개의 땅의 정보를 달라고 요청했다고 가정해 봅니다. 이럴 경우 요청이 들어올 때마다 데이터를 다 뒤져서 값을 찾아줄 수 있습니다.
하지만 하루에 몇 백건 혹은 몇 천 건이 들어오는 데이터라면 매번 이런 방법을 사용할 수 없을 것입니다. 관리자가 전체 데이터를 정렬해 두었다면, 요청이 들어왔을 때 정렬된 데이터의 앞의 몇 개, 뒤의 몇 개씩으로 바로 결과를 줄 수 있습니다. 따라서 탐색이 많은 데이터의 경우에는 전체 데이터를 정렬해두면 탐색에 좋은 자료가 되겠지요. 그리고 이런 경우 자료를 효율적으로 정리하고 있다고 말할 수 있습니다. 이게 바로 두 번째 의미이겠지요.
마지막에 있는 자료의 상이성, 중복성을 탐색하는 것은 학생들의 학번을 예로 들어 설명해 보겠습니다. 학번은 학생들 개개인에게 하나씩 주어지는 것으로 모두 상이해야 합니다. 학생 데이터를 관리하는 관리자가 학생들의 데이터를 학번 순으로 모두 정렬해서 관리한다고 하면, 학생들의 데이터를 정렬할 때 같은 학번이 나타나는 것을 찾아낼 수 있습니다. 그러면 관리자는 학번이 잘못 입력되었거나, 학생에게 잘못 주어졌을 경우 또는 같은 학생이라는 것을 조사해 볼 수 있습니다. 이렇게 입력 자료가 상이하거나 중복되어 있음을 찾아낼 때에도 정렬을 사용할 수 있습니다.
그럼 정렬이 어떤 것이고, 어떠한 성능이 좋은지를 모두 아셨죠? 이젠 정렬 알고리즘의 종류에 대해서 알아보겠습니다. 이번 호에서 사용할 정렬 알고리즘은 앞에서 말했던 숫자 데이터를 입력으로 하는 수치 정렬에 대한 것입니다.

수치 정렬 알고리즘이란?
수치 정렬 알고리즘이란 입력 데이터가 숫자 데이터라는 것입니다. 그럼 수치 정렬의 결과는 무엇일까요? 앞에서 이야기했듯이 입력 데이터들의 크기에 따라 내림 또는 오름차순으로 정렬된 숫자 열이 될 것입니다. 수치 정렬 알고리즘에는 다음과 같은 알고리즘들이 있습니다.

① 버블 정렬(bubble sorting)
② 선택 정렬(selection sort)
③ 삽입 정렬(insertion sort)
④ 퀵 정렬(quick sorting)
⑤ 힙 정렬(heap sorting)

물론 이외에도 여러 정렬 알고리즘들이 존재합니다. 이번 연재에서는 수치 정렬의 기본이 되는 버블, 삽입, 퀵 정렬에 대해서 알아보도록 하겠습니다. 알고리즘들은 모두 같은 예를 사용해서 해보겠습니다. 그래야 서로 어떻게 다른지를 금방 느낄 수 있겠죠?
우리가 최종적으로 만들어 낼 학생 성적 관리 시스템을 예로 생각해 보겠습니다. 우선 학생수가 많으면 손으로 풀어보기가 힘드니 적은 학생 수로 시작해 볼까요? 모두 7명의 학생이 있습니다. 국어 시험을 쳤는데, 학생의 성적이 [67, 33, 21, 84, 49, 50, 75] 이렇게 나왔습니다. 우리가 원하는 결과는 학생의 성적을 오름차순으로 정렬하는 것입니다.

수치 정렬(1), 버블 정렬
버블 정렬은 정의하면 다음과 같습니다.

◆ 버블 정렬 : 매 단계에서 인접한 원소들을 비교 및 교환하면서 가장 큰 키의 원소를 정렬하고자 하는 부 리스트의 마지막으로 보낸다.

정의를 살펴볼까요? “매 단계에서 인접한 원소들을 비교 및 교환한다”라고 되어 있죠? 다시 말해 예제의 처음 두 점수를 보면 67과 33이죠? 67과 33을 비교하면 67이 더 크죠? 이렇게 비교를 한 다음에 67이 더 크므로 67과 33의 자리를 바꾸는 교환 작업을 수행합니다. 그런데 “가장 큰 키의 원소를 정렬하고자 하는 부 리스트의 마지막으로 보낸다”라고 되어 있죠? 이것은 지금 우리가 비교하고 있는 데이터 67, 33 중에서 67이 제일 크니 67이 두 수 중에서 가장 뒤로 가게하라는 말입니다. 만약 67, 33, 21을 본다면 67이 이 세 수의 가장 마지막에 갈 때까지 방금한 것처럼 두 개씩 비교하면서 교환이 필요하면 교환을 하는 것입니다. 이해가 되죠? 그럼 전체 데이터를 가지고 실행을 해보도록 하겠습니다. 예제는 손으로 꼭 해봐야 합니다.
<표 1>처럼 6번째 단계(처음 두 수를 비교하는 단계)까지 수행되고 나면 입력된 데이터들이 모두 정렬이 되는 것입니다. 그럼 버블 정렬을 분석해 볼까요? <표 1>의 마지막 항을 보면 비교 횟수라고 되어 있죠? 비교 횟수는 한 단계에서 부 리스트에 수행되는 비교의 횟수를 모두 더한 것입니다. 첫 단계를 살펴보면, 부 리스트의 데이터가 모두 7개죠? 따라서 6번의 비교가 있는 것입니다. 두 번째 단계는 5번, 세 번째 단계는 4번 이런 식으로 비교 횟수가 하나씩 줄어듭니다. 따라서 예에서처럼 입력 데이터의 수가 7개인 경우에는 모두 21번의 비교가 수행됩니다.

6 + 5 + 4 + 3 + 2 + 1 = 21

이를 식으로 나타내면 다음과 같습니다.

( n - 1) + ( n - 2) + ··· + 2 + 1 = n ( n - 1)
2

<표 1> 버블 정렬 방법

그럼 이제 코딩을 해볼까요? 자바의 클래스로 구현해 보겠습니다. 버블 정렬이니 클래스 이름은 bubblesort로 정합니다. 버블 정렬에 필요한 데이터는 숫자 데이터이므로 그냥 1차원 배열로 하겠습니다. 데이터 외에 버블 정렬을 위한 함수와 정렬된 데이터를 프린트할 함수를 정의해 둡니다.
먼저 <리스트 1>처럼 틀을 만들어두고 나서 본격적으로 알고리즘을 코딩으로 바꾸어 보도록 하겠습니다. 버블 정렬의 주요 알고리즘은 인접한 두 데이터를 비교하고 오름차순에서 앞의 데이터가 더 크다면 뒤의 데이터와 교환하는 것입니다. 이를 코딩으로 바꾼다면 어떻게 할까요? 우선 ‘인접한 두 데이터를 비교한다’는 것은 if문을 사용하면 되겠죠? 앞의 데이터가 더 클 경우 교환이 일어나므로 다음처럼 할 수 있습니다.

if(data[i-1] > data[1])

그럼 데이터를 계속 처음부터 끝까지 비교하나요? 아니죠. 비교하는 리스트에서 가장 큰 데이터가 제일 마지막으로 옮겨지므로, 처음에는 배열의 끝까지 비교를 하고 그 다음 번엔 끝에서 하나를 뺀 곳까지 비교하면 됩니다. 이런 식으로 비교가 계속될 것이므로 이를 for문을 사용하여 나타낼 수 있습니다. 지금까지 이야기한 것을 코딩하면 다음과 같습니다.
<리스트 2>에서 교환에 사용되는 코드는 다른 정렬 알고리즘에서도 사용되는 코드이므로, swap()이라는 함수를 만들어서 사용하는 것이 좋습니다. swap 함수는 두 데이터 a, b의 값을 서로 교환하는 함수입니다. swap 함수에서 값이 변하면 이것이 원래 데이터에 영향을 미쳐야 하므로 배열의 인덱스 값을 넘겨서 배열의 값을 교환해 보겠습니다,
<리스트 3>을 적용하면, <리스트 2>는 <리스트 4>와 같이 바꿀 수가 있습니다.

수치 정렬(2), 삽입 정렬
삽입 정렬은 정의하면 다음과 같습니다.

◆ 삽입 정렬 : 새로운 원소를 정렬된 리스트(ordered list)에 삽입하여 다시 정렬된 리스트를 만드는 과정을 반복한다.

정의를 보면 원소를 정렬된 리스트에 하나씩 추가하면서 리스트를 다시 정리하는 거라고 되어 있죠? 제일 처음에는 정렬된 리스트가 비어 있겠죠? 여기에서 첫 번째 원소인 67을 삽입합니다. 아무것도 없는 리스트이니 당연히 67을 삽입한 그 자체가 정렬이 되어 있는 것이겠죠? 그 다음 33을 넣도록 하겠습니다. 33이 더 작으니까 67의 앞이 33의 위치가 되겠죠? 그래서 정렬된 리스트가 ‘33, 67’이 되는 겁니다.
세 번째 원소인 21이 삽입되면 정렬된 리스트의 마지막 원소가 67이므로 67과 우선 비교를 하게 됩니다. 21이 67보다 작기 때문에 21은 67의 앞에 위치하게 됩니다. 67 앞에 33이 있으므로 21은 33과 다시 비교하게 되고, 33보다 21이 더 작기 때문에 33의 앞에 21이 위치하게 됩니다. 4번째 원소인 84가 삽입되면 정렬된 리스트의 모습이 어떻게 변하게 될까요? 세 번째 원소가 삽입돼 정렬된 리스트의 마지막 원소가 67이죠? 그럼 우선 67과 84를 비교합니다. 84가 67보다 크죠? 그럼 그 다음 원소인 33과 84를 비교할 필요가 있을까요? 이미 세 번째 데이터까지는 모두 정렬이 되어 있기 때문에 67이 84보다 작은 데이터라는 것은 그 앞의 데이터는 당연히 더 작다는 뜻이 됩니다. 따라서 84는 67의 뒤인 정렬된 리스트의 마지막에 84가 삽입되게 됩니다.
그럼 이제 알고리즘을 분석해 볼까요? 삽입 알고리즘이 가장 많이 수행되는 시간은 새로운 원소를 정렬된 리스트에 추가할 때 정렬된 리스트 원소들과 비교하는 것입니다. 만약 새로운 원소가 정렬되어 있는 첫 번째 원소보다 작다면 새로운 원소의 위치는 리스트의 처음이 되고 비교 횟수는 한 번입니다. 만약 새로운 원소가 정렬된 리스트의 마지막 원소보다 크다면 정렬된 리스트의 원소의 수만큼 비교를 하게 됩니다. 이를 식으로 나타내면 다음과 같습니다.

1 + 2 + 3 +·· + ( n - 1) = n ( n - 1)
2
우리가 손으로 직접 풀어본 예제를 코딩으로 옮겨볼까요? 삽입 정렬은 입력 데이터의 마지막 데이터부터 처음 데이터까지 자신의 값과 비교하면서 위치를 찾아가는 것입니다. 그러면 ‘입력 데이터의 마지막 데이터부터 첫 번째 데이터까지 하나씩 데이터를 선택한다’는 무엇으로 코딩할 수 있을까요? for문을 이용하면 되겠죠? 그리고 다시 처음부터 자신의 위치를 찾는 것은 어떻게 알 수 있을까요? 만약 두 번째 데이터라면 입력 배열(data)의 마지막 원소가 하나(67)뿐이므로 그 데이터만을 비교하면 되겠죠? 만약 다섯 번째 데이터가 삽입된다면 네 번째 데이터까지 정렬된 리스트에서 비교를 하므로 리스트의 네 번째 데이터와 세 번째 데이터 순으로 두 번째 데이터까지 비교하는데 두 번째 데이터가 자신보다 작다면 비교를 그만두고 세 번째 데이터 위치에 다섯 번째 데이터를 넣으면 되겠죠?
그런데 만약 세 번째 위치에 다섯 번째 데이터를 넣는다면 원래 세 번째에 있던 데이터는 어디로 가야하죠? 바로 다섯 번째 데이터와 교환하면 될까요? 세 번째는 네 번째로, 네 번째는 다섯 번째로 옮겨야합니다. 따라서 비교를 하면서 자신이 더 클 때까지 비교한 데이터를 계속 교환해서 나가면 됩니다. 이를 코딩으로 옮기면 <리스트 5>와 같이 할 수 있습니다.

<표 2> 삽입 정렬의 방법

수치 정렬(3), 퀵 정렬
퀵 정렬을 정의하면 다음과 같습니다.

① 분할
리스트에서 피봇(pivot) 키의 원소를 선택하여 리스트를 다음과 같이 분할한다.
- 피봇 키의 값보다 작은 키를 가진 원소들을 피봇 키 원소보다 앞에 둔다.
- 피봇 키의 값보다 큰 키를 가진 원소들은 피봇 키 원소보다 뒤에 둔다.
② 재귀적 퀵 정렬 : 피봇 키의 원소 앞뒤의 부 리스트들에 각각 퀵 정렬을 수행한다.

퀵 정렬도 말로 설명을 하는 것보다 우선 예제를 보고 손으로 먼저 해 보는 것이 좋습니다.
퀵 정렬은 피봇라는 데이터를 하나 정하고, 입력 데이터를 피봇 데이터보다 큰 것과 작은 것으로 분할하는 분할 작업이 주된 작업입니다. 분할 작업이 한번 수행되면 피봇 앞에 있는 데이터는 피봇보다 큰 것이고, 피봇 뒤에 있는 것은 피봇보다 작은 데이터들이 모입니다. 이렇게 분할 된 데이터는 다시 각각을 분할 작업을 수행하게 됩니다. 만약 분할된 리스트의 데이터 수가 2라면 이는 두 데이터만을 비교하고 교환하여 정렬할 수 있습니다. 더 이상 분할할 리스트가 없을 때까지 수행되는데 이는 재귀적으로 수행할 수 있습니다.
이를 코딩으로 나타내 볼까요? 우선 퀵 정렬을 재귀적으로 호출하는 것부터 해봅시다. 재귀적으로 호출한다는 것은 자신을 다시 호출한다는 거죠? 피봇 데이터가 리스트에서 들어갈 위치가 j라고 한다면, 피봇보다 작은 데이터들의 리스트와 피봇보다 큰 데이터들의 리스트를 다시 퀵 정렬의 입력으로 넣기만 하면 됩니다. 퀵 정렬의 입력 데이터의 위치가 left~ right까지 이었다면 다음처럼 나타낼 수 있습니다.

QuickSort(left, j-1);
QuickSort(j+1, right);

그럼 피봇 데이터가 들어갈 위치를 찾는 것은 어떻게 할까요? 퀵 정렬의 분할 알고리즘의 두 조건 생각나죠? 이 두 조건을 수행하기 위해서 while문을 수행합니다. 그러면 다음처럼 나타낼 수 있습니다.

// 리스트의 제일 처음 데이터부터 피봇 데이터보다 큰 값인 데이터를 찾는다.
do i++;
while(i // 리스트의 제일 마지막 데이터부터 피봇 데이터보다 작은 값을 찾는다.
do j--;
while(j>left && data[j] > pElement);

그럼 이젠 퀵 정렬을 분석해 보겠습니다. 퀵 정렬의 최악의 경우는 리스트가 역순으로 정렬되어 있는 경우입니다. 왜냐하면, 역순으로 정렬된 경우에는 분할을 n -1번 수행해야 하고, i번째 분할에서 비교횟수는 n -i 가 되기 때문입니다. 따라서 총 비교횟수는 다음과 같습니다.

( n - 1) + ( n - 2) + ··· + 2 + 1 = n ( n - 1) ①
2

수치 정렬 정리
이번 호에서 살펴본 세 가지 정렬 알고리즘인 버블, 삽입, 퀵 정렬의 성능을 비교해보는 일이 남았습니다. 세 정렬을 살펴볼 때 이미 각각의 알고리즘의 성능 분석을 했습니다. 다시 살펴볼까요?
모두 앞의 ①이라고 되어 있습니다. 그러면 세 알고리즘의 성능이 모두 같다는 말일까요? 다시 살펴보면 버블 정렬의 경우는 항상 만큼의 수행시간이 필요합니다. 삽입 정렬과 퀵 정렬의 경우에는 입력된 데이터가 역순일 경우에
만큼의 수행시간이 필요합니다. 따라서 일반적인 데이터일 경우에는 버블 정렬보다는 삽입 정렬이나 퀵 정렬이 빨리 수행된다고 볼 수 있습니다. 하지만 데이터가 작을 경우에는 버블 정렬이 더 빠를 수 있으며, 퀵 정렬의 경우 함수를 재귀적으로 호출해야하기 때문에 시간이 더 걸립니다. 요즘 우리가 사용하는 컴퓨터의 성능으로는 작은 데이터에서 각 알고리즘의 시간 차이를 알 수가 없습니다. 하지만 국가 차원에서 다루는 데이터나 기업, 학교 같이 대용량의 데이터를 다루는 곳에서는 어떤 알고리즘을 사용하느냐에 따라 시간차이가 나므로 자신에게 알맞은 알고리즘을 사용해야겠습니다.

모든 알고리즘 코딩을 직접?
프로그램을 개발할 때 기초가 되는 자료구조나 알고리즘을 모두 코딩해서 사용하는 것은 작성하는 프로그램 오류를 증가시킬 수 있습니다. 물론 이번 호에서 살펴본 간단한 알고리즘이나 자신이 개발하거나 수정한 알고리즘 같은 경우는 코딩을 하겠지만, Red-Black Tree와 같이 복잡한 자료구조를 사용할 때에는 능숙한 프로그래머라도 실수를 할 수 있습니다. 실수를 하지 않더라도 개발 시간이 많이 걸리겠죠? 이렇게 직접 구현하는 것보다 이미 구현되어 있는 검증된 라이브러리를 이용하는 것이 효율적일 수 있습니다. 현재 전 세계적으로 많은 알고리즘들이 라이브러리화되어 있지만, STL, 알고리즘 리파지토리와 같은 라이브러리가 많이 사용되는 라이브러리입니다. 이중 LEDA는 많은 자료구조와 알고리즘이 구현되어 있습니다. 물론 알고리즘이나 자료구조를 배우고 있는 학생이라면 한번쯤은 코딩을 하는 것이 좋은 경험이 될 것입니다.
이번 호를 보면서 ‘너무 쉬워’라고 생각한 독자도 있을 것입니다. 하지만 이번 연재는 처음 알고리즘이라는 것을 접하고 이를 어떻게 해결해야 할까를 고민하는 독자를 대상으로 한 것이므로 이러한 독자들에게는 많은 도움이 되었기를 바랍니다

'고니의사진방' 카테고리의 다른 글

[쩐의전쟁] 뮤비 - 심플라이프 (0)	2007/06/14
Phishing Attacks (0)	2007/06/14
기초부터 차근차근 ‘정렬 알고리즘’ (0)	2007/06/08
사돌이 사순이 빈볼시비 (0)	2007/06/01
유리잔 연주 (0)	2007/04/22
바나나폰 CF (0)	2007/04/21