Inplace quick sort

Question

Write a java program to sort a list of integers using ‘in place’ Quicksort algorithm.

Generate the list randomly every time using the java.util.Random class. Allow the user to choose the size of the array. The program should display the result of sorting the array of that size using different pivot choices. In particular, try these 4 choices –

 First element as pivot
 Randomly choosing the pivot element
 Choosing the median of 3 randomly chosen elements as the pivot
 Median of first center and last element (book technique).

PLEASE dont give me the implementation because I would like to try on my own. I want to know what is inplace quick sort? How is it different from the regular quiksort. Is it regular quicksort. I am really confused. I would like someone to provide the pusedocode or explanation in plain english will help too.

Answer 1

Inplace sorting - it's when you operate on the original array, given to you from outside, as opposed to creating some new arrays and using them in any way. Inplace sorting takes O(1) space, as opposed to O(n)+ when using additional data structres

Example of inplace sort:

    public static void simpleBubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length; j++) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);
                }
            }
        }
    }

As opposed to Merge sort that creates arrays along the way, and by the end combines them and returns NOT the original (given to us) array, but an array containing the result.

    public static int[] mergeSort(int[] arr) {
        if (arr.length < 2) return arr;

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[mid + arr.length % 2];

        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i < mid) {
                left[i] = arr[i];
            } else {
                right[j++] = arr[i];
            }
        }
        // keeps going until there's 1 element in each array[]
        return mergeReturn(mergeSort(left), mergeSort(right));
    }

    private static int[] mergeReturn(int[] leftArr, int[] rightArr) {
        int leftPointer = 0, rightPointer = 0, combinedSize = leftArr.length + rightArr.length;
        int[] merged = new int[combinedSize];

        for (int i = 0; i < combinedSize; i++) {
            if (leftPointer < leftArr.length && rightPointer < rightArr.length) {
                if (leftArr[leftPointer] < rightArr[rightPointer]) {
                    merged[i] = leftArr[leftPointer++];
                } else {
                    merged[i] = rightArr[rightPointer++];
                }
            } else if (leftPointer < leftArr.length) { // adding the last element
                merged[i] = leftArr[leftPointer++];
            } else {
                merged[i] = rightArr[rightPointer++];
            }
        }
        return merged;
    }