알고리즘 - C로 구현한 삽입,병합,힙,퀵,카운팅 정렬 성능비교

소개글

알고리즘 - C로 구현한 삽입,병합,힙,퀵,카운팅 정렬 성능비교에 대한 보고서 자료입니다.

목차

Sorting Algorithms 구현하기

각각의 알고리즘의 수행시간에 대한 그래프와 성능분석

Merge Sort

Heap Sort

Quick Sort

Count Sort

*환경(컴퓨터 사양)

본문내용

Count Sort
구현 원리 : 입력키가 어떤 범위, 예를 들어 0부터 k사이의 작은 정수범위에 있다는 것을 알고 있을 때만 적용할 수 있는 방법이다. 즉 그 사이에 있다고 가정한다. 이럴 때 어떤 입력 키 x의 정렬 위치는 x보다 작은 키가 몇개나 입력에 나타나는지를 알면 결정할 수 있다. 예를 들어 입력키들이 숫자일 때 입력에 10이라는 키가 있고 이보다 작은 키가 5개 있다면10은 정렬순서에서 6번째에 위치하게 될 것이다. 따라서 계수정렬에서는 입력 키들이 범위 k내의 각 값에 대하여 입력키가 실제로 입력에 나타나는 횟수를 계산한다.
장점 : 시간복잡도는 O(n + k)인데 보통 k=O(n)일 때에만 사용되므로 실질적인 시간복잡도는 O(n)이라고 할 수 있다. 또한 동일한 값을 가지는 키의 상대적 순서(정렬하기 전의 순서)가 바뀌지 않는 안정적 정렬이라는 것이다.
단점 : 정렬을 위한 메모리 공간이 더 필요하다. 처음의 값을 가지는 공간과 정렬을 위한 공간, 그리고 정렬된 값들을 나열하기 위한 공간까지 필요하므로 메모리를 많이 쓴다는 것은 단점이라고 할 수 있지만 이 과정에서 순서를 바꾸지 않는 안정성을 보여주므로 단점이지만 장점이 될 수 있다고도 할 수 있다.

키워드

알고리즘,   정렬,   삽입정렬,   병합정렬,   힙정렬,   퀵정렬,   카운팅정렬,   정렬 성능비교