*** To do this assignment you are not to use any of the Collections API, or any
ID: 3858994 • Letter: #
Question
*** To do this assignment you are not to use any of the Collections API, or any pre-implemented sort routines in Java. ***
In this assignment you are required to make use of the sorting routines in chapter 8 of your text book. You must ask the user to select which sorting routine he/she wants to use out of those routines implemented in the book (Insertion Sort, Shell Sort, Merge Sort, or Quick Sort). Based on the user input, you need to call the corresponding routine.
You are required to write one main program that will read in any number of integers and store it in an array of ints (not an ArrayList). What you need to do first is to ask the user what sorting routine he/she would like to use. Then you need to ask the user how many integers to be entered as input, and then ask the user to input these integers.
Your program will store these integers into an array of integers first. Then your program is supposed to remove the duplicates out of this array by first sorting the array (using the user-specified sorting routine), and then removing any duplicates.
Your program must not copy these elements into another array to remove the duplicates. The duplicates should be removed in place which means in the same array. Also, you must sort the array first before you start duplicate removal.
Once your array (the same array you started with) has only unique numbers, your program should print out the array followed by a list of all the numbers that were duplicated. The numbers that were duplicated can be stored into another array.
--------
The following would be a sample scenario of running your program:
Make your choice of a sorting routine first. Then continue as follows:
Enter the number of integers: 10
Enter the 10 integers: 7 9 8 1 9 28 23 28 9 8
The resulting array is: 1 7 8 9 23 28
The numbers 8, 9, 28 were duplicated in the input.
----------
public static void main(String[] args)
{
//TO DO:
1. create menu
2. choose sort routine
3. ask how many element in array
4. fill array
5. Sort the array
6. check sorted array for duplicates
7. prints sorted array as well as the number that were duplicated
}
//Methods from the book
public static boolean duplicates (Object [] a)
{
for(int i = 0; i<a.length; i++)
{
for(int j = i + 1; j< a.length; j++)
{
if(a[i].equals(a[j]))
{
return true; //Duplicate found
}
}
}
return false; //not found
}
public static<AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType []a)
{
for(int p = 1; p<a.length; p++)
{
AnyType tmp = a[p];
int j = p;
for(; j>0 &&tmp.compareTo(a[j-1])<0;j--)
{
a[j] = a[j-1];
}
a[j] = tmp;
}
}
public static <AnyType extends Comparable<? super AnyType>> void shellSort(AnyType a[])
{
for(int gap = a.length/2; gap>0; gap = gap ==2?1 : (int) (gap/2.2))
{
for(int i = gap; i<a.length; i++)
{
AnyType tmp = a[i];
int j = i;
for(; j>=gap && tmp.compareTo(a[j-gap]) <0; j -=gap)
{
a[j] = a[j - gap];
}
a [j ]= tmp;
}
}
}
public static<AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType []a)
{
AnyType [] tmpArray = (AnyType []) new Comparable[a.length];
mergeSort (a, tmpArray, 0, a.length -1);
}
private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType []a, AnyType [] tmpArray, int left, int right )
{
if(left < right)
{
int center = (left + right)/2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center+1, right);
merge(a, tmpArray, left, center +1, right);
}
}
private static<AnyType extends Comparable<? super AnyType>> void merge(AnyType []a, AnyType [] tmpArray, int leftPos, int rightPos, int rightEnd)
{
int leftEnd = rightPos -1;
int tmpPos = leftPos;
int numElments = rightEnd - leftPos +1;
//main loop
while(leftPos <= leftEnd && rightPos <= rightEnd)
{
if(a[leftPos ].compareTo(a[rightPos])<= 0)
tmpArray[tmpPos++] = a[leftPos++];
else
tmpArray[tmpPos++] = a[rightPos++];
while(leftPos <= leftEnd)//copy rest of first half
tmpArray[tmpPos++] = a[leftPos++];
while(rightPos <= rightEnd)//copy rest of first half
tmpArray[tmpPos++] = a[leftPos++];
//copy tmpArray back
for(int i = 0; i <numElments; i++, rightEnd--)
{
a[rightEnd] = tmpArray[rightEnd];
}
}
}
public static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType []a)
{
quickSort(a, 0, a.length-1);
}
private static final int CUTOFF = 10;
private static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType []a, int low, int high)
{
if(low + CUTOFF> high)
{
insertionQSort(a, low, high);
} else
{
//Sort low, middle, high
int middle = (low+high)/2;
if(a[middle].compareTo(a[low])<0)
swapReferences(a, low, middle);
if(a[high].compareTo(a[low])<0)
swapReferences(a, low, high);
if(a[high].compareTo(a[middle])<0)
swapReferences(a, middle, high);
//place pivot at position high -1
swapReferences(a, middle, high-1);
AnyType pivot = a[high -1];
//begin partitioning
int i, j;
for(i = low, j = high; ;)
{
while(a[++i].compareTo(pivot)<0)
;
while(pivot.compareTo(a[--j])<0)
;
if(i>-j)
break;
swapReferences(a, i , j);
}
swapReferences(a, i , high-1);
quickSort(a, low, i-1); //sort small elements
quickSort(a, i+1, high); //sort large elements
}
}
public static final <AnyType> void swapReferences(AnyType []a, int i, int j)
{
AnyType tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
private static <AnyType extends Comparable<? super AnyType>> void insertionQuickSort(AnyType[]a, int low, int high)
{
for(int p = low+1; p <=high; p++)
{
AnyType tmp = a[p];
int j;
for( j = p; j > low && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
{
a[j] = a[j - 1];
a[j] = tmp;
}
}
}
Explanation / Answer
Java Program:
import java.util.Scanner;
class SortingArrays
{
/* ShellSort Method */
public static void ShellSort(int arr[])
{
int len = arr.length;
int step, i, j, tempVal;
// Process starts with a larger step and goes on decreasing it
for (step = len/2; step > 0; step = step / 2)
{
//Sorting array
for (i = step; i < len; i = i + 1)
{
// Consider the value present at position i
tempVal = arr[i];
// Shifting elements
for (j = i; j >= step && arr[j - step] > tempVal; j = j - step)
{
arr[j] = arr[j - step];
}
// Placing element at position j
arr[j] = tempVal;
}
}
}
/* Insertion Sort */
public static void InsertionSort(int[] arr)
{
int tempVal, i, j;
//Iterating over array
for (i = 1; i < arr.length; i++)
{
//Searching remaining array
for(j = i ; j > 0 ; j--)
{
//Comparing elements
if(arr[j] < arr[j-1])
{
//Swapping elements
tempVal = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tempVal;
}
}
}
}
/* Quick Sort */
public static void QuickSort(int arr[], int low, int high)
{
if (low < high)
{
// Finding position to partition
int pos = partition(arr, low, high);
// Recursive calls
QuickSort(arr, low, pos-1);
QuickSort(arr, pos+1, high);
}
}
//Partitioning Array
public static int partition(int arr[], int low, int high)
{
int temp, i, j, pivot;
//Finding Ppivot element
pivot = arr[high];
//Storing lowest index
i = (low-1);
//Iterating over array
for (j=low; j<=high-1; j++)
{
// Searching for elements smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++;
// Swapping elements
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swapping elements
temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
//Returning position
return i+1;
}
//Main method
public static void main(String args[])
{
int sortType;
int size, i, j, k;
//Scanner class object
Scanner reader = new Scanner(System.in);
//Prompting user for selection of sorting method
System.out.print(" Selection Sorting Method 1 - Shell Sort 2 - Insertion Sort 3 - Quick Sort Your option: ");
//Reading sorting type
sortType = reader.nextInt();
//Reading size
System.out.print(" Enter the number of integers: ");
size = reader.nextInt();
//Declaring array
int[] array = new int[size];
//Reading data
System.out.print(" Enter the " + size + " integers:: ");
//Reading array
for(i=0; i<size; i++)
{
array[i] = reader.nextInt();
}
//Sorting array
switch(sortType)
{
//Calling appropriate function
case 1: ShellSort(array); break;
case 2: InsertionSort(array); break;
case 3: QuickSort(array, 0, array.length - 1); break;
}
int n = size, p = 0;
//Array to hold duplicates
int[] duplicates = new int[size];
//Iterating over array
for(i=0; i < n; i++)
{
//Iterating over remaining elements
for(j=i+1; j < n; )
{
//Comparing elements
if(array[j] == array[i])
{
//Storing duplicates
if( (p == 0 && duplicates[p] != array[j]) || (p > 0 && duplicates[p-1] != array[j]) )
{
duplicates[p] = array[i];
p++;
}
//Adjusting Array
for(k=j; k<n-1; k++)
{
array[k] = array[k+1];
}
n--;
}
else
{
//Move to next element
j++;
}
}
}
//Reading data
System.out.print(" Resulting array is: ");
//Reading array
for(i=0; i<n; i++)
{
//Storing value
System.out.print(" " + array[i]);
}
//Reading data
System.out.print(" Duplicate Elements: ");
//Reading array
for(i=0; i<p; i++)
{
//Storing value
System.out.print(" " + duplicates[i]);
}
System.out.print(" ");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.