Write a program in Java that performs the Randomized Quicksort algorithm. a) Cre

Question

Write a program in Java that performs the Randomized Quicksort algorithm. a) Create the randomizedPartition method. Use the pseudocode shown in the lecture. b) Implement the recursive randomizedQuicksort method. c) Test your codes by writing a program that uses the following input array: int[] array = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; d) Your output should display the following versions of the array: I. The original input array II. The sub-arrays after each of the randomizedPartition calls has completed III. The final sorted array after performing the Quicksort algorithm

Explanation / Answer

package com.javacodegeeks.sorting.quicksort;
public class QuicksortExample {

private static int []a;

public static void main(String[] args) {
// Get a random generated array
a = getArray();

// prints the given array
printArray();

// sort the array
sort();

System.out.println("");

//prints the sorted array

printArray();

}



// This method sorts an array and internally calls quickSort

public static void sort(){

int left = 0;

int right = a.length-1;



quickSort(left, right);

}

private static void quickSort(int left,int right){
// If both cursor scanned the complete array quicksort exits
if(left >= right)
return;
// For the simplicity, we took the right most item of the array as a pivot
int pivot = a[right];
int partition = partition(left, right, pivot);

// Recursively, calls the quicksort with the different left and right parameters of the sub-array
quickSort(0, partition-1);
quickSort(partition+1, right);
}

4
// This method is used to partition the given array and returns the integer which points to the sorted pivot index
private static int partition(int left,int right,int pivot){
int leftCursor = left-1;
int rightCursor = right;
while(leftCursor < rightCursor){
while(a[++leftCursor] < pivot);

while(rightCursor > 0 && a[--rightCursor] > pivot);
if(leftCursor >= rightCursor){
break;
}else{
swap(leftCursor, rightCursor);
}
}
swap(leftCursor, right);
return leftCursor;
}

// This method is used to swap the values between the two given index

public static void swap(int left,int right){
int temp = a[left];
a[left] = a[right];
a[right] = temp;
}
public static void printArray(){
for(int i : a){
System.out.print(i+" ");
}
}
public static int[] getArray(){
int size=10;
int []array = new int[size];
int item = 0;
for(int i=0;i<size;i++){
item = (int)(Math.random()*100);
array[i] = item;
}
return array;
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.