In Java Implement the insertion sort and the Shell sort so that they count the n

Question

In Java

Implement the insertion sort and the Shell sort so that they count the number of comparisons made during a sort. Use your implementations to compare the two sorts on arrays of random Integer objects of various sizes. Also, compare the Shell sort as implemented in Segment 8.23 with a revised Shell sort that adds 1 to space any time it is even. For what array size does the difference in the number of comparisons become significant? Is the size consistent with the size predicted by the algorithm’s Big Oh?

Implement and exercise the algorithm to verify its functionality. Be sure to test with multiple values to insure its correct implementation.

Explanation / Answer

Ans.)

Insertion Sort:

class InsertionSort
{
int count=0;
/*Function to sort array using insertion sort*/
void 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)
{
count++;
arr[j+1] = arr[j];
j = j-1;
}
count++;
arr[j+1] = key;
}
System.out.println("Number of comparisons made: "+count);
}
/* A method to print array of size n*/
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Main method
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6};
InsertionSort ob = new InsertionSort();
ob.sort(arr);
printArray(arr);
}
}

Output:

Shell Sort:

class ShellSort
{
/* An utility function to print array of size n*/
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
/* function to sort arr using shellSort */
int sort(int arr[])
{
int n = arr.length;
int count=0;
for (int gap = n/2; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i += 1)
{
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){
count++;
arr[j] = arr[j - gap];
}
// put temp into arr[j]
arr[j] = temp;
}
count++;
}
System.out.println("Number of comparisons made: "+count);
return 0;
}
// Main method
public static void main(String args[])
{
int arr[] = {12, 34, 54, 2, 3};
ShellSort ob = new ShellSort();
ob.sort(arr);
System.out.println("Sorted Array :");
printArray(arr);
}
}

Output:

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.