4. Given the array 17 25 2 4 13 60 47 26 24 15] 17 [8] [2] 3 [4] tell which sort
ID: 3868538 • Letter: 4
Question
4. Given the array 17 25 2 4 13 60 47 26 24 15] 17 [8] [2] 3 [4] tell which sorting algorithm would produce the following results after four iterations 24 24 25 47 60 13 17 26 a.1 24 24 60 47 26 13 17 25 L2] 13] 14] 16] 26 25 24 13 60 47 C. 3 17 2 4 5. How many comparisons would be needed to sort an array containing 100 elements using ShortBubble a. in the worst case? b. in the best case? 6. A sorting function is called to sort a list of 100 integers that have been read from a file. If all 100 values are zero, what would the execution requirements (in terms of Big-O notation) be if the sort used was a. Quicksort, with the first element used as the split value? b. ShortBubble C. Selectionsort? d. HeapSort? e. InsertionSort? f. Mergesort?Explanation / Answer
4 a. Selection sort
b. Quick Sort
c. Bubble sort
5. Ans a. In the best case, the array is already sorted, and the bubble sort terminates after the first pass of n 1 comparisons. So if n = 100, there are 99 comparisons in the best case.
Ans b. The body of the loop executes in bubble sort is (n 1) + (n 2) + · · · + 2 + 1 = n(n 1) /2 where n=100. Then the result is considered as 100*99/2 =4950 comparisons in Worst case.
6. Answer
Name
Average
Worst
Memory
Stable
Method
Bubble sort
O(n2)
O(n2)
O(1)
Yes
Exchanging
Selection sort
O(n2)
O(n2)
O(1)
No
Selection
Insertion sort
O(n2)
O(n2)
O(1)
Yes
Insertion
Merge sort
O(n log n)
O(n log n)
O(n)
Yes
Merging
Quicksort
O(n log n)
O(n2)
O(1)
No
Partitioning
Heapsort
O(n log n)
O(n log n)
O(1)
No
Selection
7. Answer
4950 where selection sort best case O(n2 ). So the right answer is c
8. Ans D
9 Ans. Follow the order
Algorithms
Best
Average
Worst
Quick Sort
(n log(n))
(n log(n))
O(n^2)
Heap Sort
(n log(n))
(n log(n))
O(n log(n))
Merge Sort
(n log(n))
(n log(n))
O(n log(n))
Insertion Sort
(n)
(n^2)
O(n^2)
Bubble Sort
(n)
(n^2)
O(n^2)
Selection Sort
(n^2)
(n^2)
O(n^2)
.
Name
Average
Worst
Memory
Stable
Method
Bubble sort
O(n2)
O(n2)
O(1)
Yes
Exchanging
Selection sort
O(n2)
O(n2)
O(1)
No
Selection
Insertion sort
O(n2)
O(n2)
O(1)
Yes
Insertion
Merge sort
O(n log n)
O(n log n)
O(n)
Yes
Merging
Quicksort
O(n log n)
O(n2)
O(1)
No
Partitioning
Heapsort
O(n log n)
O(n log n)
O(1)
No
Selection
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.