We have an array of objects we want to sort. Each object contains a key and data. The key is an int, and the data is a char. Assume this is stored as a class with two data fields. But I will represent an object in this homework as if the int and char were concatenated. In other words, if the int is 2 and the char is 'A', I will write it as 2A. The particular array we want to sort is represented as follows. 2A 4V 2B 1T 2C 0S 2D 3U Important: When we sort this array, we compare two objects only by the key. The data is completely ignored. For example, 2A and 2B are equal. We will sort this function using various methods. But we will stop the sort in the before it is finished. You need to tell me what the array looks like when the sort is stopped, for all the following cases: 1. Selection Sort: Stop after you have gone through the outer loop 4 times. 2. Insertion Sort: Stop after you have gone through the outer loop 4 times. 3. Shell Sort: Stop after the first time through the outer for loop. 4. Merge Sort: Stop after the first recursion is finished in the initial call to mSort. 5. Merge Sort Bottom Up: Stop after the first time through the outer for loop. 6. Natural Merge Sort: Stop after the first time through the outer for loop. 7. Quick Sort: Stop after the first recursion is finished in the initial call to quickSort. 8. Quick Sort with 3 way partitioning: Stop after the first recursion is finished in the initial call to quickSort3. What to submit: You can copy the following 7 lines, and permute the objects so they are in the correct order. Insertion: 2A 4V 2B 1T 2C 0S 2D 3U Selection: 2A 4V 2B 1T 2C 0S 2D 3U Shell: 2A 4V 2B 1T 2C 0S 2D 3U Merge: 2A 4V 2B 1T 2C 0S 2D 3U MergeBU: 2A 4V 2B 1T 2C 0S 2D 3U Natural: 2A 4V 2B 1T 2C 0S 2D 3U Quick: 2A 4V 2B 1T 2C 0S 2D 3U Quick3: 2A 4V 2B 1T 2C 0S 2D 3U
We have an array of objects we want to sort. Each object contains a key and data. The key is an int, and the data is a char. Assume this is stored as a class with two data fields. But I will represent an object in this homework as if the int and char were concatenated. In other words, if the int is 2 and the char is 'A', I will write it as 2A. The particular array we want to sort is represented as follows.
2A 4V 2B 1T 2C 0S 2D 3U
Important: When we sort this array, we compare two objects only by the key. The data is completely ignored. For example, 2A and 2B are equal.
We will sort this function using various methods. But we will stop the sort in the before it is finished. You need to tell me what the array looks like when the sort is stopped, for all the following cases:
1. Selection Sort: Stop after you have gone through the outer loop 4 times.
2. Insertion Sort: Stop after you have gone through the outer loop 4 times.
3. Shell Sort: Stop after the first time through the outer for loop.
4. Merge Sort: Stop after the first recursion is finished in the initial call to mSort.
5. Merge Sort Bottom Up: Stop after the first time through the outer for loop.
6. Natural Merge Sort: Stop after the first time through the outer for loop.
7. Quick Sort: Stop after the first recursion is finished in the initial call to quickSort.
8. Quick Sort with 3 way partitioning: Stop after the first recursion is finished in the initial call to quickSort3.
What to submit:
You can copy the following 7 lines, and permute the objects so they are in the correct order.
Insertion: 2A 4V 2B 1T 2C 0S 2D 3U
Selection: 2A 4V 2B 1T 2C 0S 2D 3U
Shell: 2A 4V 2B 1T 2C 0S 2D 3U
Merge: 2A 4V 2B 1T 2C 0S 2D 3U
MergeBU: 2A 4V 2B 1T 2C 0S 2D 3U
Natural: 2A 4V 2B 1T 2C 0S 2D 3U
Quick: 2A 4V 2B 1T 2C 0S 2D 3U
Quick3: 2A 4V 2B 1T 2C 0S 2D 3U
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
