Please write pseudo code for this program public class SortingBenchMarks { int b
ID: 3739573 • Letter: P
Question
Please write pseudo code for this program
public class SortingBenchMarks {
int bubbleCount = 0;
int selectionCount = 0;
int insertionCount = 0;
int quickCount = 0;
public int bubbleSort(int[] array)
{
int maxElement;
int index;
int temp;
for(maxElement = array.length - 1; maxElement >=0; maxElement--){
for(index = 0; index <= maxElement - 1; index++){
if(array[index] > array[index + 1]){
temp = array[index];
array[index] = array[index + 1];
array[index + 1] = temp;
bubbleCount += 2;
}
}
}
return bubbleCount;
}
public int selectionSort(int[] array) {
int strtScan;
int indx;
int minIndx;
int miniValue;
for(strtScan = 0; strtScan < (array.length-1); strtScan++){
minIndx = strtScan;
miniValue = array[strtScan];
for(indx = strtScan + 1; indx < array.length; indx++){
if(array[indx] < miniValue){
miniValue = array[indx];
minIndx = indx;
}
}
array[minIndx] = array[strtScan];
array[strtScan] = miniValue;
selectionCount += 2;
}
return selectionCount;
}
public int insertionSort(int[] array){
int unsortedValue;
int scan;
for(int index = 1; index < array.length; index++){
unsortedValue = array[index];
scan = index;
while(scan > 0 && array[scan - 1] > unsortedValue){
array[scan] = array[scan - 1];
scan--;
insertionCount++;
}
array[scan] = unsortedValue;
insertionCount++;
}
return insertionCount;
}
public int quickSort(int array[]){
doQuickSort(array, 0, array.length - 1);
return quickCount;
}
private void doQuickSort(int array[], int start, int end){
int pivotPoint;
if(start < end){
pivotPoint = partition(array, start, end);
doQuickSort(array, start, pivotPoint - 1);
doQuickSort(array, pivotPoint + 1, end);
}
}
private int partition(int array[], int start, int end){
int pivotValue;
int endOfLeftList;
int mid;
mid = (start + end) / 2;
swap(array, start, mid);
pivotValue = array[start];
endOfLeftList = start;
for(int scan = start + 1; scan <= end; scan++){
if(array[scan] < pivotValue){
endOfLeftList++;
swap(array, endOfLeftList, scan);
}
}
swap(array, start, endOfLeftList);
return endOfLeftList;
}
private void swap(int[] array, int a, int b){
int temp;
temp = array[a];
array[a] = array[b];
array[b] = temp;
quickCount += 2;
}
}
//TestClass.java
import java.util.Random;
public class TestClass {
public static void main(String[] args) {
int bubbleValues[] = new int[20];
int selectionValues[] = new int[20];
int insertionValues[] = new int[20];
int quickValues[] = new int[20];
Random input = new Random();
for(int i = 0; i < 20; i++){
bubbleValues[i] = input.nextInt(100);
selectionValues[i] = input.nextInt(100);
insertionValues[i] = input.nextInt(100);
quickValues[i] = input.nextInt(100);
}
SortingBenchMarks in = new SortingBenchMarks();
int bubbleCount = in.bubbleSort(bubbleValues);
int selectionCount = in.selectionSort(selectionValues);
int insertionCount = in.insertionSort(insertionValues);
int quickCount = in.quickSort(quickValues);
System.out.println("Elements in the bubble array: ");
for(int i =0; i < 20; i++){
System.out.print(" " +bubbleValues[i]);
}
System.out.println();
System.out.println("Elements in the selection array:");
for(int i = 0; i <20; i++){
System.out.print( " " +selectionValues[i]);
}
System.out.println();
System.out.println("Elements in the insertion array:");
for(int i = 0; i <20; i++){
System.out.print( " " +insertionValues[i]);
}
System.out.println();
System.out.println("Elements in the quick array:");
for(int i = 0; i <20; i++){
System.out.print( " " +quickValues[i]);
}
System.out.println();
System.out.println("Bubble swaps: " +bubbleCount);
System.out.println("Selection swaps: " +selectionCount);
System.out.println("Insertion swaps: " +insertionCount);
System.out.println("Quick swaps: " +quickCount);
}
}
Explanation / Answer
Please find the code with detailed Pseudocode above the respective algorithm.
CODE
=======================
public class SortingBenchMarks {
// create local variables to store the number of swaps
int bubbleCount = 0; //no. of swaps in Bubble Sort
int selectionCount = 0; //no. of swaps in Selection Sort
int insertionCount = 0; //no. of swaps in Insertion Sort
int quickCount = 0; //no. of swaps in Quick Sort
/*
* PSEUDOCODE of BUBBLE SORT
*
* begin BubbleSort(list)
* for maxElement = (arr_length-1) to 0
* for i = 0 to (arr_length-1)
* if list[i] > list[i+1]
* swap(list[i], list[i+1])
* bubbleCount = bubbleCount + 2
* end if
* end for
* end for
* return bubbleCount
* end BubbleSort
*
*/
public int bubbleSort(int[] array)
{
int maxElement;
int index;
int temp;
for(maxElement = array.length - 1; maxElement >=0; maxElement--){
for(index = 0; index <= maxElement - 1; index++){
if(array[index] > array[index + 1]){
temp = array[index];
array[index] = array[index + 1];
array[index + 1] = temp;
bubbleCount += 2;
}
}
}
return bubbleCount;
}
/*
* PSEUDOCODE of SELECTION SORT
*
* begin SelectionSort(list)
* for strtScan = 0 to (arr_length-2)
* min_index = strtScan
* min_value = list[min_index]
*
* for indx = (strtScan + 1) to (arr_length-1)
* if list[indx] < min_value
* min_value = list[indx]
* min_index = indx
* end if
* end for
*
* list[min_index] = list[strtScan]
* list[strtScan] = min_value
* selectionCount = selectionCount + 2
*
* end for
* return selectionCount
*
* end SelectionSort
*
*/
public int selectionSort(int[] array) {
int strtScan;
int indx;
int minIndx;
int miniValue;
for(strtScan = 0; strtScan < (array.length-1); strtScan++){
minIndx = strtScan;
miniValue = array[strtScan];
for(indx = strtScan + 1; indx < array.length; indx++){
if(array[indx] < miniValue){
miniValue = array[indx];
minIndx = indx;
}
}
array[minIndx] = array[strtScan];
array[strtScan] = miniValue;
selectionCount += 2;
}
return selectionCount;
}
/*
* PSEUDOCODE of INSERTION SORT
*
* begin InsertionSort(list)
* for indx = 1 to (arr_length-1)
* current_value = list[indx]
* scan = indx
*
* while scan > 0 AND list[scan - 1] > current_value
* list[scan] = list[scan - 1];
* scan = scan - 1
* insertionCount = insertionCount + 1
* end while
*
* list[scan] = current_value
* insertionCount = insertionCount + 2
*
* end for
* return insertionCount
*
* end InsertionSort
*
*/
public int insertionSort(int[] array){
int unsortedValue;
int scan;
for(int index = 1; index < array.length; index++){
unsortedValue = array[index];
scan = index;
while(scan > 0 && array[scan - 1] > unsortedValue){
array[scan] = array[scan - 1];
scan--;
insertionCount++;
}
array[scan] = unsortedValue;
insertionCount++;
}
return insertionCount;
}
// Driver method to do quick sort`
public int quickSort(int array[]){
doQuickSort(array, 0, array.length - 1);
return quickCount;
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
start --> Starting index,
end --> Ending index
*/
private void doQuickSort(int array[], int start, int end){
int pivotPoint;
if(start < end){
/* pivotPoint is partitioning index, arr[pivotPoint] is now at right place */
pivotPoint = partition(array, start, end);
// Separately sort elements before
// partition and after partition
doQuickSort(array, start, pivotPoint - 1);
doQuickSort(array, pivotPoint + 1, end);
}
}
/* This function takes last element as pivot, places
* the pivot element at its correct position in sorted
* array, and places all smaller (smaller than pivot)
* to left of pivot and all greater elements to right
* of pivot
*/
/*
* PSEUDOCODE of PARTIONING ALGO
*
* begin Parition(list, start, end)
*
* mid = (start + end)/2
* swap(list, start, mid)
* pivot = list[start]
*
* for scan = (start + 1) to (end)
* if list[scan] < pivot
* endOfLeftList = endOfLeftList + 1
* swap(list[endOfLeftList], list[scan])
* quickCount = quickCount + 2
* end if
* end for
*
* swap(list[start], list[endOfLeftList])
* quickCount = quickCount + 2
*
* return insertionCount
*
* end Parition
*
*/
private int partition(int array[], int start, int end){
int pivotValue;
int endOfLeftList;
int mid;
mid = (start + end) / 2;
swap(array, start, mid);
pivotValue = array[start];
endOfLeftList = start;
for(int scan = start + 1; scan <= end; scan++){
if(array[scan] < pivotValue){
endOfLeftList++;
swap(array, endOfLeftList, scan);
}
}
swap(array, start, endOfLeftList);
return endOfLeftList;
}
private void swap(int[] array, int a, int b){
int temp;
temp = array[a];
array[a] = array[b];
array[b] = temp;
quickCount += 2;
}
}
//TestClass.java
import java.util.Random;
public class TestClass {
public static void main(String[] args) {
// Create arrays of size 20 for sorting
int bubbleValues[] = new int[20];
int selectionValues[] = new int[20];
int insertionValues[] = new int[20];
int quickValues[] = new int[20];
Random input = new Random();
// fill the arrays with random values between 0 and 100
for(int i = 0; i < 20; i++){
bubbleValues[i] = input.nextInt(100);
selectionValues[i] = input.nextInt(100);
insertionValues[i] = input.nextInt(100);
quickValues[i] = input.nextInt(100);
}
SortingBenchMarks in = new SortingBenchMarks();
// Get the number of swaps using Bubble Sort,
// Selection Sort, Insertion Sort and Quick Sort
int bubbleCount = in.bubbleSort(bubbleValues);
int selectionCount = in.selectionSort(selectionValues);
int insertionCount = in.insertionSort(insertionValues);
int quickCount = in.quickSort(quickValues);
// Print the sorted array done using Bubble Sort
System.out.println("Elements in the bubble array: ");
for(int i =0; i < 20; i++){
System.out.print(" " +bubbleValues[i]);
}
System.out.println();
// Print the sorted array done using Selection Sort
System.out.println("Elements in the selection array:");
for(int i = 0; i <20; i++){
System.out.print( " " +selectionValues[i]);
}
System.out.println();
// Print the sorted array done using Insertion Sort
System.out.println("Elements in the insertion array:");
for(int i = 0; i <20; i++){
System.out.print( " " +insertionValues[i]);
}
System.out.println();
// Print the sorted array done using Quick Sort
System.out.println("Elements in the quick array:");
for(int i = 0; i <20; i++){
System.out.print( " " +quickValues[i]);
}
System.out.println();
// print the swap count of each sort algorithm
System.out.println("Bubble swaps: " +bubbleCount);
System.out.println("Selection swaps: " +selectionCount);
System.out.println("Insertion swaps: " +insertionCount);
System.out.println("Quick swaps: " +quickCount);
}
}