Thread: Custom quick sort

Hi,

I found a quick sort implementation in this link mentioned below. I modified it into a custom version.

Code:

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


// https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#C


void quicksort(int *A, int len)
{
    if(len < 2)
        return;


    int pivot = A[len / 2];


    int i, j;
    for(i = 0, j = len - 1;; i++, j--)
    {
        while(A[i] < pivot)
            i++;
        while(A[j] > pivot)
            j--;


        if(i >= j)
            break;


        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }


    quicksort(A, i);
    quicksort(A + i, len - i);
}
/////////////////////////////
// A custom quicksort:


// min max
int min(int a, int b)
{
    return a < b ? a : b;
}
int max(int a, int b)
{
    return a > b ? a : b;
}
// median of 3
int median3(int a, int b, int c)
{
    intmax_t tot_v = a + b + c;
    int max_v = max(a, max(b, c));
    int min_v = min(a, min(b, c));
    return tot_v - max_v - min_v;
}


#define MIN_LEN 10


void quicksort2(int *A, int len)
{
    if(len < 2)
        return;


    int pivot;
    if(len < MIN_LEN)
        pivot = A[len / 2];
    else
        pivot = median3(A[0], A[len / 2], A[len - 1]);


    int i, j;
    for(i = 0, j = len - 1;; i++, j--)
    {
        while(A[i] < pivot)
            i++;
        while(A[j] > pivot)
            j--;


        if(i >= j)
            break;


        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }


    quicksort2(A, i);
    quicksort2(A + i, len - i);
}


/////////////////////////////
#define ARR_LEN 1000 // 10000000


// https://benpfaff.org/writings/clc/shuffle.html


void shuffle(int *array, size_t n)
{
    if(n > 1)
    {
        size_t i;
        for(i = 0; i < n - 1; i++)
        {
            size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
            int t = array[j];
            array[j] = array[i];
            array[i] = t;
        }
    }
}


bool sorted(int *arr, int n)
{
    int i;
    for(i = 0; i < n - 1; i++)
    {


        if(arr[i] > arr[i + 1])
            return false;
    }


    return true;
}


int main(void)
{
    int *arr = malloc(ARR_LEN * sizeof(int));
    int i;
    //srand(time(NULL));


    for(i = 0; i < ARR_LEN; i++)
        arr[i] = i; //-i; 1;
    shuffle(arr, ARR_LEN);


    // quicksort(arr, ARR_LEN);
    quicksort2(arr, ARR_LEN); 


    bool is = sorted(arr, ARR_LEN);
    if(is == false)
        return EXIT_FAILURE;


    free(arr);
    printf("Finished.\n");
    return 0;
}

These are some questions:

1. Does the modification make any difference ?
2. If so is that modification more efficient ?

Originally Posted by Salem

> Does the modification make any difference ?
Why haven't you tested it?

> If so is that modification more efficient ?
Why haven't you tested it?

I already tested. Results are close and I am afraid of slightly different
results on each run. I am on a laptop also.

Here are some test cases
- the numbers are already sorted
- the numbers are already reverse sorted
- the numbers are all the same

Try pathological sequences like this which put outliers at all the points you sample the median.
1, 2, 3, 4, 1, 5, 6, 7, 1

Do that for a range of array sizes from say 10 to 1E7 (or whatever power of 10 your machine starts taking many minutes to do one test).

I did a variety of tests here is one result from a shuffled array (ARR_LEN is 1e8) :
quicksort : 26.77 sec from 50.52 sec
quicksort2 : 26.04 sec from 49.81 sec

FWIW, your median calculation risks integer overflow.
Can you fix it?

I get it from here :

Code:

median = max(min(a,b), min(max(a,b),c));

Here is my current effort:

Code:

#define MIN_LEN 10


void quicksort2(int *A, int len) 
{ 
    if (len < 2) return;
 
    if(len==2) // Added 
    {
        if(A[0]>A[1])
            swap(&A[0],&A[1]);
        return;
    }
 
    int pivot;
    if(len<MIN_LEN)
        pivot = A[len / 2];
    else 
        pivot=median3(A[0],A[len/2],A[len-1]); 
 
    int i, j;
    for (i = 0, j = len - 1; ; i++, j--) 
    {
       while (A[i] < pivot) i++;
       while (A[j] > pivot) j--;
 
       if (i >= j) 
           break;
 
       int temp = A[i];
       A[i]     = A[j];
       A[j]     = temp;   
    }
 
    quicksort2(A, i);
    quicksort2(A + i, len - i);   
}

I borrowed some code from quadsort. Now here is a new version of custom quicksort:

Code:

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


void swap2(int* first, int* second)
{
    int temp = *first;
    *first = *second;
    *second = temp;
}


// min max
int min(int a,int b)
{
    return a < b ? a : b;
}
int max(int a,int b)
{
    return a > b ? a : b;
}
// median of 3
int median3(int a, int b, int c)
{  
    int median = max(min(a,b), min(max(a,b),c));
    return median;
}




/////////////////////////
typedef int CMPFUNC (const void *a, const void *b);
int cmp(const void* a, const void* b)
{
    int arg1 = *(const int*)a;
    int arg2 = *(const int*)b;
 
    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}


//#define cmp(a,b) (*(a) > *(b))
#define parity_merge_two(array, swap, x, y, ptl, ptr, pts, cmp)  \
{  \
    ptl = array + 0; ptr = array + 2; pts = swap + 0;  \
    x = cmp(ptl, ptr) <= 0; y = !x; pts[x] = *ptr; ptr += y; pts[y] = *ptl; ptl += x; pts++;  \
    *pts = cmp(ptl, ptr) <= 0 ? *ptl : *ptr;  \
  \
    ptl = array + 1; ptr = array + 3; pts = swap + 3;  \
    x = cmp(ptl, ptr) <= 0; y = !x; pts--; pts[x] = *ptr; ptr -= x; pts[y] = *ptl; ptl -= y;  \
    *pts = cmp(ptl, ptr)  > 0 ? *ptl : *ptr;  \
}


