1.Workout the following sorting algorithms for the following array. Clearly show
ID: 3553980 • Letter: 1
Question
1.Workout the following sorting algorithms for the following array. Clearly show array and other
variables at each step.
A={22, 91, 24, 78, 6, 89, , 98, 99}
a) Selection sort
b) Merge sort
c) Quicksort
2. Analyzing sorting algorithm for time and space complexity
a) What is the time complexity of an algorithm?
b) What is space complexity of an algorithm?
c) Suppose you take a size n array (assume that n = 2m), and start dividing the array into halves
until you have one element in the bottom level. Show that the height of the tree structure
created by the above process has the height m and m=log (n).
d) Compare and contrast above three sorting algorithm based on time and space complexity.
Consider the best-case, worst-case, and average case scenarios.
Explanation / Answer
1. 22, 91, 24, 78, 6, 89, 98, 99
a) Selection sort
Select the minimum, place it in 1st unsorted position.
temp = position 0 = 22 .
Scan array from temp to last for minimum number.
min = 6
Swap temp and min
Array = 6, 91, 24, 78, 22, 89, 98, 99
Increase temp. temp = position 1 = 91.
Scan array from temp to end. Find minimum.
min = 22.
Swap temp and min.
array = 6, 22, 24, 78, 91, 89, 98, 99
Approching like this.
Array = 6, 22, 24, 78, 91, 89, 98, 99 . temp = position 2. ( 0 index )
6, 22, 24, 78, 91, 89, 98, 99 . temp = position 3.
6, 22, 24, 78, 89, 91, 98, 99 . temp = position 4.
6, 22, 24, 78, 89, 91, 98, 99 . temp = position 5.
6, 22, 24, 78, 89, 91, 98, 99 . temp = position 6.
b) Merge sort. ( Divide and conquer )
Merge sort ( 22, 91, 24, 78, 6, 89, 98, 99 )
Divides array into two. Merge sort ( 22, 91, 24, 78 ) Merge sort ( 6, 89, 98, 99 ) And then merges the sorted arrays into 1.The divided array are further divided.
sort ( 22, 91, 24, 78, 6, 89, 98, 99 )
/
sort ( 22, 91, 24, 78 ) sort ( 6, 89, 98, 99 )
/ /
sort ( 22, 91 ) sort ( 24, 78 ) sort ( 6, 89 ) sort ( 98, 99 )
sort ( 22, 91 ) arranges the numbers in ascending order by comparing the numbers.
So does all sort with array size of two.
Now merge ( sort ( 22, 91 ) , sort ( 24 , 78 ) )
temp1 = 22. temp2 = 24.
answer array = {}.
answer array takes minimum of two = 22
temp1++.
temp1 = 91, temp2 = 24.
answer array takes minimum of two = 22, 24
temp2++.
temp1 = 91, temp2 = 78.
answer array takes minimum of two = 22, 24, 78
temp2++.
now temp2 has reached the end. So simply temp1 is copied.
Answer array ( merged array ) = 22, 24, 78, 91
Similarly merged array of merge ( sort ( 6, 89) , sort ( 98 , 99 ) ) = 6, 89, 98, 99.
Now merge ( { 22, 24, 78, 91 } , { 6, 89, 98, 99 } ).
temp1 = 22. temp2 = 6.
answer array = {}.
answer array takes minimum of two = 6
temp2++.
temp1 = 22, temp2 = 89.
answer array takes minimum of two = 6, 22
temp1++.
temp1 = 24, temp2 = 89.
answer array takes minimum of two = 6, 22, 24
temp1++.
temp1 = 78, temp2 = 89.
answer array takes minimum of two = 6, 22, 24, 78
temp1++
temp1 = 91, temp2 = 89.
answer array takes minimum of two = 6, 22, 24, 78, 89
temp2++.
temp1 = 91, temp2 = 98.
answer array takes minimum of two = 6, 22, 24, 78, 89, 91
temp1++.
now temp1 has reached the end. So simply temp2 is copied.
answer array = 6, 22, 24, 78, 89, 91, 98, 99
c ) Quick sort
Take 1st element as the pivot. Move it to the position where it will be in sorted array at last.
( All elemnents before it are smaller than it, All elements after it are greater )
recursively sort the left and right half of the array.
sort ( 22, 91, 24, 78, 6, 89, 98, 99 ). pivot = 22
Move 22 to its position.
array = { 6, 22, 91, 24, 78, 89, 98, 99 }
sort ( 6 ) , sort ( 91, 24, 78, 89, 98, 99 )
sort ( 6 ) is sorted as 1 element in array.
sort ( 91, 24, 78, 89, 98, 99 ). pivot = 91.
Move 91 to its position.
array = { 6, 22, 24, 78, 89, 91, 98, 99 }
sort ( 24, 78, 89 ) sort ( 98, 99 ).
And so on.
2.
a ) The number of (machine) instructions which a program executes during its running time is called its time complexity in computer science. This number depends primarily on the size of the program's input, that is approximately on the number of the strings to be sorted (and their length) and the algorithm used.
So approximately, the time complexity of the program
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.