2
\$\begingroup\$

Quick sort is a sorting algorithm in which we select any random element as pivot from the array and we do the partition of the array around that pivot. Basically we place all the elements smaller than pivot on its left side and the elements greater than it on its right side. So following is the code written by me that implements quick sort on an array of numbers:

public class Main{
    public static void main(String[] args){
        int[] arr = {11, 888, 65, 33, 73, 11, 22};
        int n = arr.length-1;
        quickSort(arr, 0, n);
        for(int i=0; i<=n; i++){
            System.out.print(arr[i] + " ");
        }
    }
    public static void quickSort(int[] arr, int si, int ei){
        if(si>=ei){
            return;
        }
        int j=si;
        int pi = ei;
        int pivot = arr[pi];
        while(si < ei){
            int temp;
            if(arr[si] <= pivot){
                temp = arr[si];
                arr[si] = arr[j];
                arr[j] = temp;
                j++;
            }
            else{
                temp = arr[pi];
               arr[pi] = arr[si];
               arr[si] = temp;
               pi--;
            }
            si++;
        }
        quickSort(arr, 0, pi-1);
        quickSort(arr, pi+1, ei);
    }
}

I tried this by running it with different sets of input and each time it gave the correct output. But I'm not sure if its good enough generally and also according to time and space complexity. Any feedback on this would be appreciated.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$
  • No naked loops

    Every loop implements an important algorithm, and deserves a name. In this case, the while loop implements partition. Factor it out into a method. Consider

      public static void quickSort(int[] arr, int si, int ei){
          if(si>=ei){
              return;
          }
          int pp = partition(arr, si, ei);
          quickSort(arr, si, pp - 1);
          quickSort(arr, pp + 1, ei);
      }
    

    Now you may unit test partition(). You may reuse it in other contexts. Etc.

  • You working too hard

    si is incremented at each iteration. j is incremented sometimes. Necessarily, j <= ai. In case arr[si] <= pivotit is guaranteed that arr[j] <= pivot as well. Why bother to swap?

  • You working extra hard

    As mentioned in the other answer, quickSort(arr, 0, pi - 1) better be quickSort(arr, original_si, pi - 1). Unfortunately your implementation lost the original si. It is yet another benefit of having a partition() method.

\$\endgroup\$
2
\$\begingroup\$

Advice 1 (API error)

The 3rd argument in your quickSort(arr, si, ei) (that is, ei) is the index of the rightmost element in the range to sort. The JDK follows another semantics: the 3rd argument to the sort routine must be the index of the one element after the last element in the range to sort. So, in order to sort, say, <1, 4, 3> in <2, 1, 4, 3, 0>, your call should be like:

quickSort(<2, 1, 4, 3, 0>, 1, 4) // Gives <2, 1, 3, 4, 0>.

Advice 2 (Performance bugs)

Bug 2.1 (Hackable pivot selection)

You keep using the rightmost element in the input (sub)range as the pivot. It's not hard to contruct an array on which the running time of your quicksort implementation will degrade to the \$\Theta(n^2)\$. (I will leave this for an exercise.)

Bug 2.2 (sorting left subrange)

In your quickSort(...), the first recursive call is:

               |
               |
               v
quickSort(arr, 0, pi-1);

So, you are sorting the prefixes of the input array all over again. You need:

quickSort(arr, si, pi - 1);

Unfortunately, that breaks your implementation so there are bugs to fix. (See the Advice 6.)

Advice 3 (Spacing)

int j=si;    // Wrong. Should be 'int j = si;'
int pi = ei; // OK

In Java, it is customary to add one space before and after a binary operator. Also,

if(si>=ei){
    ...
}

is "wrong". Should be:

if (si >= ei) {
    ...
}

(Above, note that there is a space before and after the condition parentheses.)

Finally, I suggest you have a single empty line before each if, for, while.


Advice 4 (Naming)

In JDK, the ìnt sorting method is called java.util.Arrays.sort(int[] a, int fromIndex, int toIndex). Perhaps you could create a package, say, com.strangealchemist.util and put an Arrays.java file in it, declaring your quicksort as sort(int[] a, int fromIndex, int toIndex).

Advice 5 (Readability)

if(si>=ei){
    return;
}

More readable way might be (that is only my opinion, though):

int rangeLength = toIndex - fromIndex;

if (rangeLength < 2) {
    return; // Trivially sorted.
}

Advice 6 (Randomizing pivot selection)

In order to guarantee an expected running time of \$\Theta(n \log n)\$, you could follow the following variant:

package com.strangealchemist.util;

import java.util.Random;

public class Arrays {

    private static final int SIZE = 1000;
    private static final int LIMIT = 100;

