***Look at the implementation of the three sorting algorithms below. What detail
ID: 3742681 • Letter: #
Question
***Look at the implementation of the three sorting algorithms below. What details in them might help you write better test cases? (you don't need to write test cases for this, just identify code features)***
Below are the 3 Sorting Algorithms
Shotgun Sort
import java.util.*;
public class ShotgunSort
{
// This sorting method is also known as BogoSort. It is not efficient (not
// even a little).
public static void sort(int[] arr)
{
while(!isSorted(arr))
shuffle(arr);
}
private static boolean isSorted(int[] arr)
{
for(int i = 0 ; i < arr.length - 1; i++)
if (arr[i] > arr[i + 1])
return false;
return true;
}
private static void shuffle(int[] arr)
{
Random rand = new Random();
for(int i = arr.length - 1; i > 0; i--)
{
int index = rand.nextInt(i+1);
int tmp = arr[index];
arr[index] = arr[i];
arr[i] = tmp;
}
}
public static void main(String args[])
{
// Transform args into int array. This is a demo, so if it crashes,
// that's on you.
int[] arr = new int[args.length];
for(int i = 0; i < args.length; i++)
arr[i] = Integer.parseInt(args[i]);
sort(arr);
for(int i : arr)
System.out.println(i);
}
}
QuickSort Algorithm
public class QuickSort
{
// From http://www.geeksforgeeks.org/quick-sort/
/* 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 */
private static int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
private static void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
public static void sort(int arr[])
{
sort(arr, 0, arr.length - 1);
}
public static void main(String args[])
{
// Transform args into int array. This is a demo, so if it crashes,
// that's on you.
int[] arr = new int[args.length];
for(int i = 0; i < args.length; i++)
arr[i] = Integer.parseInt(args[i]);
sort(arr);
for(int i : arr)
System.out.println(i);
}
}
BubbleSort
public class BubbleSort {
// From: https://www.javatpoint.com/bubble-sort-in-java
public static void sort(int[] arr) {
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(String args[]) {
// Transform args into int array. This is a demo, so if it crashes,
// that's on you.
int[] arr = new int[args.length];
for(int i = 0; i < args.length; i++)
arr[i] = Integer.parseInt(args[i]);
sort(arr);
for(int i : arr)
System.out.println(i);
}
}
Explanation / Answer
Shotgun Sort
In bogo sort, you keep on shuffling the array till the array is sorted. So while writing test cases for bogo sort, for every shuffle, print the array and print the result of isSorted() function [it should return false for unsorted array and true for sorted array]. And make sure that the reshuffling is stopped once the array is sorted.
Quick sort
Quick sort picks an element as pivot and partitions the given array around the picked pivot. In you case, the last element is always picked as the pivot. The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.
Hence, in quick sort, write test cases to ensure that after each partition, the elements lesser than pivot are always on the left side and elements greater than the pivot are always on the right hand side. Also the partition stops when the array is sorted.
Bubble Sort:
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Hence while writing test cases for bubble sort, always check that the first adjacent elements which are in wrong order are swapped (each such swap is called an iteration). And the iteration stops when the array is sorted.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.