Simple quicksort java implementation while maintaining partition element order

Question

TL;DR What is the simplest way to maintain left and right partition ordering?

SO...

I am working on this HackerRank challenge, but I am having trouble with their printing requirements as the challenge states...

Please maintain the original order of the elements in the left and right partitions while partitioning around a pivot element.

...I am trying to write the most simple / elegant solution I can (prefer to not create new arrays / lists, rotate multiple elements, etc.) and here's what I have...

import java.io.*;
import java.util.*;

public class Solution {
  public static void main(String[] args) {
    final int n;
    final int[] arr;
    
    try(final Scanner scanner = new Scanner(System.in)) {
        n = scanner.nextInt();
        arr = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
    }
    
    quickSort(arr, 0, n - 1);    
}

private static void quickSort(final int[] arr, final int start, final int end) {
    if(start >= end) return;
    
    final int partitionIndex = partition(arr, start, end);
    
    quickSort(arr, start, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, end);
    
    for(int i = start; i <= end; i++) {
        System.out.print(arr[i] + " ");
    }
    
    System.out.println();
}

private static int partition(final int[] arr, final int start, final int end) {
    final int pivot = arr[start];
    int pivotIndex = end + 1;
    
    for(int i = end; i > start; i--) {
        if(arr[i] > pivot) {
            pivotIndex--;
            final int temp = arr[pivotIndex];
            arr[pivotIndex] = arr[i];
            arr[i] = temp;
        }    
    }
    
    pivotIndex--;
    arr[start] = arr[pivotIndex];        
    arr[pivotIndex] = pivot;
    
    return pivotIndex;
  }
}

...and my submission fails because my first partition is not {1, 3, 2, 5, 8, 7, 9} but rather {3, 2, 1, 5, 8, 7, 9}, so upon subsequent partitions, my first merge is 1 2 instead of 2 3 because my algorithm did not keep the left partition's elements ordered (i.e. 1, 3, 2).

My algorithm iterates from the end to the start, excluding the start element (the pivot)...

{5, 8, 1, 3, 7, 9, 2} -> Pivot is 5, pivot index is 7 (out of bounds)

{5, 8, 1, 3, 7, 9, 2} -> 2 is not bigger than 5, skip

{5, 8, 1, 3, 7, 9, 2} -> 9 is bigger than 5, pivot index is 6, swap 9 and 2

{5, 8, 1, 3, 7, 2, 9} -> 7 is bigger than 5, pivot index is 5, swap 7 and 2

{5, 8, 1, 3, 2, 7, 9} -> 3 is not bigger than 5, skip

{5, 8, 1, 3, 2, 7, 9} -> 1 is not bigger than 5, skip

{5, 8, 1, 3, 2, 7, 9} -> 8 is bigger than 5, pivot index is 4, swap 8 and 2

{5, 2, 1, 3, 8, 7, 9} -> pivot index is 3, swap 5 and 3

{3, 2, 1, 5, 8, 7, 9} -> final result after first partition

...I maintained the order for the right partition (i.e. 8 7 9) but not the left...

Lane Lane · Accepted Answer · 2021-02-02T04:01:30

TL;DR from Wikipedia

Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved.

SO...

Unfortunately I had to make a concession in order to make my Quicksort implementation stable; in case anyone is interested, here's what I decided to do (opting for simplicity over performance)...

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        final int n;
        final int[] arr;

        try(final Scanner scanner = new Scanner(System.in)) {
            n = scanner.nextInt();
            arr = new int[n];

            for(int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
            }
        }

        quickSort(arr, 0, n - 1);
    }

    private static void quickSort(final int[] arr, final int start, final int end) {
        if(start >= end) return;

        final int partitionIndex = partition(arr, start, end);

        quickSort(arr, start, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, end);

        for(int i = start; i <= end; i++) {
            System.out.print(arr[i] + " ");
        }

        System.out.println();
    }

    private static int partition(final int[] arr, final int start, final int end) {
        final int pivot = arr[start];
        int pivotIndex = start;

        for(int i = start + 1; i <= end; i++) {
            if(arr[i] < pivot) {
                pivotIndex++;
            }
        }

        int smallerIndex = start;
        int biggerIndex = pivotIndex + 1;
        final int[] copy = Arrays.copyOf(arr, arr.length);

        for(int i = start + 1; i <= end; i++) {
            if(copy[i] < pivot) {
                arr[smallerIndex++] = copy[i];
            } else if(arr[i] > pivot) {
                arr[biggerIndex++] = copy[i];
            }
        }

        arr[pivotIndex] = pivot;

        return pivotIndex;
    }
}

Simple quicksort java implementation while maintaining partition element order

1 Answers