Question

Programming Language : Java

Modify the quicksort algorithm such that it uses the last item as the pivot instead of the 1^st. Also, sort in descending order, instead of ascending order.

NOTE: Do not move the last element into the first element of the array. You must treat the algorithm as if the pivot is actually sitting in the last location of the array.

After it has been sorted in descending order, go through all the items in the array and make sure that they all have the same number of digits as the largest element in the array by adding additional 5’s to the end of the numbers. For example, given the following sorted array:

324, 46, 6

After adding the additional digits, the array will look like the following:

324, 465, 655

Then sort the new array using radix sort indescending order.

Read the original data elements from a file. The elements in the file will be separated by some kind of white space, just like before. The number of elements will not exceed 10.

Answer 1

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;

public class Sort {

    private void quickSort(int array[], int start, int end) {
        if (start < end) {
            /* pi is partitioning index, array[pi] is
              now at right place */
            int pi = partition(array, start, end);

            // Recursively sort elements before
            // partition and after partition
            quickSort(array, start, pi - 1);
            quickSort(array, pi + 1, end);
        }
    }

    /* Taking last element as pivot, places the pivot
     element at its correct position in sorted array,
     and places all smaller elements to right and all
     larger elements to left */
    private int partition(int array[], int start, int end) {
        int pivot = array[end];
        int i = (start - 1); // index of larger element
        for (int j = start; j < end; j++)
            if (array[j] > pivot) {
                i++;
                // swap array[i] and array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }

        // swap array[i+1] and array[end] (or pivot)
        int temp = array[i + 1];
        array[i + 1] = array[end];
        array[end] = temp;
        return i + 1;
    }

    private void printArray(int array[]) {
        for (int item : array) System.out.print(item + " ");
        System.out.println();
    }

    private void equifyDigits(int[] array) {

        //Find out length of the greatest number
        int maxLength = String.valueOf(array[0]).length();

        for (int i = 1; i < array.length; i++) {

            //Get length of subsequent numbers
            int length = String.valueOf(array[i]).length();

            /* If length is less than that of the
            greatest number, keep appending 5 to the
            end until length becomes equal*/
            while (length < maxLength) {
                array[i] = (array[i] * 10) + 5;
                length++;
            }
        }
    }

    private void radixSort(int array[], int n) {
        // Find the maximum number to know number of digits
        int m = getMax(array, n);

        // Do counting sort for every digit. Note that instead
        // of passing digit number, exp is passed. exp is 10^i
        // where i is current digit number
        for (int exp = 1; m / exp > 0; exp *= 10)
            countSort(array, n, exp);
    }

    // A function to do counting sort of array[] according to
    // the digit represented by exp.
    private static void countSort(int array[], int n, int exp) {
        int output[] = new int[n]; // output array
        int i;
        int bucket[] = new int[10];
        Arrays.fill(bucket, 0);

        // Store count of occurrences in count[]
        for (i = 0; i < n; i++)
            bucket[9 - (array[i] / exp) % 10]++;

        // Change count[i] so that count[i] now contains
        // actual position of this digit in output[]
        for (i = 1; i < 10; i++)
            bucket[i] += bucket[i - 1];

        // Build the output array
        for (i = n - 1; i >= 0; i--) {
            output[bucket[9 - (array[i] / exp) % 10] - 1] = array[i];
            bucket[9 - (array[i] / exp) % 10]--;
        }

        // Copy the output array to array[], so that array[] now
        // contains sorted numbers according to curent digit
        for (i = 0; i < n; i++)
            array[i] = output[i];
    }

    private int getMax(int array[], int n) {
        int max = array[0];
        for (int i = 1; i < n; i++)
            if (array[i] > max)
                max = array[i];
        return max;
    }

    public static void main(String args[]) throws Exception {

        String data[] = new String(Files.readAllBytes(Paths.get("C:\\Path\\to\\file\\test.txt")))
                .split(" ");
        int n = data.length;
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(data[i]);
        }

        Sort ob = new Sort();

        ob.quickSort(arr, 0, n - 1);

System.out.print("After Quick Sorting: ");
ob.printArray(arr);
ob.equifyDigits(arr);
System.out.print("After Appending 5: ");
ob.printArray(arr);
ob.radixSort(arr, n);
System.out.print("After Radix Sorting: ");

        ob.printArray(arr);
    }
}