MadeEasy Test Series: Programming & DS - Sorting

Question

An array A of size n is known to be sorted except for the first k elements and the last k elements, where k is a constant. Which of the following algorithms will be the best choice for sorting the array A?

a-Insertion Sort

b-Bubble sort

c-Quicksort

d-Selection sort

Comments

Selection sort?

---

Yes i did thought the same. But answer given is Insertion sort

---

Whats the explanation given

---

It said if the array is already sorted then insertion sort is the best choice.

But how come the array is sorted? The last and first elements arden't sorted right..

---

And selection sort will sort with the least number of swaps isn't it

---

yes.

---

Strength of a sorting algorithm is not only on the number of swaps but comparisons ,

in search of maximum or minimum , the selection sort will be making searches thus we cannot escape the O(n) complexity of comparisons , but with insertion sort , the number of comparisons would be just constant .

Correct me if i am wrong.

---

How the complexity would be constant in terms of insertion sort? We still need comparison of entire array elements since k starting and end elements aren't sorted. According to me in that case the compkexity would rise up to O(n^2). Right ?

---

After a thought . Yes , you're correct . Basically it would depend upon the nature of the sorted and unsorted array , still in worst case it will be n^2 , i overlooked that case.

---

@Shaik Masthan @MiNiPanda

what should be the correct answer?

---

There are many parameters that decide whether a sorting algorithm is efficient or not but none of them can satisfy all the criteria at the same time. We generally center around the space and time complexity but there are other parameters as well.

We take operations like swapping, comparisons as constant time taking operations. But computational complexity is also one factor that shouldn't be ignored. Such operations come under this complexity.

Here in the worst case (k=0 or 1), insertion sort will be taking O(n^2) but recall what happens in insertion sort :

void insertionSort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       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 && arr[j] > key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   } 
} 

We shift the elements towards right in order to sort (arr[j+1]=arr[j]). This isn't called swapping. It may be termed as "movements".

In other sorting algo, we swap 2 elements where we need to do assignments for 3 times to swap using temporary variables during each iteration.

Whereas here only 1 time assignment is done per iteration.

In average case when the array is nearly sorted, the no. of movements vs no. of swappings make a significant difference.

Though asymptotic time complexity doesn't vary but computational complexity does.

I summarized the knowledge I had on it. Open to suggestions and additions :)

---

In almost sorted or sorted array number of swap and no. of comparison will almost be O(n), whereas in case of selection sort only no. of swaps will be less but comparison will still be O(n^2). That's why selection sort has O(n^2) in all cases. Whereas Insertion Sort best case is O(n).