Thread: Custom quick sort

  1. #1
    Registered User
    Join Date
    Apr 2017
    Location
    Iran
    Posts
    115

    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 ?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,801
    > 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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Apr 2017
    Location
    Iran
    Posts
    115
    Quote Originally Posted by Salem View Post
    > 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));

  4. #4
    Registered User
    Join Date
    Apr 2017
    Location
    Iran
    Posts
    115
    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);   
    }

  5. #5
    Registered User
    Join Date
    Apr 2017
    Location
    Iran
    Posts
    115
    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);
    }

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,801
    The code is getting uglier, but is it getting any quicker?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Apr 2017
    Location
    Iran
    Posts
    115
    Quote Originally Posted by Salem View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sort linked list using quick sort in C
    By Babita Sandooja in forum C Programming
    Replies: 1
    Last Post: 03-04-2014, 09:24 AM
  2. Sort of vector of custom objects
    By Mycroft Holmes in forum C++ Programming
    Replies: 9
    Last Post: 02-24-2014, 09:54 PM
  3. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 06:48 PM
  4. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM

Tags for this Thread