3
\$\begingroup\$

I've implemented a solution to generate the worst-case scenario for QuickSort using the middle pivot strategy in Java. The goal is to rearrange an input array to produce the worst performance during sorting.

Here's the code I've written:

public class WorstCaseForMiddlePivotQuickSort<E extends Comparable<? super E>> {
    private static <E extends Comparable<? super E>> int partition(List<E> arr, int low, int high) {
        int middlePivotIndex = (low + high) / 2;
        E pivot = arr.get(middlePivotIndex);
        
        int i = low;
        int j = high;
        
        while (i <= j) {
            while (arr.get(i).compareTo(pivot) < 0) {
                i++;
            }
            while (arr.get(j).compareTo(pivot) > 0) {
                j--;
            }
            
            if (i <= j) {
                Collections.swap(arr, i, j);
                i++;
                j--;
            }
        }
        
        return i;
    }
    
    
    private static <E extends Comparable<? super E>> void quickSortUsingMiddlePivot(List<E> arr, int low, int high, List<Integer> partitionIndexHistory) {
        if (low >= high) {
            return;
        }
        int partitionIndex = partition(arr, low, high);
        partitionIndexHistory.add(partitionIndex);
        quickSortUsingMiddlePivot(arr, low, partitionIndex - 1, partitionIndexHistory);
        quickSortUsingMiddlePivot(arr, partitionIndex + 1, high, partitionIndexHistory);
    }
    
    public static <E extends Comparable<? super E>> List<E> generateWorstCaseForQuickSortPivotPoint(List<E> input, Map<Integer, Integer> currentIndexToPreviousIndexMapping) {
        List<E> reverseOrdered = new ArrayList<>(input);
        reverseOrdered.sort(Collections.reverseOrder());
        List<E> worstCase = new ArrayList<>(Collections.nCopies(reverseOrdered.size(), null));
        int inOrderCount = 0;
        while (inOrderCount < worstCase.size()) {
            int whereToPut = (reverseOrdered.size() - inOrderCount - 1) / 2;
            if (worstCase.get(whereToPut) != null) {
                whereToPut = retrieveIndex(whereToPut, currentIndexToPreviousIndexMapping);
            }
            worstCase.set(whereToPut, reverseOrdered.get(inOrderCount));
            currentIndexToPreviousIndexMapping.put(whereToPut, worstCase.size() - inOrderCount - 1);
            inOrderCount++;
        }
        return worstCase;
    }
    
    public static <E extends Comparable<? super E>> void quickSortUsingMiddlePivot(List<E> input, List<Integer> partitionIndexHistory) {
        if (input == null || input.isEmpty()) {
            return;
        }
        quickSortUsingMiddlePivot(input, 0, input.size() - 1, partitionIndexHistory);
    }
    
    private static int retrieveIndex(int currentIndex, Map<Integer, Integer> currentIndexToPreviousIndexMapping) {
        if (!currentIndexToPreviousIndexMapping.containsKey(currentIndex)) {
            return currentIndex;
        }
        return retrieveIndex(currentIndexToPreviousIndexMapping.get(currentIndex), currentIndexToPreviousIndexMapping);
    }
}

I've conducted a simple test, and it has passed. However, I'm uncertain about the accuracy of my approach.

import org.junit.jupiter.api.Test;

import java.util.*;

import static org.junit.jupiter.api.Assertions.*;
import static worstcasegenerator.WorstCaseForMiddlePivotQuickSort.generateWorstCaseForQuickSortPivotPoint;
import static worstcasegenerator.WorstCaseForMiddlePivotQuickSort.quickSortUsingMiddlePivot;

class WorstCaseForMiddlePivotQuickSortTest {
    
    private List<Integer> generatePrefixSizeList(int size) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= size; i++) {
            list.add(i);
        }
        return list;
    }
    
    private void checkIfIsWorstCase(List<Integer> partitionIndexHistory, int size) {
        assertEquals(size - 1, partitionIndexHistory.size());
        for (int i = 0; i < partitionIndexHistory.size(); i++) {
            assertEquals(size - 1 - i, partitionIndexHistory.get(i));
        }
    }
    
    @Test
    void testWorstCaseForMiddlePivotQuickSortGenerator() {
        for (int size = 1; size <= 100; size++) {
            List<Integer> testInput = generatePrefixSizeList(size);
            List<Integer> partitionIndexHistory = new ArrayList<>();
            Map<Integer, Integer> currentIndexToPreviousIndexMapping = new HashMap<>();
            List<Integer> worstCase = generateWorstCaseForQuickSortPivotPoint(testInput, currentIndexToPreviousIndexMapping);
            System.out.println("input size: " + size + " , worst case input : " + worstCase);
            quickSortUsingMiddlePivot(worstCase, partitionIndexHistory);
            System.out.println("partition index history: " + partitionIndexHistory);
            checkIfIsWorstCase(partitionIndexHistory, size);
        }
    }
}

I'm seeking feedback on correctness and potential improvements for this solution. Specifically, I'd like insights into optimizing the algorithm, improving code readability, etc.

Any feedback, suggestions, or improvements would be greatly appreciated. Thank you!

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

cite your reference

There is a rich literature on QuickSort. Pick an author and cite the work.

Preferably work that includes worst case analysis, so we don't need a second citation, and so there's consistent notation throughout.

write down loop variants

Also pre- and post- conditions.

You don't have to throw an error if caller of partition() passed in some low > high parameters, but it would improve clarity. Especially for the case of low == high -- is it OK for caller to do that? The code can tell the Gentle Reader that, and seeing such an error during interactive testing might quickly reveal an OBOB, saving you some debugging effort. I know, I know, I see a caller making an if (low >= high) { test. What I'm shooting for is Local Analysis, being able to reason about a function in isolation, understanding the promises involved. The author's goal should be to make it easy for the Gentle Reader to reason about what's happening.

Within the loop, and/or at the end of partition(), it would be nice to see a comment and/or assertion describing what we guarantee upon exit.

Since generateWorstCaseForQuickSortPivotPoint() covers less familiar ground, the above points are especially relevant for that code.

concise identifier

whereToPut isn't a bad identifier, but it sounds like a temporary name you meant to come back to and rename later. Consider using a straightforward noun like worstLocation.

define a logging object

The partitionIndexHistory is a common parameter that comes along for the ride throughout. Which is a code smell. The code is telling you that it wants you to create a Sorter object with the history as an attribute. Then we can make the usual quicksort calls without noisily drawing attention to the history log which will be side effected.

chatty test

testWorstCaseForMiddlePivotQuickSortGenerator() sends many lines to stdout. Prefer to make automated unit tests succeed silently, displaying Green Bar rather than Red.

\$\endgroup\$

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.