How do you construct an algorithm for Quicksort with an array and the length of the array as two arguments?
that is:
void quick_sort(int A[], int n)
like this.
However, I am only familiar with writing Quicksort with 3 arguments, an array, and the lowest index and the highest index.
the Quicksort
function below takes 3 arguments, arr
, l
, and h
.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int l, int h) {
int pivot = arr[l];
int i = l;
int j = h;
while (i < j) {
while (arr[i] <= pivot) {
i ;
}
while (arr[j] > pivot) {
j--;
}
if (i < j) {
swap(&arr[j], &arr[i]);
}
}
swap(&arr[l], &arr[j]);
return j;
}
void quickSort(int arr[], int l, int h) {
if (l < h) {
int j = partition(arr, l, h);
quickSort(arr, l, j - 1);
quickSort(arr, j 1, h);
}
}
However, I need to write a QuickSort implementation with only two arguments.
How do you write the function that does the same sorting?
That is, we have only the length of n
, while the complete quicksort algorithm above has l
and h
as arguments.
CodePudding user response:
A lot of code presents a nice interface to the actual work functions. For example, a Quicksort algorithm may present itself as:
void quickSort( int * xs, int n );
But be implemented as:
static int partition( int * xs, int left, int right )
{
...
}
static void quickSort_( int * xs, int left, int right )
{
...
}
void quickSort( int * xs, int n )
{
quickSort_( xs, 0, n );
}
Notice how the actual workhorse functions are static
to the library where the user cannot see them.