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:
- Does the modification make any difference ?
- If so is that modification more efficient ?