Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is this a correct implementation of quicksort? [closed]

Tags:

java

quicksort

I would like to check if this is a correct implementation of QuickSort, It seems to be doing the job, but Am I missing out anything?

public class QuickSort implements Sorter {

public void sort(Comparable[] items) {
    QuickSort(items, 0, items.length - 1);
}

static void QuickSort(Comparable[] items, int a, int b) {
    int lo = a;
    int hi = b;
    if (lo >= hi) {
        return;
    }
    Comparable mid = items[(lo + hi) / 2];
    Comparable T;

    while (lo < hi) {
        while (items[lo].compareTo(mid)<0) {
            lo++;
        }
        while (mid.compareTo(items[hi])<0) {
            hi--;
        }
        if (lo < hi) {
            T = items[lo];
            items[lo] = items[hi];
            items[hi] = T;
        }
    }

    QuickSort(items, a, lo);
    QuickSort(items, lo == a ? lo + 1 : lo, b);

}

}

fixed:

private static void quickSort(Comparable[] items, int a, int b) {
    int i = a;
    int j = b;

    Comparable x = items[(a+ b) / 2];
    Comparable h;

    do {
        while (items[i].compareTo(x) < 0) {
            i++;
        }
        while (items[j].compareTo(x) > 0) {
            j--;
        }
        if (i <= j) {
            h = items[i];
            items[i] = items[j];
            items[j] = h;
            i++;
            j--;
        }
    } while (i <= j);

    if (a < j) {
        quickSort(items, a, j);
    }
    if (i < b) {
        quickSort(items, i, b);
    }
}
like image 789
Roch Avatar asked Mar 27 '09 18:03

Roch


People also ask

Which of the following is the correct implementation of the Quicksort algorithm?

1. Quick sort uses which of the following algorithm to implement sorting? Explanation: Quick sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two parts about the pivot and then apply a quick sort to both the parts.

How Quicksort is implemented?

In quick sort, a large array is divided into two arrays in which one holds values that are smaller than the specified value (Pivot), and another array holds the values that are greater than the pivot. After that, left and right sub-arrays are also partitioned using the same approach.

Can Quicksort be implemented iteratively?

You can implement an iterative version of Quicksort with a queue rather than a stack.

Why is Quicksort not inplace?

If you define "in-place" as requiring a constant amount of memory, then quicksort is not "in-place" as it requires log(N) memory for the recursion. If you define "in-place" as more human-friendly "does not move the data outside the input structure", then quicksort is again not "in-place".


1 Answers

1 small point- there's a potential int overflow here:

(lo + hi) / 2

like image 89
RossFabricant Avatar answered Nov 11 '22 10:11

RossFabricant