정렬 알고리즘 속도 비교(버블 정렬, 단순 삽입 정렬, 퀵 정렬)/C,C++

안녕하세요 

 

이번 글에는 정렬 알고리즘들의 정렬 속도 차이를 비교해볼까 합니다.

 

 

비교할 정렬 알고리즘은

 

1. 버블 정렬 (bubble sort)

2. 단순 삽입 정렬(straight insertion sort)

3. 퀵 정렬(quick sort)

 

입니다.

 

정렬 알고리즘 구현 코드는 글 하단에 있습니다 :)

 

 

- 기본 지식

 

버블 정렬과 단순 삽입 정렬의 시간 복잡도는 O(n^2),

 

퀵 정렬의 시간 복잡도는 O(n logn)입니다.

 

 

 

정렬 알고리즘들의 실제 정렬 속도 차이를 알기 위해 

 

라이브러리 <time.h>의 함수인 clock()을 이용해 정렬 전 시간과, 정렬 후 시간을 비교할 것입니다.

 

또한 무작위 숫자가 저장된 배열을 만들기 위해 라이브러리 <stdlib.h>의 rand() 함수도 사용할 것입니다.

 

 

또한 정렬할 원소 수가 적을 경우와 많을 경우도 비교해 보겠습니다.

 

 

- 사전 준비

 

1. 헤더 파일 선언

2. 매크로 상수 선언

4. 정렬용 함수 원형 선언

4. swap macro

5. std 클래스 사용

 

 

-링크 swap macro??

besforyou.tistory.com/5?category=875444

 

 

 

1. 정렬할 수가 적은 경우 ( 1000인 경우 )

 

 

1)

배열의 길이가 ARR_LEN_1인 정수형 배열을 2개 준비합니다.

배열 1개는 원본 배열로 이용할 것이고, 나머지 1개는 정렬에 쓰도록 하겠습니다.

 

2)

'정렬 전 시간'과 '정렬 후 시간'을 저장할 변수 clock_t PrevTime , CurTime 도 선언합니다.

 

3)

배열에 저장되는 숫자를 완전한 무작위로 만들기 위해 

srand() 함수에 프로그램 실행 때마다 달라지는 시드 값을 줍니다. 숫자 범위는 (0~9999)

- 링크 : srand?? rand??

 

4)

cout을 그냥 쓰게 되면 전체 자리 수가 6개로 고정되어 소수점이 제대로 표현 안 되는 경우가 생기게 되므로 소수점 5자리까지 출력되게 하겠습니다.

 

cout << fixed;

cout.precision(5); 

 

 

 

원본 배열에 숫자들을 무작위로 저장한 후 정렬용 배열에 원본 배열 내용을 복사합니다.

 

 

 

 

첫 번째 정렬 알고리즘은 버블 정렬입니다.

 

 

정렬 전, clock() 함수를 이용해 정렬 전 시간을 저장한 후

 

버블 정렬로 배열을 정렬하고

 

정렬 후, clock() 함수를 이용해 정렬 후 시간을 저장 한 뒤

 

cout을 이용해 걸린 시간을 출력합니다.

 

CurTime - PrevTime을 (double)로 casting 한 뒤 CLOCKS_PER_SEC으로 나누어주면 걸린 시간을 초단위로 알 수 있게 됩니다.

 

 

정렬이 완료된 뒤에는 원본 배열의 내용을 다시 정렬용 배열에 복사합니다.

 

 

 

 

 

두 번째 정렬 알고리즘인 단순 선택 정렬 또한 똑같은 작업을 해주고

 

 

 

 

 

세 번째 정렬 알고리즘인 퀵 정렬에도 같은 일을 해준 뒤

 

 

 

프로그램을 실행시켜보면 

 

 

 

0.001초 단위로 차이가 나는 것을 볼 수 있습니다.

 

인간이 인지하기도 힘든 차이죠 허허

 

 

 

 

2. 정렬할 수가 많은 경우( 길이 10000 )

 

이제 길이가 10000인(1만) 배열로 같은 작업을 해보겠습니다.

 

 

길이를 10000으로 바꾸고 돌려보니

 

 

 

차이가 조금씩 나기 시작하네요

하지만 크게 체감은 나지 않는 수준입니다.

 

 

 

3. 더 많은 경우 ( 10만 )

 

이번에는 길이를 10만 인 배열로 해보겠습니다.

 

 

매크로 상수를 수정하고 프로그램을 돌려보니

 

 

.....

 

 

.....

 

 

 

????

 

 

아 나온다

 

 

 

 

컴퓨터 어떻게 된 줄 알았습니다.

 

시간 차이가 정말 많이 벌어졌습니다.

 

 

 

정렬할 숫자 단위가 10만이 되니 차이가 현격하게 벌어지기 시작합니다.

 

100만으로 해보려다가 너무 오래 걸릴듯하여 참았습니다

 

 

 

- 결 론

버블 정렬은 거르자

 

배열 길이가 천 단위 이하면 구조가 단순한 정렬 알고리즘을 사용하여도 무방하다.

 

배열 길이가 만단 위 이상이거나, 정렬을 여러 번 해야 하는 경우에는 무조건 빠른 정렬 알고리즘을 쓰자

 

 

 

 

 

- 정렬 함수 코드

 

0. swap macro

 

#define swap(type, x , y ) do{ type t; t = x; x = y; y = t; }while(0);

 

 

 

1. 버블 정렬(Bubble sort)

 

 
void bubble_sort(int a[], int n) {
 
    int i,j;
 
    for( i=0 ; i < n-1 ; i++) {
        for(j = n - 1 ; j > i ; j--) {
            if(a[j] < a[j-1]){
                swap(int , a[j] , a[j-1]);
            }
        }
    }
}

 

 

 

2. 단순 삽입 정렬 (Straight Insertion Sort)

 

void straight_selection_sort(int a[], int n) {
 
    int i,j;
 
    for(i=1; i < n; i++) {
        int temp = a[i];
        for (j = i; j > 0 && a[j - 1] > temp; j--) {
            a[j] = a[j - 1];
        }
        a[j] = temp;
    }
}

 

 

 

3. 퀵 정렬 (Quick sort)

 

void quick_sort(int a[], int left, int right) {
 
    int pl = left;
    int pr = right;
    int x = a[(pl+pr)/2];
 
    do {
        while(a[pl] < x) pl++;
        while(a[pr] > x) pr--;
 
        if(pl<=pr){
            swap(int,a[pl],a[pr]);
            pl++;
            pr--;
        }
 
    }while(pl<=pr);
 
    if(left < pr) quick_sort(a,left,pr);
    if(pl < right) quick_sort(a,pl,right);
}