70.8k views
2 votes
Assume the existence of an UNSORTED ARRAY of n characters. You are to trace the CS111Sort algorithm (as described here) to reorder the elements of a given array. The CS111Sort algorithm is an algorithm that combines the SelectionSort and the InsertionSort following the steps below: 1. Implement the SelectionSort Algorithm on the entire array for as many iterations as it takes to sort the array only to the point of ordering the elements so that the last n/2 elements are sorted in increasing (ascending) order. 2. Implement the InsertionSort Algorithm to sort the first half of the resulting array elements so that these elements are sorted in decreasing (descending) order.

1 Answer

6 votes

Answer:

class Main {

public static void main(String[] args) {

char arr[] = {'T','E','D','R','W','B','S','V','A'};

int n = arr.length;

System.out.println("Selection Sort:");

System.out.println("Iteration\tArray\tComparisons");

long comp1 = selectionSort(arr);

System.out.println("Total comparisons: "+comp1);

System.out.println("\\Insertion Sort:");

System.out.println("Iteration\tArray\tComparisons");

long comp2 = insertionSort(arr);

System.out.println("Total Comparisons: "+comp2);

System.out.println("\\Overall Total Comparisons: "+(comp1+comp2));

}

static long selectionSort(char arr[]) {

// applies selection sort for n/2 elements

// returns number of comparisons

int n = arr.length;

long comparisons = 0;

// One by one move boundary of unsorted subarray

for (int i = n-1; i>=n-n/2; i--) {

// Find the minimum element in unsorted array

int max_idx = i;

for (int j = i-1; j>=0; j--) {

// there is a comparison everytime this loop returns

comparisons++;

if (arr[j] > arr[max_idx])

max_idx = j;

}

// Swap the found minimum element with the first

// element

char temp = arr[max_idx];

arr[max_idx] = arr[i];

arr[i] = temp;

System.out.print(n-1-i+"\t");

printArray(arr);

System.out.println("\t"+comparisons);

}

return comparisons;

}

static long insertionSort(char arr[]) {

// applies insertion sort for n/2 elements

// returns number of comparisons

int n = arr.length;

n = n-n/2; // sort only the first n/2 elements

long comparisons = 0;

for (int i = 1; i < n; ++i) {

char 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) {

// there is a comparison everytime this loop runs

comparisons++;

if (arr[j] > key) {

arr[j + 1] = arr[j];

} else {

break;

}

j--;

}

arr[j + 1] = key;

System.out.print(i-1+"\t");

printArray(arr);

System.out.println("\t"+comparisons);

}

return comparisons;

}

static void printArray(char arr[]) {

for (int i=0; i<arr.length; i++)

System.out.print(arr[i]+" ");

}

}

Step-by-step explanation:

Explanation is in the answer.

User Justinxreese
by
7.0k points