Investigating Sorting Algorithms In this assignment we will create a sorting pro
ID: 3689746 • Letter: I
Question
Investigating Sorting Algorithms In this assignment we will create a sorting program that provides the user with a large assortment of sorting methods and options. The user should be able to choose from a menu to select which Sort they would like to use. For each Sort, be sure to sort four arrays (*see note below), and list the time it took to sort each of the four arrays either in milliseconds or nanoseconds. For each sorting algorithm, write a brief description of how the sort works, and be sure to note the time complexity. You can include both in the code as comments. The user should be able to choose from the following sort algorithms (Be sure to implement all). If you use any other resource (including online) you need to cite the source in your code
. Bogo Sort **
Selection Sort
Insertion Sort
Bubble Sort
Quick Sort
Shell Sort
Merge Sort
Gnome Sort
Cocktail Sort
Radix Sort
** One more Sort of your choice**
*Note: For the assignment, you will need to create several arrays of integers of the following sizes {20,100, 500, 1000}. Fill the values of these arrays with random values between the number 0 and 999. You may need to reinitialize these arrays if the user decides to run another sort. You may also need values of 1000 to 9999 if you want to use Radix from the in-class example. **For Bogo Sort, due to the speed you may want to give the user a choice of the array size so that it may finish the sort in a somewhat timely manner. i have following codes for sort methods so far:
import java.util.*; // for Random
public class Sorting
{
private static final Random RAND = new Random(42);
public static void main(String[] args)
{
int LENGTH = 1000;
int RUNS = 17;
for (int i = 0; i < RUNS; i++)
{
int[] a = createRandomArray(LENGTH);
long startTime1 = System.currentTimeMillis();
quickSort(a);
long endTime1 = System.currentTimeMillis();
if (!isSorted(a))
{
throw new RuntimeException("not sorted afterward: " + Arrays.toString(a));
}
System.out.printf("%10d elements => %6d ms ", LENGTH, endTime1 - startTime1);
LENGTH *= 2;
}
}
public static void quickSort(int[] a)
{
quickSort(a, 0, a.length - 1);
}
private static void quickSort(int[] a, int min, int max)
{
if (min >= max)
{
return;
}
int pivot = a[min];
swap(a, min, max);
int i = min;
int j = max - 1;
while (i <= j)
{
while (i <= j && a[i] < pivot)
{
i++;
}
while (i <= j && a[j] > pivot)
{
j--;
}
if (i <= j)
{
swap(a, i, j);
i++;
j--;
}
}
swap(a, max, i);
quickSort(a, min, i - 1);
quickSort(a, i + 1, max);
}
public static void mergeSort(int[] a)
{
if (a.length >= 2)
{
int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);
mergeSort(left);
mergeSort(right);
int i1 = 0;
int i2 = 0;
for (int i = 0; i < a.length; i++)
{
if (i2 >= right.length ||(i1 < left.length && left[i1] < right[i2]))
{
a[i] = left[i1];
i1++;
}
else
{
a[i] = right[i2];
i2++;
}
}
}
}
public static void shellSort(int[] a)
{
for (int gap = a.length / 2; gap >= 1; gap = gap / 2)
{
for (int i = gap; i < a.length; i++)
{
int temp = a[i];
int j = i;
while (j >= gap && a[j - gap] > temp)
{
a[j] = a[j - gap];
j -= gap;
}
a[j] = temp;
}
}
}
public static void insertionSort(int[] a)
{
for (int i = 1; i < a.length; i++)
{
int temp = a[i];
int j = i;
while (j >= 1 && a[j - 1] > temp)
{
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
}
public static void selectionSort(int[] a)
{
for (int pass = 0; pass < a.length; pass++)
{
int min = pass;
for (int j = pass + 1; j < a.length; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
swap(a, pass, min);
}
}
public static void bubbleSort(int[] a)
{
for (int pass = 0; pass < a.length; pass++)
{
boolean changed = false;
for (int i = 0; i < a.length - 1 - pass; i++)
{
if (a[i] > a[i + 1])
{
swap(a, i, i + 1);
changed = true;
}
}
if (!changed)
{
return;
}
}
}
public static void bogoSort(int[] a)
{
while (!isSorted(a))
{
shuffle(a);
}
}
public static void heapSort(int[] a)
{
for (int i = a.length / 2; i >= 0; i--)
{
bubbleDown(a, i, a.length - 1);
}
for (int i = a.length - 1; i > 0; i--)
{
swap(a, 0, i);
bubbleDown(a, 0, i - 1);
}
}
private static void bubbleDown(int[] a, int hole, int max)
{
int temp = a[hole];
while (hole * 2 <= max)
{
int child = hole * 2;
if (child != max && a[child + 1] > a[child])
{
child++;
}
if (a[child] > temp)
{
a[hole] = a[child];
}
else
{
break;
}
hole = child;
}
a[hole] = temp;
}
public static void bucketSort(int[] a)
{
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int k : a)
{
max = Math.max(max, k);
min = Math.min(min, k);
}
int[] counters = new int[max - min + 1];
for (int k : a)
{
counters[k - min]++;
}
int i = 0;
for (int j = 0; j < counters.length; j++)
{
for (int k = 0; k < counters[j]; k++)
{
a[i] = j + min;
i++;
}
}
public static void radixSort(int[] a)
{
Queue<Integer>[] buckets =(Queue<Integer>[]) new Queue[10];
for (int i = 0; i < buckets.length; i++)
{
buckets[i] = new ArrayDeque<Integer>();
}
int digit = 1;
while (toBuckets(a, digit, buckets))
{
fromBuckets(a, buckets);
digit++;
}
}
private static boolean toBuckets(int[] a, int digit, Queue<Integer>[] buckets)
{
boolean nonZero = false;
for (int element : a)
{
int which = kthDigit(element, digit);
buckets[which].add(element);
if (which != 0)
{
nonZero = true;
}
}
return nonZero;
}
private static final int kthDigit(int element, int k)
{
for (int i = 1; i <= k - 1; i++)
{
element = element / 10;
}
return element % 10;
}
private static void fromBuckets(int[] a, Queue<Integer>[] buckets)
{
int i = 0;
for (int j = 0; j < buckets.length; j++)
{
while (!buckets[j].isEmpty())
{
a[i] = buckets[j].remove();
i++;
}
}
}
public static void stoogeSort(int[] a)
{
stoogeSort(a, 0, a.length - 1);
}
private static void stoogeSort(int[] a, int min, int max)
{
if (min < max)
{
if (a[min] > a[max])
{
swap(a, min, max);
}
int - min + 1) / 3;
if (oneThird >= 1)
{
stoogeSort(a, min, max - oneThird);
stoogeSort(a, min + oneThird, max);
stoogeSort(a, min, max - oneThird);
}
}
}
private static final void swap(int[] a, int i, int j)
{
if (i != j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
private static void shuffle(int[] a)
{
for (int i = 0; i < a.length; i++)
{
int randomIndex = (int) (Math.random() * a.length - i);
swap(a, i, i + randomIndex);
}
}
private static boolean isSorted(int[] a)
{
for (int i = 0; i < a.length - 1; i++)
{
if (a[i] > a[i + 1])
{
return false;
}
}
return true;
}
public static int[] createRandomArray(int length)
{
int[] a = new int[length];
for (int i = 0; i < a.length; i++)
{
a[i] = RAND.nextInt(1000000);
}
return a;
}
public static int[] createAscendingArray(int length)
{
int[] a = new int[length];
for (int i = 0; i < a.length; i++)
{
a[i] = i;
}
return a;
}
public static int[] createDescendingArray(int length)
{
int[] a = new int[length];
for (int i = 0; i < a.length; i++)
{
a[i] = a.length - 1 - i;
}
return a;
}
}
so now all i need is to write a program to give the user an option when the program starts where they can pick what sort they want to run. Like with a menu of options, and from there they can choose what sort they want to run.Can anyone please help me with this ?And this is java language.
Explanation / Answer
Please find below answer--->
import java.io.*;
class sortArray
{
private static final Random RAND = new Random(42);
public static void main(String[] args)
{
int LENGTH = 1000;
int RUNS = 17;
for (int i = 0; i < RUNS; i++)
{
int[] a = createRandomArray(LENGTH);
}
}
}
int a[];
int n;
static BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
public sortArray(int nn) // Constructor
{
a = new int[nn];
n = nn;
}
public static void main(String args[]) throws IOException
{
System.out.print(" Enter the size of the array : ");
int nn = Integer.parseInt(br.readLine());
sortArray call = new sortArray(nn);
// Read array from user
System.out.println(" Enter " +nn +" elements :");
call.readArray();
// Ask for choosing the sorting technique
System.out.println("Choose Sorting Technique : ");
System.out.println("1 : Bubble Sort");
System.out.println("2 : Selection Sort");
System.out.println("3 : Insertion Sort");
System.out.println("4 : Quick Sort");
system.out.println("5 : Merge Sort");
System.out.println("6 : Shell Sort");
system.out.println("7 : Radix Sort");
system.out.print(" Your Choice : ");
int choice = Integer.parseInt(br.readLine());
switch(choice)
{
case 1:
call.bubbleSort();
break;
case 2:
call.selectionSort();
break;
case 3:
call.insertionSort();
break;
case 4:
call.quickSort();
break;
case 5:
call.mergeSort();
break;
case 6:
call.ShellSort();
break;
case 7:
call.RadixSort();
break;
default :
System.out.println(" Invalid Choice !");
System.exit(1);
break;
}
call.display(); // Print the sorted array
}
public void readArray() throws IOException
{
for(int i=0;i<n;i++)
a[i] = Integer.parseInt(br.readLine());
}
public void bubbleSort()
{
int t;
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
}
public void selectionSort()
{
int t, min;
for(int i=0;i<n-1;i++)
{
min = i;
for(int j=i+1;j<n;j++)
2{
if(a[min]>a[j])
min = j;
}
if(min!=i)
{
t = a[min];
a[min] = a[i];
a[i] = t;
}
}
}
public void insertionSort()
{
int t,j;
for(int i=1;i<n;i++)
{
j = i-1;
t = a[i];
while(t<a[j] && j>=0)
{
a[j+1] = a[j];
j--;
}
a[j+1] = t;
}
}
public void quickSort()
{
int j,l,u;
if(l<u)
{
j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
}
}
int partition(intl,intu)
{
int v,i,j,temp;
v=a[l];
i=l;
j=u+1;
do
{
do
i++;
while(a[i]<v && i<=u);
do
j--;
while(v<a[j]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
while(i<j);
a[l]=a[j];
a[j]=v;
return(j);
}
public void merge_sort()
{
int i, j,k ;
if(i<j)
{
k=(i+j)/2;
merge_sort(a,i,k);
merge_sort(a,k+1,j);
merge(a,i,k,j);
}
}
void merge()
int l,m,u,i,j,k,c[MAX];
i=l;
j=m+1;
k=0;
while(i<m && j<=u)
{
if(a[i]<a[j])
{
c[k]=a[i];
k++; i++;
}
else
{
c[k]=a[j];
k++; j++;
}
}
while(i<=m)
{
c[k]=a[i];
i++; k++;
}
while(j<=u)
{
c[k]=a[j];
k++;j++;
}
for(i=l,j=0;i<=u;i++,j++)
a[i]=c[j];
}
public void shell_sort()
{
int n,i.j step,temp;
for(step=n/2;step>0;step=step/2)
for(i=step;i<n;i++)
{
temp=a[i];
for(j=i;j>=step;j=j-step)
if(temp<a[j-step])
a[j]=a[j-step];
else
break;
a[j]=temp;
}
public void radix_sort()
{
int n, buckets[10][10],count[10];
int passes, large,div,bucketno,i,j,k;
large=a[0];
for(i=1;i<n;i++)
if(a[i]>large)
large=a[i];
passes=0;
while(large>0)
{ passes++;
large=large/10;
}
div=1;
for(i=1;i<=passes;i++)
for(j=0;j<=9;j++)
count[j]=0;
for(j=0;j<n;j++)
{ bucketnoi=(a[j]/div)%10;
buckets[bucketno][count[bucketno]]
=a[j];
count[bucketno]++;
}
j=0;
for(bucketno=0;bucketno<=9;bucketno++)
for(k=0;k<count[bucketno];k++)
a[j++]=buckets[bucketno][k];
div=div*10;
}
}
public void display()
{
System.out.println(" Sorted Array :");
for(int i=0;i<n;i++)
System.out.println(a[i]);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.