412 views
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

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).