정렬 계산량과 실제 프로그램

정렬 알고리즘에 관한 작은 단락.'서열을 서슴없이 빠르게 정렬한다'[1]는 말이 종종 나오지만, 상황에 따라 부적절한 경우도 있다.빠른 정렬과 삽입 정렬을 비교합니다.
O기법로 쓰면 빠른 정렬의 계산량은 O(n*log(n)), 단순한 삽입 정렬은 O(n^2)로 전자가 빨라 보인다.그러나 도대체 이 기법은 n이 무한시에 가까운 동작을 서술하는 것일 뿐 현실적인 프로그램이 반드시 빠른 순서가 빠른 것은 아니다.
다음 방법의 절차로 양자의 속도를 실제로 비교해 보자.

규정된 정수 요소의 배열을 정렬하고 해당 소요시간을 출력

첫 번째 매개 변수(len): 원소수

두 번째 매개 변수: 알고리즘의 유형삽입 정렬"q'빠른 정렬.

이 규격을 실현한 것은 다음과 같은sort 프로그램이다.

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

#define NSECS_PER_MSEC 1000000UL
#define NSECS_PER_SEC 1000000000UL

static void insertion_sort(int *a, int len)
{
        int i, tmp;
        for (i = 1; i < len; i++) {
                tmp = a[i];
                if (a[i - 1] > tmp) {
                        int j;
                        j = i;
                        do {
                                a[j] = a[j - 1];
                                j--;
                        } while (j > 0 && a[j - 1] > tmp);
                        a[j] = tmp;
                }
        }
}

static inline long diff_nsec(struct timespec before, struct timespec after)
{
        return ((after.tv_sec * NSECS_PER_SEC + after.tv_nsec)
                - (before.tv_sec * NSECS_PER_SEC + before.tv_nsec));

}

static void prepare_data(int *a, int len)
{
        int i;
        for (i = 0; i < len; i++)
                a[i] = rand();
}

static int comp(const void *a, const void *b)
{
        return *((int *)a) - *((int *)b);
}

static char *progname;

int main(int argc, char *argv[])
{
        progname = argv[0];

        if (argc < 3) {
                fprintf(stderr, "usage: %s <len> <i|q>\n", progname);
                exit(EXIT_FAILURE);
        }

        int len = atoi(argv[1]);

        char type = argv[2][0];

        if (!((type == 'i') || (type == 'q'))) {
                fprintf(stderr, "%s: type should be 'i or q'\n", progname);
                exit(EXIT_FAILURE);
        }

        int *a;
        a = malloc(len * sizeof(int));
        prepare_data(a, len);

        struct timespec before, after;
        if (type == 'i') {
                clock_gettime(CLOCK_MONOTONIC, &before);
                insertion_sort(a, len);
                clock_gettime(CLOCK_MONOTONIC, &after);
        } else {
                clock_gettime(CLOCK_MONOTONIC, &before);
                qsort(a, len, sizeof(int), comp);
                clock_gettime(CLOCK_MONOTONIC, &after);
        }

        printf("%lu\n", diff_nsec(before, after));

        exit(EXIT_SUCCESS);
}

구축 방법은 다음과 같다.

$ CFLAGS=-O3 make sort
$ 

다음 매개 변수를 사용하여 이 프로그램을 실행했습니다.
매개 변수
값
첫 번째 매개변수(len)
2^(0, 1, 2, ..., 15)
보조 매개변수(type)
i, q
결과는 다음 도표에 그려집니다.x축은 2^(len), y축은 log(소요 시간)를 주의하십시오.
[f:id:satoru_takeuchi:20200329053129p:plain]
렌이 커지면서 빠른 정렬이 확실히 빨라지고 격차도 점점 커진다.하지만 렌이 어렸을 때는 여기서 2^8(=128)까지 삽입 정렬이 빨랐다.삽입 정렬보다 빠른 정렬이 더 복잡하기 때문이다.따라서 보통 빠른 정렬을 사용하면 나쁘지 않지만, 프로그램을 바삭바삭하게 조정하고 렌이 커지지 않는다는 것을 알았을 때 삽입 정렬을 사용하여 고속화에 도전하는 것도 방법이다.하지만'조기 최적화'라는 말처럼 처음부터 이런 세밀한 조정은 필요 없겠죠.
마지막.이 보도가 제작된 프로그램에서도 사용된 globc의 qsort() 함수는 어느 정도 작은 렌 (<=MAX THRESH) 의 경우 내부에 삽입 정렬을 사용합니다라는 이유도 있다.이 외에도 이런 실복은 많다.관심 있는 사람들은 각종 빠른 순서의 실시 방안을 볼 수 있다.
각주
특히 스크립트 언어의 경우 정렬 알고리즘을 스스로 선택하는 경우도 적을 수 있다↩︎