    public static void main(String[] args){
        int[] arr = {11, 888, 65, 33, 73, 11, 22};

        sort(arr); // Do the sorting.

        System.out.println(java.util.Arrays.toString(arr));

        int[] arr1 = getRandomArray();
        int[] arr2 = arr1.clone();
        int[] arr3 = arr1.clone();

        long startTime = System.currentTimeMillis();
        quickSort(arr2, 0, arr2.length - 1);
        long endTime = System.currentTimeMillis();

        System.out.println(
                "Alchemist's sort in " + (endTime - startTime) + " ms.");

        startTime = System.currentTimeMillis();
        sort(arr1);
        endTime = System.currentTimeMillis();

        System.out.println(
                "coderodde's sort in " + (endTime - startTime) + " ms.");

        startTime = System.currentTimeMillis();
        java.util.Arrays.sort(arr3);
        endTime = System.currentTimeMillis();

        System.out.println(
                "java.util.Arrays.sort in " + (endTime - startTime) + " ms.");

        System.out.println(
                "coderodde's quicksort agrees with java.util.Arrays.sort(): " 
                        + java.util.Arrays.equals(arr1, arr3));

        System.out.println(
                "Alchemist's quicksort agrees with java.util.Arrays.sort(): " 
                        + java.util.Arrays.equals(arr2, arr3));
    }

    public static void quickSort(int[] arr, int si, int ei){
        if(si>=ei){
            return;
        }
        int j=si;
        int pi = ei;
        int pivot = arr[pi];
        while(si < ei){
            int temp;
            if(arr[si] <= pivot){
                temp = arr[si];
                arr[si] = arr[j];
                arr[j] = temp;
                j++;
            }
            else{
                temp = arr[pi];
               arr[pi] = arr[si];
               arr[si] = temp;
               pi--;
            }
            si++;
        }
        quickSort(arr, 0, pi-1);
        quickSort(arr, pi+1, ei);
    }

    /**
     * Sorts the entire integer array into non-decreasing order. Runs in 
     * expected {@code O(n log n)}.
     * 
     * @param a the array to sort.
     */
    public static void sort(int[] a) {
        sort(a, 0, a.length);
    }

    /**
     * Sorts the range {@code a[fromIndex], ..., a[toIndex - 1]} into 
     * non-decreasing order. Runs in expected {@code O(n log n)}.
     * 
     * @param a         the array holding the range to sort.
     * @param fromIndex the index of the leftmost element in the range to sort.
     * @param toIndex   the index one past the rightmost element in the range to 
     *                  sort.
     */
    public static void sort(int[] a, int fromIndex, int toIndex) {
        // Note: the Random is created only once per sort.
        sort(a, fromIndex, toIndex, new Random());
    }

    // Implements actual sorting.
    private static void sort(int[] a,
                             int fromIndex, 
                             int toIndex, 
                             Random random){

        int rangeLength = toIndex - fromIndex;

        if (rangeLength < 2) {
            // Once here, the input is trivially sorted.
            return;
        }

        int pivotIndex = partition(a, fromIndex, toIndex, random);

        sort(a, fromIndex, pivotIndex, random);
        sort(a, pivotIndex + 1, toIndex, random);
    }

    // Partitions the input range around a random pivot and returns the index of
    // location in which the pivot ends up:
    private static int partition(int[] a,
                                 int fromIndex, 
                                 int toIndex,
                                 Random random) {

        int rangeLength = toIndex - fromIndex;
        int pivotIndex = fromIndex + random.nextInt(rangeLength);
        int pivot = a[pivotIndex];
        int i = fromIndex - 1;

        swap(a, pivotIndex, toIndex - 1);

        for (int j = fromIndex; j < toIndex - 1; j++) {
            if (a[j] < pivot) {
                swap(a, ++i, j);
            }
        }

        swap(a, ++i, toIndex - 1);
        return i;  
    }

    private static void swap(int[] a, int i1, int i2) {
        int temp = a[i1];
        a[i1] = a[i2];
        a[i2] = temp;
    }

    private static int[] getRandomArray() {
        return getRandomArray(SIZE, LIMIT);
    }

    private static int[] getRandomArray(int size, int limit) {
        return getRandomArray(size, limit, new Random());
    }

    private static int[] getRandomArray(int size, int limit, Random random) {
        int[] array = new int[size];

        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(limit);
        }

        return array;
    }
}

The above program gives:

[11, 11, 22, 33, 65, 73, 888]
Alchemist's sort in 684 ms.
coderodde's sort in 14 ms.
java.util.Arrays.sort in 1 ms.
coderodde's quicksort agrees with java.util.Arrays.sort(): true
Alchemist's quicksort agrees with java.util.Arrays.sort(): true

As you can see, your sort is really slow, yet seems to sort correctly.

Hope that helps.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Would enjoy reading your answer more if you Advice X headers were named to describe the content. \$\endgroup\$
    – K.H.
    Feb 5, 2023 at 23:45
  • \$\begingroup\$ @K.H. Fair enough. I will deal with it a little bit later. \$\endgroup\$
    – coderodde
    Feb 6, 2023 at 4:52
  • 1
    \$\begingroup\$ @K.H. Done. Thank you for your patience. \$\endgroup\$
    – coderodde
    Feb 6, 2023 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.