DEV Community

Satoru Takeuchi
Satoru Takeuchi

Posted on

1

Should we always use quicksort than insertion sort?

It's often said that "Use always O(n*log(n)) algorhithms". However, depending on the situation, it might not always be right. In this article, I will compare quicksort and insertion sort.

When written in Big O notation, the computational complexity of quicksort is O(n*log(n)), while that of insertion sort is O(n^2). So, it seems like the former would be faster at a glance. However, this notation only describes the behavior when n approaches infinity, so in real-world programs, quicksort is not always faster.

Let's compare the speeds of both algorithms in a program with the following specifications:

  • Sort an array with a given number of integer elements and output the time it takes to do so.
  • First argument (len): Number of elements.
  • Second argument (type): Type of algorithm. 'i' for insertion sort, 'q' for quicksort.

The following sort program implements these specifications.

#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;
        }
    }
}

int pivot(int a[], int l, int r){
    int i = l, j = r-1;
    int p = a[r];
    int tmp;
    for (;;) {
        while (a[i] < p)
            i++;
        while (i < j && p < a[j])
            j--;
        if (i >= j)
            break;
        tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;

    return i;
}

void quick_sort_inner(int *a, int l, int r){
    if (l >= r)
        return;
    int v = pivot(a, l, r);
    quick_sort_inner(a, l, v-1);
    quick_sort_inner(a, v+1, r);
}

static void quick_sort(int *a, int len)
{
    quick_sort_inner(a, 0, len-1);
}

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);
}

Enter fullscreen mode Exit fullscreen mode

Let's build this progam.

$ CFLAGS=-O3 make sort
$ 
Enter fullscreen mode Exit fullscreen mode

I ran this program with the following parameters.

Parameter Value
First argument (len) 2^(0, 1, 2, ..., 15)
Second argument (type) "i", "q"

I plotted the results on the following graph. Note that the x-axis is 2^(len) and the y-axis is log(elapsed time).

Image description

As len gets larger, quicksort indeed becomes faster, and the difference only grows. However, when len is small, it can be seen that insertion sort is faster up to around 2^8 (=128). This is because quicksort performs more complex processing compared to insertion sort. Therefore, using quicksort is generally not a bad choice, but if you want to fine-tune your program and know that len will not be that large, trying to speed up using insertion sort is one option. However, as the saying goes, "premature optimization", there is no need to start with this kind of fine-tuning.

One last point. For the reasons mentioned above, the qsort() function in glibc, internally uses insertion sort for a somewhat small len (<=MAX_THRESH). There are many other implementations that work this way. If you're interested, it's a good idea to take a look at various quicksort implementations.

Image of AssemblyAI

Automatic Speech Recognition with AssemblyAI

Experience near-human accuracy, low-latency performance, and advanced Speech AI capabilities with AssemblyAI's Speech-to-Text API. Sign up today and get $50 in API credit. No credit card required.

Try the API

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay