2014150029_sorting.zip1. 개요
설계 목적
- 해당 보고서는 C로 각 정렬 알고리즘을 책이나 깃허브의 소스를 이용하여 간편하게 구현하였으며, 성능 테스트를 목적으로 구현하였다. 해당 소스는 첨부파일로 확인 가능함.
- 첨부한 파일은 소스코드와 텍스트 파일로, 텍스트 파일은 영화 정보가 담겨있음. 영화정보는 영화 ID값, 제목, 년도, 장르로 구성되어 있음. 각 항목별로 데이터를 추출하는 과정에서 장르가 없는 것도 있고 얼핏 보면 항목별 구분자가 콤마 인것처럼 보이지만 제목 안에도 콤마가 들어가는 경우도 있기 때문에 이를 잘 고려해서 파일 입출력 부분 코드를 작성해야 함.
- 다양한 자료구조를 이용하여 목적에 따라 효율적인 알고리즘을 구현 할 수 있는 능력을 향상시키기 위함. 특히 이번 보고서는 정렬 알고리즘을 기준으로 설명.
- 다양한 개수, 종류의 입력 데이터를 가지고 삽입정렬, 합병정렬, 퀵정렬, 힙정렬, 기수정렬, 계수정렬을 사용하여 데이터를 정렬하는 코드를 직접 구현하기 위함.
- 이러한 정렬과정을 통해 수행 시간을 측정하고, 이를 통해 입력 데이터의 종류와 알고리즘 별 성능과 Stability를 확인하기 위함.
- 실제 측정한 시간을 통해 각 알고리즘 별 ‘시간복잡도‘와 비교하여 수업 때 학습한 내용을 비교학습하고, Stability가 어디서 유지되고 깨지는 지를 확인하기 위함.
- 최종 적으로 어떠한 자료구조를 이용하고, 어떠한 알고리즘을 사용 했을 때 효율적인 성능 기반의 데이터를 얻을 수 있는지 확인하기 위함
프로그램 수행 시나리오
(1) 입력 데이터는 주어진 데이터 약 33000개의 영화 관련 내용을 사용하고 입력 데이터를 3천개 씩 쪼개어 대략 11개의 입력 데이터로 분할 함
(2) 정렬 순서는 ( 타이틀 – 년도 ) 순으로 정렬하고 각 정렬이 끝나면 수행 결과를 표시할지 선택을 하고 측정된 시간을 표시함. 두 번의 정렬이 끝나면 데 이터는 정렬되지 않은 원래의 데이터로 돌아옴.
(3) 각 정렬마다 ( 타이틀 – 년도 ) 순으로 정렬을 하고 5개 정렬의 수행시간 확인
(4) 측정된 결과를 그림 및 그래프를 사용하여 성능 분석.
2. 본론
삽입 정렬
삽입정렬은 하나의 ‘키’를 설정하여 그 ‘키’를 기준으로 좌측 데이터를 비교하며 정렬을 해나감. 입력 데이터를 배열에 저장하고 맨 좌측 데이터는 비교할 것이 없으 므로 그다음 값을 키로 설정하고 시작.
‘키‘를 이용하여 비교할 할 때 ‘키‘ 값을 저장할 임시 공간을 마련. 임시 공간의 데이터 형식은 구조체의 멤버변수(년도 및 타이틀)을 가지고 비교해야 함으로 선언한 구조체 형식으로 생성. (문자열 비교시는 strcmp 함수를 사용해야 함)
1단계에서 인덱스 1번의 값인 1994를 ‘키‘ 값으로 잡고 임시 공간에 저장
키 값 좌측의 값인 1995와 비교함.
1995가 더 큰 값이므로 비교대상을 오른쪽으로 이동시킴
더 이상 비교할 대상이 없으므로 ‘키‘ 값이 저장된 임시 데이터를 인덱스 0에 삽입하고 ’키‘ 값을 우측으로 하나 이동시킴.
여기서는 비교대상의 개수가 2개임. 키 값과 1995를 비교함.
키 값이 더 작으므로 1995를 우측으로 이동시킴
1904와 비교함. 키 값이 더 작으므로 1904를 우측으로 이동
더 이상 비교할 것이 없으므로 키 값을 인덱스 0 자리에 삽입.
이러한 과정을 반복하여 삽입 정렬 과정 진행함. 키 값과 비교하여 키 값 보다 작은 값이 나올 경우 이미 좌측의 값들은 정렬이 돼있다는 뜻이므로 키 값을 우측으로 변경하여 다시 위의 과정을 진행함.
키 값과 비교하는 과정에서 비교대상을 오른쪽으로 미는 경우는 오로지 키 값 보다 큰 값을 만나는 경우임. 따라서 작은 값 뿐만 아니라 같은 값을 가지면 비교를 중단함.
이 과정에서 같은 값의 input 데이터의 순서가 유지기 때문에 삽입 정렬은 stable 정렬임. 따라서 movies.txt 데이터를 ‘타이틀’로 정렬하고, ‘년도’로 정렬하면 같은 년도 내에서 타이틀의 정렬 순서가 유지됨.
삽입 정렬 – 성능 평가
정렬 대상이 완전히 정렬된 상태면, 비교대상이 계속 작거나 큰 값이므로 비교는 계속 False를 반환하게 되고 데이터의 이동도 발생하지 않음. 결국 키 값은 인덱스 1부터 n까지 n-1 번 세팅이 됨(데이터개수가 n일 때)
따라서 최선의 경우 시간복잡도는 n이 나옴. 하지만 반대로 최악의 경우를 고려했을 때 키 값을 기준으로 비교를 할 때 비교가 True가 되어 데이터의 이동이 계속 일어나면 키 하나당 키의 좌측 값을 계속 비교해 나가야 함.
따라서 키 설정 하는 n-1 횟수와 각 키 마다 키의 좌측 값 들과 비교를 하는 횟수(키가 맨 우측까지 가면 비교의 횟수는 n-1)를 곱하면 빅오 n^2이 나오게 됨.
위 그림이 바로 앞서 설명한 최악의 경우를 뜻함.
합병 정렬
합병 정렬은 divide and conquer 알고리즘 방식을 사용. divide and conquer 방식이란 수많은 데이터를 분할하여 해결하기 쉬운 상태로 만들고, 다시 그 결과를 결합해나가 최종적으로 원하는 결과를 얻어내는 과정을 말함.
위 그림은 년도 데이터를 분할하는 과정임. 데이터 개수의 절반을 기준으로 계속 분할되어 나감. 알기 쉽게 전체적으로 분할되는 과정을 설명한 것이고, 사실 코드로 구현에 있어서는 위 그림과 같이 전체적으로 분할이 일어나는 것이 아님.
재귀호출을 이용하여 코드를 구현함. 그렇기 때문에 분할의 과정은 위 첫 번째 데이터를 분할하고, 분할된 왼쪽 데이터 영역을 또 재귀호출을 통해 분할이 이루어짐. 더 이상 왼쪽에서 두 개의 데이터를 비교하여 병합.
실제 코드로 구현할 시 실행되는 과정을 나타냄. 전체 데이터가 분할되고, 분할된 좌측 값을 또 분할함. 1->2->3 까지 분할하여 더 이상 쪼갤 것이 없으면 두 데이터를 정렬하여 병합함. 아직 파란색 선을 기준으로 우측 데이터는 그대로임.
그다음 5번이 수행됨. 5번에서 다시 분할을 시작하여 더 이상 쪼개 질 것이 없을 때까지 수행되고 병합함. 그다음 아까 4번에서 나온 결과와 비교하여 총4개의 정렬된 데이터로 병합함.
이렇게 되면 왼쪽 4개의 년도는 정렬이 종료된 상태임. 하지만 오른쪽 4개의 년도 데이터는 아직 그대로이기 때문에 위와 같은 방식으로 시작함.
만약 같은 년도의 데이터가 있다면 들어온 순으로 그대로 병합됨. 또한 다른 데이터와 병합 할 때도 입력 순으로 정렬됨으로 stable이 유지됨.
따라서 합병정렬도 stable한 정렬임.
합병 정렬 – 성능 평가
분할하는데 걸리는 시간은 중간 값만 구하면 되기 때문에 상수시간이 걸림
n개의 데이터를 분할하고, 재귀적으로 또 분할하는데, 각 부분 문제는 크기가 n/2이므로 t(n/2)+t(n/2)만큼 시간이 걸림
병합하는 과정은 n개의 데이터를 n번 비교해야 하므로 O(n) 만큼 걸림.
recursion tree를 이용하여 시간복잡도를 계산할 수 있음. 각 레벨별 비용은 n만큼 들게 됨. 계속 분할하다보면 더 이상 분할 할 수 없는 구간이 나오고 t(1)이 바로 그 경우임.
0레벨 | n |
1레벨 | n/2 |
2레벨 | n/2(^2) |
k레벨 | n/2(^k) |
t(1)은 n/2(^k) = 1 이 되는 경우를 뜻함. 따라서 k는 log(n)으로 표현 가능. 즉 이는 트리의 높이를 뜻하고 각 레벨별 비용은 n이므로 recursion tree를 통해 병합정렬의 시간복잡도가 nlog(n)인 것을 알 수 있음.
퀵 정렬
퀵 정렬도 앞서 말한 divide and conquer 방식을 기반으로 함. 피벗이라는 기준점을 하나 잡고 피벗 기준으로 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 위치시킴. 하나의 데이터가 두 영역으로 분할됨
분할된 두 영역에서 위와 같이 피벗을 설정하고 피벗기준으로 작은 값은 좌측, 큰 값은 우측으로 이동시키는 파티셔닝이 일어남. 피벗은 맨 우측 값으로 기준잡음.
1. 맨 우측 값을 피벗으로 설정하고 각 start, end를 설정.
2. 인덱스 i 의 값과 피벗과 비교해서 피벗보다 작으면 point 값 과 스왑하고. point를 하나 증가시킴. 아니면 그냥 i 만 증가.
3. 1999, 2013 둘다 큰 값이므로 I만 증가함. 1814는 피벗보다 작으므로 point가 가리키는 값과 스왑하고 pointer와 I는 하나 증가.
4. 현재 I가 가리키는 값은 피벗보다 크므로 종료. 이제 point가 가리키는 값과 피벗을 스왑.
5. 피벗을 기준으로 좌측은 작은 값, 우측은 큰 값으로 정렬됨. 이제 좌우측을 또 다시 분할해서 진행함. 위 과정을 재귀적으로 진행하면 됨.
퀵 정렬 – 성능 평가
일단 퀵 정렬은 1999(1), 2013, 1999(2), 1814, 1997 이러한 데이터가 있다면 위에서 설명한 과정을 거쳤을 때 1884 1997 1999(2) 1999(1) 이렇게 1999 데이터의 입력 순서가 깨짐으로 unstable한 정렬임.
퀵 정렬은 피벗의 위치를 찾는게 성능을 판별함. 만약 데이터가 이미 정렬되어 있는 상태라면, 피벗을 맨 우측으로 잡든 좌측으로 잡든 끝까지 다 비교하게 됨. 즉 n개의 데이터가 있으면 n-1번 확인하고 피벗의 위치는 그대로임.
이렇게 n번을 수행하게 되면 최악의 경우 시간복잡도는 O(n^2)임
하지만 데이터가 이미 정렬되어 있는 경우는 매우 드물고, 피벗에 의한 분할이 만약 1: 9 이렇게 한쪽으로 치우치게 되어도. 매번 같은 비율로 이렇게 분할되면 시간복잡도는 O(n*log(n))임. 그림을 보면 쉽게 이해감.
위 그림은 매번 분할이 균등하게 1:9 비율로 이루어짐. 위 그림을 모형화 하면 다음과 같음.
1 : 9 비율로 recursion tree를 그리다 보면 전체적으로 봤을 때 이런 모양이 나옴. 점선을 기준으로 루트 기준 좌측 서브 트리가 빨리 리프노드에 도달. 왼쪽 서브트리와 오른쪽 서브트리의 높이는 다음으로 구할 수 있음.
레벨 | 좌측 서브트리 높이 | 우측 서브트리 높이 |
0 | n(1/10)^0 | n(9/10)^0 |
1 | n(1/10)^1 | n(9/10)^1 |
2 | n(1/10)^2 | n(9/10)^2 |
k | n(1/10)^k = 1 | n(9/10)^k=1 |
따라서 좌측 서브트리의 높이는 logn, 우측 서브트리의 높이는 log(10/9)n이 나옴.
따라서 logn <= T(n) <= log(10/9)n 이고 빅오의 정의에 의해 T(n)=O(log n)
힙 정렬
힙 정렬은 비선형 자료구조인 트리를 이용하여 정렬을 함. 힙이란 완전 이진트리를 뜻함. 부모노드가 가질수 있는 자식노드의 개수는 최대 2개이고, 데이터들은 왼쪽부터 차례대로 채워짐.
힙의 종류
Max heap : 부모노드는 자식노드보다 커야함. - 루트가 가장 큰 값
Min heap : 부모노드는 자식노드보다 커야함. - 루트가 가장 작은 값
(Max heap을 기준으로 설명.)
Max heap은 루트가 가장 큰 값이므로 영화 데이터를 Max Heap 구조로 만든 뒤 루트 값과 맨 마지막 값을 바꿔준 뒤 합 사이즈를 하나 감소시키고 뺀 루트 값을 배열의 맨 뒤에 넣음.
이러한 과정에서 max heap 구조가 깨지게 되므로 다시 힙 구조로 재구성 하는 과정이 필요함. 힙 정렬의 과정을 정리하면 다음으로 나타남.
1. 영화 데이터를 max heap으로 변경하기. (BUILD-MAX-HEAP)
2. 루트값을 뽑아 배열의 맨 뒤에 넣기.
3. 깨진 힙 구조 재구성. (MAX-HEAPIFY)
BUILD-MAX-HEAP
입력 데이터를 인덱스 순서대로 트리로 표현함. 완전 이진트리가 완성되면
max-heap을 만들어줘야 함. max heap을 만드는 과정은 Top-down 방식이 아 닌 bottom-up 방식으로 해야 함. 그림을 통해 설명함.
이러한 형태의 트리를 루트부터 max 힙 구조로 만들게 되면 루트부터 빨간 삼각형의 max 힙이 만족하는 지 보고 그 서브트리도 본다고 하면 매번 그 때마다 루트부터 계속 max heap을 만족하는지 확인해야 함. 즉 할 때마다 매번 log(n)번 확인.
반대로 bottom-up으로 하게 되면 아래쪽 서브트리가 만족하는지 보고 그다음 서브트리, 그다음 서브트리, ...이렇게 되면 여러번 반복할 필요가 없이 해당되는 서브트리에 대해서만 만족하는지만 보면 되므로 더 효과적으로 힙 구성 가능
또한 bottom-up으로 확인할 때 n개의 데이터가 있으면 n부터 시작할 필요가 없음. 왜냐하면 n개의 데이터가 트리로 구성되어 있을 때 맨 마지막 노드인 n의 부모노드는 n/2임.
따라서 가장 마지막 노드의 부모가 n/2위치에 있으므로 n/2보다 큰 위치에 있는 노드들은 heapfify를 할 필요가 없음. 결국 heapfify는 bottom-up 방식으로 n/2부터 진행하면 됨.
이렇게 루트의 년도 값이 가장 크므로 배열의 마지막에 넣어두고 맨 값인 1748을 루트로 올린 뒤 다시 heapify 구성. -루트의 값을 뺌으로써 힙 구조가 깨짐. 위 과정을 반복하여 힙의 사이즈가 1이 될 때 까지 반복. 타이틀도 동일 방식으로 진행.
힙 정렬은 max heap 구조를 만드는 과정에서 동일한 값이 나오면 값의 변경이 안 일어남. 동일 데이터의 순번이 구조체 안에 저장되어 있다면 그 값을 통해 비록 동일한 값 일지라도 순번으로 stable하게 구성 가능. (확인함.)
힙 정렬 – 성능 평가
힙 정렬은 우선 들어온 데이터를 힙 구조로 만들어야 함. 이 과정은 n개의 데이터가 있을 때 O(n)이 걸림. 그다음 루트값을 빼서 배열의 맨뒤에 저장하고, 맨 마지막 데이터를 루트에 올린뒤 다시 히피파이를 수행하여 힙 구조로 재구성해야 함.
이 과정은 트리의 높이만큼, 즉 log n 번 수행되고, 아까 히피파이는 n/2부터 bottom-up 으로 진행된다고 설명했으므로 대략 총 n/2번 수행됨. 따라서 힙 구조를 재구성하는데 걸리는 시간은 n/2 * log n = O(nlog n)임.
따라서 힙 정렬은 O(n) + O(n logn)= O(nlogn) 의 시간복잡도를 가짐.
기수 정렬
기수정렬이란 데이터의 자릿수 별로 구분하여 각 자리 수 끼리 정렬을 함. 다른 정렬들과는 다르게 비교연산을 하지 않음. 작은 자릿수에서 시작해서 가장 큰 자릿수까지 정렬해나가는 LSD 방식과, 반대의 방식인 MSD 방식이 존재.
년도 데이터는 4자리라는 고정크기이고 각 자리 수는 10의 자리로 고정됨. 따라서 0~9까지 데이터가 옴. 각 자릿수 정렬은 수업시간에 배운 counting sort 말고 큐리스트를 사용.
년도는 고정길이이고 정수이므로 구현하기 어려움이 없음. 하지만 영화 타이틀은 크기가 가변이고, 문자열이기 때문에 구현하기 까다로움.
년도는 정수 이므로 범위는 0~9 까지. 따라서 크기가 10인 배열을 만들고 각 배열은 큐 리스트로 구현함. % 연산자를 이용하여 각 자리수를 뽑고, 뽑은 자리수를 인덱스로 하여 선언한 배열 리스트에 해당 인덱스로 해서 집어넣음.
첫 인덱스부터 시작함. 4는 배열 리스트 큐의 인덱스 4에 대입됨. 9는 배열 리스트 큐의 인덱스 9에 삽입됨. 이렇게 8까지 완료가 리스트에 들어가게 되면 배열 큐의 인덱스 0부터 차례대로 dequeue 진행,
여기서 단순 년도 값만 enqueue 되는게 아니라 그 해당 년도를 포함하는 구조체 자체를 넣어줘야 함. 첫 번째 자리수가 정렬되면 1 2 4(1), 4(2) 8, 9 순으로 정렬됨. 큐는 먼저 들어간 놈이 먼저 나옴으로 같은 데이터에 대한 stability가 보장됨.
년도는 단순 정수이므로 쉽지만 문자열은 굉장히 까다로움. 타이틀에 영어 알파벳 뿐 만 아니라 특수기호까지 들어가 있으므로 아까 년도에서 정렬 범위를 0~9까지 한 것을 타이틀에서는 아스키 값 32 (공백)부터 126(~) 까지 세팅을 해야 함.
타이틀 정렬은 큐 리스트가 아닌 Counting sort로 구현. 아스키 값 32(공백)부터 126(~) 까지 표현해야 함으로 크기가 96인 배열 선언. 기수정렬은 같은 자릿 수 끼리 정렬함으로 문자열의 길이가 가장 긴 데이터를 찾아야 함.
찾은 가장 긴 문자열의 길이를 기준으로, 영화 타이틀의 길이와 비교해서 비교하는 타이틀의 길이가 더 작으면 0으로 세팅하고 인덱스 0 의 값을 하나 증가시킴. 이는 계수정렬의 루틴임. 모든 데이터에 대해서 최대 문자열 크기 기준으로 반복함.
Toy Story, Jumanji, Heat, Nixon 이러한 타이틀을 정렬한다고 하면, 여기서 가장긴 데이터는 Toy story==9 임. 9를 기준으로(인덱스 8) 첫 번째 자리를 비교함. 첫 번째 문자열이 가장 긴 데이터임으로 ‘y‘ 문자를 의 값을 32 ~ 126 크기의 배열에 집어 넣기 위해 –32를 하면 90이 나옴.
Counting 배열의 인덱스 90을 1 증가시킴. 위와 같이 밑에 타이틀도 진행하면 나머지는 최대길이 보다 작으므로 0으로 채우고 Counting 배열의 인덱스 0를 증가시키면 위 와 같은 결과가 나옴.
그다음 인덱스 값들을 누적하면 다음과 같음.
누적합의 의미.
≫ 0은 0번째에서 3번째 사이까지 위치 (0,1,2)
≫ 1,2,....89는 은 위치 x
≫ 90은 4번째에 위치(3)
≫ 나머진 위치 x
Stability를 유지하기 위해 역순으로 Nixon 문자열부터 누적합을 이용하여 위치를 찾아가는 결과를 나타냄. 이게 하나의 루틴임. 최대 문자열의 길이를 하나 줄여서 위의 과정을 또다시 반복. 그럼 다음 최대 문자열의 길이는 8이 되어 인덱스 7비교. 임시 배열에 저장할 때 역시 해당 타이틀을 포함하는 구조체 통째로 복사.
기수 정렬 – 성능 평가
기수정렬의 시간복잡도 = O(d(n+k))
d는 자릿수, n은 데이터 개수, k는 데이터 범위를 뜻함.
년도 정렬의 경우는 k가 10(0~9)으로 고정되어 있음.
타이틀 정렬은 k가 고정이지 않으므로 뒤 챕터인 성능분석을 년도와 비교하여 확인함.
3. 실제 성능 분석 및 평가
- 알고리즘 별 시간복잡도
2장에서 설명한 알고리즘 별 시간 복잡도를 정리한 표.
- 실제 측정 시간 (x축 : 데이터 개수 y축 : 걸린 시간)
삽입정렬
수행 결과 시간복잡도인 n^2 의 형태로 그래프가 나옴. 타이틀 정렬은 문 자열 비교이기 때문에 년도보다 쪼금 더 전체적으로 시간이 걸림.
합병정렬
삽입정렬에 비해 속도가 확 빨라짐으로 최대로 걸린시간이 0.1초 안됨. 시간복잡도인 nlogn 형태를 띔. 그리고 이 역시 타이틀 보단 년도가 더 빠름.
퀵 정렬
33000개의 데이터를 정렬하는데 0.05초도 안걸림. 합병 정렬과 아주 큰 차이는 없지만 전반적으로 합병 정렬보다 속도가 더 빠름. 퀵 정렬도 타이틀이 쫌더 걸릴 것으로 예상했으나 이건 년도가 약간 더 시간이 걸림. 하지만 그 차이는 굉장히 미미함. 이 역시 nlogn 모양으로 나옴.
힙 정렬
힙 정렬은 년도와 타이틀 둘다 거의 비슷한 속도로 측정 되었고, 최대 걸린 시간은 0.25초에 못미침. 이 역시 nlogn 형태를 띔.
기수 정렬
년도 정렬은 4로 고정된 길이의 정수를 사용하므로 속도가 매우 빠름. 하지만 타이틀 정렬은 가변길이의 문자를 사용하므로 속도가 년도에 비해 많이 차이남. 그리고 기수정렬은 고정길이의 정수를 비교할 때 좋지만, 버킷이라는 추가메모리가 필요함. 이 버킷을 생성하는데 시간이 걸림.
합병정렬, 퀵 정렬, 힙 정렬 3가지 비교 – (시간복잡도가 n*logn 인)
합병, 퀵, 힙 정렬 모두 시간복잡도가 nlogn을 가지지만, 측정 결과 퀵과 합병은 큰 차이는 없지만 퀵이 제일 빠르고 그다음 합병, 그리고 마지막으로 힙 정렬 순. 힙 정렬은 매번 루트에서 값을 뺄 때마다 heapify가 일어나게 되므로 이 과정에서 상당한 시간이 걸림.
삽입 정렬 제외 비교
타이틀 같은 경우 기수정렬에서 가장 많은 시간이 걸림. 이는 가변길이의 문자열 때문임. 년도 정렬은 힙 정렬이 가장 많은 시간이 걸림. 이는 heapifiy 시간이 다른 기수정렬이나 퀵, 합병보다 오래 걸리기 때문.
삽입 정렬 때문에 나머지 정렬의 시간차가 잘 안보여서 삽입정렬 제외하고 비교도 함.
4. 결론
종합 성능 분석
종합적으로 년도 정렬이든, 타이틀 정렬이든 가장 많은 시간이 걸리는 건 삽입 정렬이고, 가장 적은 시간이 걸리는 건 퀵 정렬임. 기수정렬은 타이틀 정렬이 삽입정렬을 제외한 다른 정렬에 비해 수행시간이 오래 걸림. 삽입 정렬을 제외한 나머지 정렬들은 33000개의 데이터 비교에서는 그래프에서 차이가 안남.(삽입 정렬 때매)
최종적으로 수행시간은 데이터의 종류에 따라 달라지지만, 가장 빠른 시간을 가지고 있는 알고리즘은 퀵정렬과 합병정렬임.(퀵이 쫌 더 빠름)
시간 측정 표
<타이틀 정렬 (초 단위)>
정렬
개수 | 삽입정렬 | 합병정렬 | 퀵정렬 | 힙 정렬 | 기수정렬 |
3000 | 0.06 | 0.011 | 0.004 | 0.016 | 0.111 |
6000 | 0.288 | 0.014 | 0.006 | 0.037 | 0.245 |
9000 | 0.639 | 0.019 | 0.01 | 0.057 | 0.546 |
12000 | 1.172 | 0.025 | 0.012 | 0.08 | 0.779 |
15000 | 2.195 | 0.026 | 0.017 | 0.106 | 1.011 |
18000 | 3.378 | 0.033 | 0.022 | 0.124 | 1.211 |
21000 | 6.109 | 0.036 | 0.026 | 0.15 | 1.439 |
24000 | 6.342 | 0.042 | 0.029 | 0.178 | 1.653 |
27000 | 6.823 | 0.046 | 0.035 | 0.189 | 1.766 |
30000 | 8.644 | 0.051 | 0.037 | 0.211 | 1.981 |
33000 | 11.1 | 0.064 | 0.041 | 0.231 | 2.199 |
<년도 정렬 (초 단위)>
정렬
개수 | 삽입정렬 | 합병정렬 | 퀵정렬 | 힙 정렬 | 기수정렬 |
3000 | 0.052 | 0.003 | 0.002 | 0.015 | 0.009 |
6000 | 0.239 | 0.007 | 0.006 | 0.036 | 0.023 |
9000 | 0.56 | 0.012 | 0.01 | 0.057 | 0.036 |
12000 | 1.012 | 0.017 | 0.014 | 0.076 | 0.048 |
15000 | 1.651 | 0.02 | 0.019 | 0.101 | 0.059 |
18000 | 2.474 | 0.025 | 0.023 | 0.124 | 0.071 |
21000 | 3.371 | 0.031 | 0.029 | 0.148 | 0.085 |
24000 | 5.015 | 0.037 | 0.036 | 0.173 | 0.096 |
27000 | 5.901 | 0.039 | 0.038 | 0.183 | 0.11 |
30000 | 8.386 | 0.04 | 0.046 | 0.21 | 0.116 |
33000 | 9.9 | 0.043 | 0.047 | 0.226 | 0.124 |
참고문헌
Introduction to algorithms — 교재
윤성우의 열혈 자료구조 — 도서
https://yaboong.github.io/algorithms/2018/03/20/counting-sort/
https://github.com/cave7/sort/blob/master/quicksort.c - 퀵 정렬 코드
https://www.quora.com/How-can-I-sort-strings-using-Radix-Sort - 문자열 기수정렬코드
http://ordo.tistory.com/m/88 - 힙 정렬 코드
https://www.youtube.com/watch?v=S42s_ANn4c4