import java.util.*;
public class Main
{
public static void main(String[] args) {
int n, howmany;
int whichsort = 0;
int whatnum = 0;
System.out.println(“Hello let’s fill it up! How many numbers? “);
Scanner sc= new Scanner(System.in);
howmany = sc.nextInt();
int array[] = new int[howmany];
int array2[] = new int[howmany];
array = filluparray (array);
System.out.println(“\nWhat sort method? 1 – bubble, 2 – selection, 3 – insertion “);
whichsort = sc.nextInt();
n = array.length;
if (whichsort == 1)
array = sortarray (array, n);
else if (whichsort == 2)
array = sortarray_select (array, n);
else if (whichsort == 3)
array = sortarray_insert (array, n);
array2 = array_remove_dub (array, array2, n);
System.out.println(“\nWhat number do you want to look for? “);
whatnum = sc.nextInt();
sSearch (array2, whatnum);
}
static int[] filluparray (int array[])
{
int a,i;
Scanner sc2= new Scanner(System.in);
// Adding elements in the array
for (i = 0; i < array.length; i++)
{
System.out.print(“Please enter a random number: “);
a = sc2.nextInt();
array[i] = a;
}
// Printing the elements for verification purpose only
for (i = 0; i < array.length; i++)
{
System.out.print(array[i] + ” “);
}
return array;
}
static int[] sortarray (int array[], int n)
{
//Bubble sort
int temp = 0;
int i,j;
for(i=0; i<n;i++) {
System.out.print(“Pass “);
System.out.print(i+1);
System.out.print(” – “);
for(j=1; j < (n-i);j++){
if(array[j-1] > array[j]){
//swap elements
temp=array[j-1];
array[j-1] =array[j];
array[j]=temp;
}
}
}
System.out.println(“\nSorted result – BUBBLE “);
for(i=0; i<n;i++)
{
System.out.print(i);
System.out.print(“->”);
System.out.print(array[i]);
System.out.print(” – “);
}
return array;
}
static int[] sortarray_select (int array[], int n)
{
int i, j, smallerNumber;
//Selection sort
for (i =0 ; i < n – 1; i++)
{
int index = i;
for(j = i + 1; j< array.length;j++){
if (array[j] < array[index]){
index = j;//searching for lowest index
}
}
smallerNumber=array[index];
array[index]=array[i];
array[i]=smallerNumber;
}
System.out.println(“\nSorted result – SELECT “);
for(i=0; i< n; i++)
{
System.out.print(i);
System.out.print(“->”);
System.out.print(array[i]);
System.out.print(” – “);
}
return array;
}
static int[] sortarray_insert (int array[], int n)
{
{
int i, j, temp;
for (i=1;i<n; i++){
temp = array[i];
j = i – 1;
while(j>=0 && temp <= array[j])
{
array[j+1] =array[j];
j = j-1;
}
array[j+ 1] = temp;
}
}
return array;
}
static int[] array_remove_dub (int array[], int array2[], int n)
{
int i, i2, i3 ;
System.out.println(“\nDuplicates removal – “);
i2 = 0;
for(i=0; i< n; i++)
{
if (array[i] != -999) // for identifying duplicated values
{
array2[i2] = array[i];
i2 = i2 + 1;
if ((i+1) < n)
for (i3 = i; i3 < n; i3++)
if ((i3+1) < n)
if (array [i] == array [i3+1])
{
array[i3+1] = -999;
}
}
}
n = array2.length;
for(i2=0; i2 < n; i2++)
System.out.println(array2[i2]);
return array2;
}
static void bSearch(int array[], int key){
int first = 0;
int n = array.length;
int i;
// look for the last non-zero number
for (i = 0; i < n; i++ )
{
if (array[i] == 0)
break;
}
int last = i-1; // last non-zero value found
int mid =(first+last)/2;
while(first<=last){
if(array[mid]<key){
first=mid+1;
} else if (array[mid]==key){
System.out.println(“It is found at index: “+ mid + ” meaning the ” + (mid+1) + ” th array element.”);
break;
}
else {
last=mid-1;
}
mid=(first+last)/2;
}
if(first>last){
System.out.println(“Sorry not found!”);
}
}
static void sSearch(int array[], int key){
int n = array.length;
int i;
boolean found = false;
// just search one by one
for (i = 0; i < n; i++ )
{
if (array[i] == key) {
System.out.println(“It is found at index: “+ i + ” meaning the ” + (i+1) + ” th array element.”);
found = true;
}
}
if(!found){
System.out.println(“Sorry not found!”);
}
}
}
//////////////////////////////////////
// This version of binary search includes function to show the number of miss
static void bSearch(int array[], int key)
{
int first = 0;
int n = array.length;
int i;
int miss = 0; // this variable is for tracking the number of comparisons
// look for the last non-zero number
for (i = 0; i < n; i++ )
{
if (array[i] == 0)
break;
}
int last = i-1; // last non-zero value found
int mid =(first+last)/2;
while(first<=last){
if(array[mid]<key){
first=mid+1;
miss = miss + 1;
} else if (array[mid]==key){
System.out.println(“It is found at index: “+ mid + ” meaning the ” + (mid+1) + “th array element.”);
System.out.println(“We have gone through ” + miss + ” rounds of comparison before reaching this…”);
break;
}
else {
last=mid-1;
}
mid=(first+last)/2;
}
if(first>last){
System.out.println(“Sorry not foundeven after ” + miss + “rounds of comparison.”);
}
}