In-class/Lab – Sort and Search for Comparables Complete the following sorting an
ID: 3797768 • Letter: I
Question
In-class/Lab – Sort and Search for Comparables
Complete the following sorting and searching methods for type Comparable:
// Selection sort for an array of Comparables _______________
public static void selectionSort(Comparable[] array)
{
int current, indexSmallest, posToFill;
Comparable temp;
for (posToFill=0; posToFill < array.length - 1; posToFill++)
{
for ( {
if ( {
}} // end for
} // end for }
// Initialize smallest
) // Set up ‘for loop’
) // Look for smallest value
// Get new smallest index
// Perform 3-way swap
// Insertion sort for an array of Comparables_______________
public static void insertionSort(Comparable[] array)
{
}
// Linear search for an array of Comparables _______________
public static void linearSearch(Comparable[] array)
{
}
Explanation / Answer
public class SelectionSortEx
{
public static void main(String a[])
{
//Numbers which are to be sorted
int n[] = {55,33,22,88,99,44,11,77,66};
//Displays the numbers before sorting
System.out.print("Before sorting, numbers are ");
for(int i = 0; i < n.length; i++)
{
System.out.print(n[i]+" ");
}
System.out.println();
insertionSort(n);
//Displaying the numbers after sorting
System.out.print("After sorting, numbers are for insertion sort ");
for(int i = 0; i < n.length; i++)
{
System.out.print(n[i]+" ");
}
initializeselectionSort(n);
System.out.print("After sorting, numbers are for selection sort ");
for(int i = 0; i < n.length; i++)
{
System.out.print(n[i]+" ");
}
}
//This method sorts the input array in descending order
public static void initializeselectionSort( int n[])
{
int i,j,first,temp;
for (i=n.length-1;i >0; i--)
{
first=0; //initialize to subscript of first element
for(j=1;j<=i;j++) //locate smallest element between 1 and i.
{
if(n[j]<n[first])
first=j;
}
temp=n[first]; //swap the smallest found in position i.
n[first]=n[i];
n[i] = temp;
}
}
public static void insertionSort(int n[])
{
for (int i = 1; i < n.length; i++)
{
int current = n[i];
int j = i;
while (j > 0 && n[j - 1] > current)
{ // move
n[j] = n[j - 1];
j--;
} // found the right place, insert now
n[j] = current;
}
}
}
o/p:
Before sorting, numbers are 55 33 22 88 99 44 11 77 66
After sorting, numbers are for insertion sort 11 22 33 44 55 66 77 88 99 After sorting, numbers are for selection sort 99 88 77 66 55 44 33 22 11