[자료구조] 정렬 알고리즘 간의 정렬 실행시간 및 정렬 속도 비교 레포트

목차

I. 단순하지만 비효율적인 정렬 방법
1. 삽입 정렬
2. 선택 정렬
3. 버블 정렬
4. 단순하지만 비효율적인 방법 비교 및 분석

II. 복잡하지만 효율적인 정렬 방법
1. 쉘 정렬
2. 퀵 정렬
3. 히프 정렬
4. 합병 정렬
5. 기수 정렬
6. 복잡하지만 효율적인 방법 비교 및 분석

III. 퀵 정렬과 기수 정렬의 비교
1. 느 낀 점

본문내용

기수정렬은?

기수 정렬은 레코드를 비교하지 않고도 정렬하는 방법이다. 버켓을 만들어서 입력 데이터를 각 자릿수의 값에 따라 버켓에 넣는다. 그리고 위에서부터 아래로 순차적으로 버켓안에 들어 있는 숫자들을 읽음으로써 정렬된 숫자 리스트를 얻을수 있다. 그러나 레코드의 타입이 한정된다는 단점이 있다. 여기에서 버켓은 큐를 이용하여 구성하게 된다.
기수 정렬은 복잡하지만 효율적인 정렬방법 이다.

기수정렬의 복잡도

기수 정렬은 다른 정렬방법들의 비교와 이동 연산을 수행하는 방법과는 달리 데이터를 비교하지 않고도 정렬하는 방법이므로 d(숫자의 자리수)에 비례하게 된다. 그러므로 O(dn)의 시간 복잡도를 가지게 된다. 따라서 기수 정렬은 다른 정렬 방법에 비하여 비교적 빠른 수행 시간안에 정렬을 마칠 수 있다.

<중략>

복잡하지만 효율적인 정렬들의 실행시간을 모두 비교해 보았다. 동일한 조건으로 난수를 발생시키고 발생한 난수들(동일한 데이터)를 이용해서 비교해보았는데, 퀵정렬 > 쉘정렬 >　합병정렬 > 기수정렬 > 히프 정렬 순서로 나타났다. 내가 예상했던 실행시간 속도는 퀵정렬 > 합병정렬 > 히프정렬 > 쉘정렬 순이었는데, 실행시간을 측정한 결과 위의 그래프의 결과를 나타내었다.

이 실행시간 결과를 보고 나니 단순하지만 비효율적인 정렬방법과 복잡하지만 효율적인 정렬방법의 정렬을 수행하는 시간의 차이가 정말 엄청나게 크게 난다는 사실을 확실하게 알 수 있었다.

<중략>

퀵정렬과 기수정렬을 비교하는 표이다. 위의 두 개의 표를 보면 함수 호출을 하면 실행시간이
확실히 늘어난다는 것을 알 수 있다. [표_1]의 경우에는 퀵정렬과 기수정렬의 정렬속도가 상당히 많이 차이난다는 것을 알 수 있다. 그러한 이유로 함수 호출을 예로 들을 수 있는데, 기수 정렬은 큐를 구성하고 큐를 이용하여 정렬을 하는 방식이다.

참고자료

· 없음