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 ?

> 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?

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).

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

Quote:

---

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.

Quote:

---

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

Quote:

---

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

---

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

Quote:

---

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.