please do it in java language In this assignment, we will create a sorting progr
ID: 3604190 • Letter: P
Question
please do it in java language
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**
Explanation / Answer
import java.io.*;
import java.util.*;
class sort
{
void display(int arr[])
{
for (int i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
}
// Sorts array a[0..n-1] using Bogo sort
void bogo_Sort(int[] a)
{
// if array is not sorted then shuffle the
// array again
while (bogo_isSorted(a) == false)
bogo_shuffle(a);
}
// To generate permuatation of the array
void bogo_shuffle(int[] a)
{
// Math.random() returns a double positive
// value, greater than or equal to 0.0 and
// less than 1.0.
for (int i=1; i <= a.length; i++)
bogo_swap(a, i, (int)(Math.random()*i));
}
// Swapping 2 elements
void bogo_swap(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// To check if array is sorted or not
boolean bogo_isSorted(int[] a)
{
for (int i=1; i<a.length; i++)
if (a[i] < a[i-1])
return false;
return true;
}
void selection_sort(int arr[])
{
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
void insertion_sort(int arr[])
{
int n = arr.length;
for (int i=1; i<n; ++i)
{
int key = arr[i];
int j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
void bubble_sort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{
// swap temp and arr[i]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
int quick_partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; 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 */
void quick_sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = quick_partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quick_sort(arr, low, pi-1);
quick_sort(arr, pi+1, high);
}
}
int shell_sort(int arr[])
{
int n = arr.length;
// Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2)
{
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already
// in gapped order keep adding one more element
// until the entire array is gap sorted
for (int i = gap; i < n; i += 1)
{
// add a[i] to the elements that have been gap
// sorted save a[i] in temp and make a hole at
// position i
int temp = arr[i];
// shift earlier gap-sorted elements up until
// the correct location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
// put temp (the original a[i]) in its correct
// location
arr[j] = temp;
}
}
return 0;
}
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void merge_sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
merge_sort(arr, l, m);
merge_sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
static void gnome_Sort(int arr[], int n)
{
int index = 0;
while (index < n)
{
if (index == 0)
index++;
if (arr[index] >= arr[index-1])
index++;
else
{
int temp =0;
temp = arr[index];
arr[index] = arr[index-1];
arr[index-1] = temp;
index--;
}
}
return;
}
void cocktail_Sort(int a[])
{
boolean swapped = true;
int start = 0;
int end = a.length;
while (swapped==true)
{
// reset the swapped flag on entering the
// loop, because it might be true from a
// previous iteration.
swapped = false;
// loop from bottom to top same as
// the bubble sort
for (int i = start; i < end-1; ++i)
{
if (a[i] > a[i + 1])
{
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
swapped = true;
}
}
// if nothing moved, then array is sorted.
if (swapped==false)
break;
// otherwise, reset the swapped flag so that it
// can be used in the next stage
swapped = false;
// move the end point back by one, because
// item at the end is in its rightful spot
end = end-1;
// from top to bottom, doing the
// same comparison as in the previous stage
for (int i = end-1; i >=start; i--)
{
if (a[i] > a[i+1])
{
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
swapped = true;
}
}
// increase the starting point, because
// the last stage would have moved the next
// smallest number to its rightful spot.
start = start+1;
}
}
static int radix_getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void radix_countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count,0);
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
static void radix_sort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = radix_getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
radix_countSort(arr, n, exp);
}
public void heap_sort(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
public static void main(String args[])
{
int ch,n,i;
int a[]=new int[50];
Scanner sc=new Scanner(System.in);
System.out.println("1.Bogo Sort");
System.out.println("2.Selection Sort");
System.out.println("3.Insertion Sort");
System.out.println("4.Bubble Sort");
System.out.println("5.Quick Sort");
System.out.println("6.Shell Sort");
System.out.println("7.Merge Sort");
System.out.println("8.Gnome Sort");
System.out.println("9.Cocktail Sort");
System.out.println("10.Radix Sort");
System.out.println("11.Heap Sort");
System.out.println("Enter your choice");
ch=sc.nextInt();
System.out.println("Enter the size of the array");
n=sc.nextInt();
System.out.println("Enter the elements in the array");
for(i=0;i<n;i++)
a[i]=sc.nextInt();
sort obj=new sort();
switch(ch)
{
case 1:
obj.bogo_Sort(a);
obj.display(a);
break;
case 2:
obj.selection_sort(a);
obj.display(a);
break;
case 3:
obj.insertion_sort(a);
obj.display(a);
break;
case 4:
obj.bubble_sort(a);
obj.display(a);
break;
case 5:
obj.quick_sort(a,0,n-1);
obj.display(a);
break;
case 6:
obj.shell_sort(a);
obj.display(a);
break;
case 7:
obj.merge_sort(a,0,n-1);
obj.display(a);
break;
case 8:
obj.gnome_Sort(a,n);
obj.display(a);
break;
case 9:
obj.cocktail_Sort(a);
obj.display(a);
break;
case 10:
obj.radix_sort(a,n);
obj.display(a);
break;
case 11:
obj.heap_sort(a);
obj.display(a);
break;
default:
System.out.println("Invalid Choice");
break;
}
}
}
/*
BOGO SORT
Worst Case : O()
Average Case: O(n*n!)
Best Case : O(n)
SELECTION SORT
Time Complexity: O(n^2)
INSERTION SORT
Time Complexity: O(n*n)
BUBBLE SORT
Worst Case Time Complexity: O(n*n)
Average Case Time Complexity: O(n*n)
Best Case Time Complexity: O(n)
QUICK SORT
Worst Case Time Complexity: theta(n^2)
Average Case Time Complexity: O(nlogn)
Best Case Time Complexity: theta(nlogn)
SHELL SORT
Time Complexity:O(n^2)
MERGE SORT
Average Case Time Complexity: theta(nlogn)
Worst Case Time Complexity: theta(nlogn)
Best Case Time Complexity: theta(nlogn)
GNOME SORT
Time complexity is O(N^2)
COCKTAIL SORT
Worst Case Time Complexity:O(n*n)
Average Case Time Complexity: O(n*n)
Best Case Time Complexity: O(n)
RADIX SORT
Time complexity : O((n+b) * logb(k))
HEAP SORT
Time complexity : O(nLogn)
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.