[자료구조]sort

소개

Sort는 여러 종류의 정렬 알고리즘을 비교/분석하기 위한 프로그램입니다.
두 가지의 문제가 있는데, 하나는 bubble, insertion, shell, merge, quick, radix sort 의 속도를 비교하는 것입니다. 각각의 소트 알고리즘에 대해서 기본 전략 및 특징, 구현 방법, 실행 속도를 분석하고 좀 더 개선된 알고리즘에 대한 방안을 제시하는 형태로 구성되어있습니다. 실행 속도는 파일로부터 자료를 입력받아 정렬하고, 정렬까지 걸리는 시간을 측정합니다.
다른 하나는 k_way merge sort의 k값에 따른 속도 변화를 살피는 것입니다.

목차

I. 요구 조건

II. 설계
1. bubble sort (거품 정렬)
2. insertion sort (삽입 정렬)
3. shell sort
4. merge sort (병합 정렬)
5. quick sort
6. radix
7. 종합 분석
8. n_way merge

III. 영향
1. 평가
2. 배운점
3. 알려진 버그와 한계

reference

본문내용

1. bubble sort (거품 정렬)

1.1 기본 전략 및 특징
bubble sort는 인접한 요소들끼리 서로 비교하여 교환하여 큰값을 차례로 뒤로 보내는 식입니다. 따라서 n번의 비교 및 교환 후에는 가장 큰 값이 가장 끝에 위치하게 됩니다. 다음에는 n-1까지 비교교환을 실시하고... 이것을 n-2, n-3 ... 까지 반복 수행하면 전체적으로 정렬이 됩니다.
알고리즘 수행시의 총 비교 횟수는 로 의 시간 복잡도를 갖습니다. 메모리는 추가 공간 없이 기존의 원시 리스트가 사용하는 공간에서 정렬됩니다. 동일한 key 값을 가질 경우 본래의 자료 순서를 유지하는 안정성이 있는 stable sort 입니다.
가장 간단하고 널리 알려진 방식이고 구현하기도 쉽지만, 많은 비교와 교환 횟수로 자료 수가 증가함에 따라 시간이 제곱으로 증가하는 가장 느린 알고리즘 중 하나입니다.

1.2 구현
이중 루프를 돌리는데, 이 중 내부 루프에서는 리스트의 정렬되지 않은 부분들의 인접한 요소를 비교해서 큰 것을 뒤로 보냅니다. 따라서 내부 루프가 완전히 돌 때마다 가장 큰 값이 가장 끝으로 이동하고 이것을 외부 루프에서 리스트의 맨 끝에서 맨 앞까지 반복하게 해줍니다. bubble sort에서는 특정 자료에 대한 액세스와 교환이 많이 이루어지기 때문에 랜덤 액세스가 가장 효율적인 배열을 사용했습니다.

1.3 실행 속도 분석
실제 측정 결과는 bubble sort의 특징을 잘 보여주고 있습니다. n이 5000에서 10000이 될 때나, 10000에서 20000이 될 때 등을 살펴보면, n이 2배가 되면 실행 속도는 약 4배 정도로 제곱에 비례해서 증가하고 있다는 것을 알 수 있습니다.
이 알고리즘에서 최선의 경우는 주어진 배열이 이미 정렬된 배열일 경우입니다. 이 경우의 비교 횟수는 지만 교환이 일어나지 않습니다.
최악의 경우는 역순 배열의 경우인데, 이 경우 비교 횟수와 교환횟수가 모두 로, 이 때 최대의 비교와 교환이 이루어지게 되어 최악의 실행 속도를 나타냅니다.

참고자료

· C로 배우는 알고리즘 I, 이재규, 도서출판 세화, 1994
· 파스칼로 구현한 자료구조, Ellis Horowitz and Sartaj Sahni, 이철회외 역, 회중당, 1992
· Data Abstraction and Problem Solving with JAVA: Walls and Mirrors, Frank M. Carrano and Janet J. Prichard, Addison-Wesley, 2001
· Computer Systems: A Programmer’s Perspective, R. E. Bryant and D. O’Hallaron, Prentice-Hall, 2003