Question

4. (7 pts) Let A be an array of 5 integers, whose contents are as follows: 3, 2, 1, 5, 4. We will apply insertion sort to sort this array. Show all of the element-wise comparisons made by the algorithm in the correct order. Here an element-wise comparison means the comparison of one element of the array with another element of the array or the key set in a particular step of the algorithm. Since the algorithm may move the elements of the array, you need to show the values of the elements being compared (rather than the form of A[U). The first element-wise comparison isel 3 > 2? You should start with this element-wise comparison to write out all element-wise comparisons, one comparison per row. 5. (7 pts) Let A be an array be an array of 5 integers, whose contents are as follows: 3, 2, 1, 5,4 We will apply quick sort to sort this array. Show all of the element-wise comparisons made by the algorithm in the correct order. Here an element-wise comparison means the comparison of one element of the array with another element of the array or the key set in a particular step of the algorithm. Since the algorithm may move the elements of the array, you need to show the values of the elements being compared (rather than the form of A[U). The first element-wise comparison isel 3 5 42 You should start with this element-wise comparison to write out all element-wise comparisons, one comparison per row.'

Answer 1

package Sort;

// Defines a class to perform insertion and quicksort

public class InsertionQuickStep

{

// Method for insertion sort

public static void insertionSort(int array[])

{

//Stores the length of array

int len = array.length;

//Loops till length minus one times

for (int c = 1; c < len; ++c)

{

//Stores i index position value as key value

int key = array[c];

int d = c - 1;   

  

// Move elements of array[0..i-1], that are greater than key, to one position ahead of their current position

while (d >= 0 && array[d] > key)

{

System.out.println(array[d] + " > " + key);

// Swaps each element of the array one position to right  

array[d + 1] = array[d];

d = d - 1;

}//End of while

//Insert the key value at d plus one position

array[d+1] = key;

}//End of for

}//End of method

  

// Recursive method to apply quick sort

static void Quicksort(int[] A, int p, int r)

{

// Checks if left is less than right

if (p < r)

{

// Partition to find the "right place" for the leftmost element.

int q = Partition (A, p, r);

// Recurse on the left side:

Quicksort(A, p, q - 1);

// Recurse on the right side:

Quicksort(A, q + 1, r);

}// End of if condition

}// End of method

// Method to perform partition

static int Partition (int[] array, int p, int r)

{

// Stores the right index position of the array data as partition element

int x = array[r];

// Stores the start -1

int i = p - 1;

  

// Loops till right is greater than or equals to left

for (int j = p; j <= r - 1; j++)

{

System.out.println(array[j] + " > " + x);

// Checks if current index position of the array is less than or equals to x value

if (array[j] <= x)

{

// Switch with swap position

i++;

// Calls the method to swap i index position with j index position

swap (array, i, j);

// Shift swap position rightwards:

}// End of if condition

}// End of for loop

// Calls the method to swap i+1 index position with r (last) index position

swap (array, i + 1, r);

// Returns i value added to one for next position

return i + 1;

}// End of method

  

// Method to swap

static void swap (int[] array, int i, int j)

{

int temp = array[i];

array[i] = array[j];

array[j] = temp;

}// End of method

  

// Method to display array contents

static void show(int A[])

{

// Loops till length of the array

for(int x = 0; x < A.length; x++)

// Displays each element

System.out.printf("%4d", A[x]);

}// End of method

  

// main function definition

public static void main(String pyari[])

{

// Creates an array

int arrayIns[] = {23, 45, 10, 2, 89, 62, 76, 33};

int arrayQui[] = {23, 45, 10, 2, 89, 62, 76, 33};

System.out.println("\n ********* Before Insertion Sort ********* ");

show(arrayIns);

System.out.println("\n ********* Comparison of Insertion Sort ********* ");

// Calls the method to perform insertion sort

insertionSort(arrayIns);

System.out.println("\n ********* After Insertion Sort ********* ");

show(arrayIns);

System.out.println("\n\n ********* Before Quick Sort ********* ");

show(arrayQui);

System.out.println("\n ********* Comparison of Quick Sort ********* ");

// Calls the method to perform sorting

Quicksort(arrayQui, 0, arrayQui.length-1);

System.out.println("\n ********* After Quick Sort ********* ");

show(arrayQui);

}// End of main

}// End of class

Sample Output:

********* Before Insertion Sort *********
23 45 10 2 89 62 76 33
********* Comparison of Insertion Sort *********
45 > 10
23 > 10
45 > 2
23 > 2
10 > 2
89 > 62
89 > 76
89 > 33
76 > 33
62 > 33
45 > 33

********* After Insertion Sort *********
2 10 23 33 45 62 76 89

********* Before Quick Sort *********
23 45 10 2 89 62 76 33
********* Comparison of Quick Sort *********
23 > 33
45 > 33
10 > 33
2 > 33
89 > 33
62 > 33
76 > 33
23 > 2
10 > 2
10 > 23
89 > 45
62 > 45
76 > 45
62 > 89
76 > 89
62 > 76

********* After Quick Sort *********
2 10 23 33 45 62 76 89