Can you please first answer part b, c and e first. Assume you have a sorted list
ID: 3897290 • Letter: C
Question
Can you please first answer part b, c and e first.
Assume you have a sorted list of n >= 3 distinct values in which exactly two different
elements have been interchanged. For each of the following justify your answer.
(b) Assume that the elements in positions i and j were interchanged, where i < j. Derive a
general formula for the number of comparisons as a function of i and/or j and/or n. (It
should not be a function of only n.)
(c) How many comparisons does your algorithm use in the best case?
(e) How many comparisons does your algorithm use in the average case?
How many comparisons does your algorithm used in the worst case?
Give an algorithm that minimizes the average number of compar-
isons, and analyze it.
Explanation / Answer
Hello there!
As per the question, the input list is already sorted and two elements in the lists are swapped.
Our main task is to chose the algorithm which makes very less comparison
Sorting algorithms which must strike when you come over to this question is :
1. Selection Sort : Basic sorting algorithm but the best case comparison among elements when the array is sorted is O(n^2).
2. Insertion Sort : Best suited for sorted arrays. Worst case complexity is O(n^2). But if the array is sorted only O(n) comparison.
3. Merge Sort : Average case and worst case complexity is O(nlogn). Even if the array is sorted.
4. Quick Sort : If the array is sorted the worst case can go upto O(n^2). But the average case is O(nlogn).
Now, from the above mentioned algorithm. We will not chose selection sort because its complexity is same for all the cases. Similarily merge sort has O(nlogn) for sorted arrays and Quick Sort has O(n^2).
We will chose Insertion Sort.
Here goes the algorithm.
(c) In the best case, algorithm will use O(n) time complexity. And, it will use n number of comparison also.
(e) In the average and the worst case it will use O(n^2) time complexity. Now coming over to the time complexity for worst case and average case.
For worst case, consider list is in reverse sorted order. Now consider, the average length of the sorted list is 1/2*(N). So, (1/2)*N is sorted. Now the number of comparison it will make will be N-1.
So the total number of comparison becomes. (1/2)*(N)*(N-1).
For average case, We will end up examining only the half of list. So, the avg length will be 1/2*1/2*N
The total number of comparison becomes (1/4)*(N)*(N-1)
Consider the following test case -
50, 40, 30, 20, 10
10 will check with 50,40,30,20
20 will check with 50,40,30
30 will check with 50,40
40 will check with 50
Comparison made will be 10
1/2*5*(5-1) = 10. Hence proved!
Please, message if you've any doubt.
Happy chegging!
Edited :
Consider an example.
5, 6, 7, 8, 9, 10 is our sorted array. Now according to the question we need to perform the best, average and worst case complexity.
What will be the best case?
When the elements which are swapped are adjacent.
So, 5,6,8,7,9,10
Total number of comparison in sorted array in Insertion sort is N. Now we will be swapping the element. So, it will be 7 for this case.
For the worst case. The swapped element must be at extreme positions.
So, 10,6,7,8,9,5
Total number of comparison will be 15.
After looking through these test cases. We can derive a formula for number of comparisons.
Total number of comparisons(n) = (N-1) + 2 * ( j - i )
Now, for best case = (6-1) + 2*(3-2) = 7.
Now, for worst case = (6-1) + 2*(5-0) = 15.
Thank you. If you have any doubt please comment again.