Question

Sorting algorithm: quick sort

Exercise One (20 marks) Given the following program body for implementing Quick sort, complete the program by writing code where required import java.util.Random; public class QuickSort public void quickSectlinti] A) QuickSort/A, O, A.length-1); private void guickSortlin Aiat low.int high) //Complete the code for the quicksort method (5 marks] private void swaplint[] a, int indexl, int index2) //Complete the code for the swap method [3 marks] private int setPivotlint low, int high) Random rand = new Random(); return cand.nextlati high-low)+1]+low; private int partition intl Aint low.int high) //Complete the code for the partition method (12 methods]

Answer 1

/*
 *  QuickSort.java
 */

import java.util.Random;

public class QuickSort
{
  public void quickSort(int A[])
  {
    quickSort(A, 0, A.length - 1);
  }

  private void quickSort(int A[], int low, int high)
  {
    if (low < high)
    {
      int pi = partition(A, low, high);
      quickSort(A, low, pi-1);
      quickSort(A, pi+1, high);
    }
  }

  private void swap(int[] A, int index1, int index2)
  {
    int temp = A[index1];
    A[index1] = A[index2];
    A[index2] = temp;
  }

  private int getPivot(int low, int high)
  {
    Random rand = new Random();
    return rand.nextInt((high-low) + 1) + low;
  }

  private int partition(int A[], int low, int high)
  {
    int piv_indx = getPivot(low, high);
    int pivot = A[piv_indx];
    swap(A, high, piv_indx);
    int i = (low - 1);
    for (int j = low; j < high; j++)
    {
      if (A[j] < pivot)
      {
        i++;
        swap(A, i, j);
      }
    }
    swap(A, i+1, high);
    return i+1;
  }
}






/*
 *  Main.java
 */

class Main
{
  public static void main(String args[])
  {
    QuickSort qs = new QuickSort();

    int[] A = {9,0,1,3,4,5,2,9,8,7,6,5,9,1,0,9};

    System.out.println("The unsorted array is: ");
    for (int i = 0; i < A.length; i++)
      System.out.print(A[i] + " ");

    qs.quickSort(A);
    System.out.println();

    System.out.println("The sorted array using quick sort is: ");
    for (int i = 0; i < A.length; i++)
      System.out.print(A[i] + " ");

  }
}

@imtusharsharma/SoulfulwordyStartup No description invite 2+ share new repl run saved Main.java Files http://SoulfulWordyStartup.imtusharsharma.repl.run 1 OpenJDK Runtime Environment (build 10.0.2+13-Ubuntu-lubuntu0.18.04.4) javac -classpath .:/run_dir/junit-4.12.jar -d . Main.java QuickSort.java java -classpath .:/run_dir/junit-4.12.jar Main The unsorted array is: Main.java Main.java 2 Randomized QuickSort 3 jdt.ls-java-project 4 9 0 1 3 4 5 2 9 8 7 6 5 9 1 0 9 QuickSort.java class Main The sorted array using quick sort is: 0 0 1 1 2 3 4 5 5 6 7 8 99 9 9 6 { public static void main(string args[ { QuickSort qs = new QuickSort(); 7 8 9 10 11 int [] A {9,0,1,3,4,5,2,9,8,7,6,5,9,1,0,9}; 12 13 System.out.println("The unsorted array is: "); for (int i = 0; i < A. length; i++) System.out.print (A[ i] + " "); 14 15 16 17 qs.quickSort(A); System.out.println ( ) ; 18 19 20 System.out.println ( "The sorted array using quick sort is: "); for (int i = 0; i < A.length; it+) System.out.print (A[ i] + " "); 21 23 24 } } 25 26