#define parity_merge_four(array, swap, x, y, ptl, ptr, pts, cmp)  \
{  \
    ptl = array + 0; ptr = array + 4; pts = swap;  \
    x = cmp(ptl, ptr) <= 0; y = !x; pts[x] = *ptr; ptr += y; pts[y] = *ptl; ptl += x; pts++;  \
    x = cmp(ptl, ptr) <= 0; y = !x; pts[x] = *ptr; ptr += y; pts[y] = *ptl; ptl += x; pts++;  \
    x = cmp(ptl, ptr) <= 0; y = !x; pts[x] = *ptr; ptr += y; pts[y] = *ptl; ptl += x; pts++;  \
    *pts = cmp(ptl, ptr) <= 0 ? *ptl : *ptr;  \
  \
    ptl = array + 3; ptr = array + 7; pts = swap + 7;  \
    x = cmp(ptl, ptr) <= 0; y = !x; pts--; pts[x] = *ptr; ptr -= x; pts[y] = *ptl; ptl -= y;  \
    x = cmp(ptl, ptr) <= 0; y = !x; pts--; pts[x] = *ptr; ptr -= x; pts[y] = *ptl; ptl -= y;  \
    x = cmp(ptl, ptr) <= 0; y = !x; pts--; pts[x] = *ptr; ptr -= x; pts[y] = *ptl; ptl -= y;  \
    *pts = cmp(ptl, ptr)  > 0 ? *ptl : *ptr;  \
}




void parity_swap_four32(int *array, CMPFUNC *cmp)
{
    int swap[4], *ptl, *ptr, *pts;
    unsigned char x, y;
    


    x = cmp(array + 0, array + 1) <= 0; y = !x; swap[0 + y] = array[0]; swap[0 + x] = array[1];
    x = cmp(array + 2, array + 3) <= 0; y = !x; swap[2 + y] = array[2]; swap[2 + x] = array[3];


    parity_merge_two(swap, array, x, y, ptl, ptr, pts, cmp);


}


void parity_swap_eight32(int *array, CMPFUNC *cmp)
{
    int swap[8], *ptl, *ptr, *pts;
    unsigned char x, y;


    if (cmp(array + 0, array + 1) > 0) { swap[0] = array[0]; array[0] = array[1]; array[1] = swap[0]; }
    if (cmp(array + 2, array + 3) > 0) { swap[0] = array[2]; array[2] = array[3]; array[3] = swap[0]; }
    if (cmp(array + 4, array + 5) > 0) { swap[0] = array[4]; array[4] = array[5]; array[5] = swap[0]; }
    if (cmp(array + 6, array + 7) > 0) { swap[0] = array[6]; array[6] = array[7]; array[7] = swap[0]; } else


    if (cmp(array + 1, array + 2) <= 0 && cmp(array + 3, array + 4) <= 0 && cmp(array + 5, array + 6) <= 0)
    {
        return;
    }
    parity_merge_two(array + 0, swap + 0, x, y, ptl, ptr, pts, cmp);
    parity_merge_two(array + 4, swap + 4, x, y, ptl, ptr, pts, cmp);


    parity_merge_four(swap, array, x, y, ptl, ptr, pts, cmp);
}




void unguarded_insert32(int *array, size_t offset, size_t nmemb, CMPFUNC *cmp)
{
    int key, *pta, *end;
    size_t i, top;


    for (i = offset ; i < nmemb ; i++)
    {
        pta = end = array + i;


        if (cmp(--pta, end) <= 0)
        {
            continue;
        }


        key = *end;


        if (cmp(array, &key) > 0)
        {
            top = i;


            do
            {
                *end-- = *pta--;
            }
            while (--top);


            *end = key;
        }
        else
        {
            do
            {
                *end-- = *pta--;
            }
            while (cmp(pta, &key) > 0);


            *end = key;
        }
    }
}


#define MAG_LEN 10


void quicksort2(int *A, int len) { 
  if (len < 2) return;
 
    if(len==2)
    {
        if(A[0]>A[1])
            swap2(&A[0],&A[1]);
        return;
    }
    else if(len==3)
    {
        unguarded_insert32(A, 1, len, cmp);    
        return;
    }
    else if(len<8 )
    {
        parity_swap_four32(A,cmp);
        unguarded_insert32(A,4,len,cmp);
        return;
    }
    else if(len<16 )
    {
        parity_swap_eight32(A,cmp);
        unguarded_insert32(A,4,len,cmp);
        return;
    }
 
    int pivot;
    if(len<MAG_LEN)
         pivot = A[len / 2];
    else 
         pivot=median3(A[0],A[len/2],A[len-1]); 
 
  int i, j;
  for (i = 0, j = len - 1; ; i++, j--) {
    while (A[i] < pivot) i++;
    while (A[j] > pivot) j--;
 
    if (i >= j) break;
 
    int temp = A[i];
    A[i]     = A[j];
    A[j]     = temp;
    
    }
    quicksort2(A, i);
    quicksort2(A + i, len - i);
}

Originally Posted by Salem

The code is getting uglier, but is it getting any quicker?

On this laptop without optimization flags for compiler , for last code I get total 47.25 sec comparing to total 50.52 sec for original quicksort ​in post #1.