기본 콘텐츠로 건너뛰기

Sorting algorithm 성능비교



그림출처 : http://dev-ahn.tistory.com/39

삽입정렬의 경우, 정렬대상이 완전히 정렬된 상태라면 안쪽 for문에서 걸리지기 때문에 시간복잡도는 O(n)이 된다.

병렬정렬의 경우, 임시메모리가 필요하다는 단점이 있다. 하지만 연결리스트를 정렬할 때는이런한 단점을 극복할 수 있다.

힙정렬의 경우도 힙저장공간이 필요하다는 단점이 있다.

퀵소트의 경우, 최악의 경우는 이미 데이터들이 정렬된 상태이고 pivot이 가장 작은 값으로 결정되는 경우이다. 이 경우 데이터가 둘로 나뉘는 횟수 k = n이고 되고
결과적으로 O(n^2)이 된다.
참고로, pivot값을 가운데에 두면 성능이 개선된다.

Radix(기수)정렬의 경우, 성능은 가장좋지만 적용할 수 있는 범위가 제한적이다.
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

Dijkstra 알고리즘과 실행시간(Priority Queue를 사용하는 이유)

정의 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘 알고리즈 개요 데이크스트라 알고리즘은 각각의 꼭짓점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다. 데이크스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지 길이가 w(u,v)인 변 (u, v)가 존재할 때, s에서 v까지의 최단 경로는 u까지의 최단 경로에 변 (u, v)를 추가함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다. 경감 연산은 모든 변 (u, v)에 대해 한번씩 경감이 적용되어 모든 d[v]가 최단 경로의 비용을 나타내게 되었을 때 끝난다. 실행시간 개의 변과  {\displaystyle n} 개의  꼭짓점 을 가진  그래프 에 대해  대문자 O 표기법 으로 데이크스트라 알고리즘의 실행시간을 나타낼 수 있다. 가장 간단한 구현으로,  Q 의 집합을  연결 리스트 나  배열  구조로 구현하고 Extract-Min(Q) 함수를 단순한  선형 탐색 으로 구현했을 때 실행 시간은  {\displaystyle O(n^{2})}  시간이 된다. 만약 희소 그래프(sparse graph), 즉  {\displaystyle n^{2}} 보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는,...
댓글 쓰기
자세한 내용 보기