Home > Blockchain >  QuickSort with only two arguments
QuickSort with only two arguments

Time:10-30

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.

  • Related