edited by
3,392 views
30 votes
30 votes

An array $A$ contains $n$ integers. We wish to sort $A$ in ascending order. We are told that initially no element of $A$ is more than a distance $k$ away from its final position in the sorted list. Assume that $n$ and $k$ are large and $k$ is much smaller than $n$. Which of the following is true for the worst case complexity of sorting $A$?

  1. $A$ can be sorted with constant $\cdot kn$ comparison but not with fewer comparisons.
  2. $A$ cannot be sorted with less than constant $\cdot n \log n$ comparisons.
  3. $A$ can be sorted with constant $\cdot n$ comparisons.
  4. $A$ can be sorted with constant $\cdot n \log k$ comparisons but not with fewer comparisons.
  5. $A$ can be sorted with constant $\cdot k^{2}n$ comparisons but not fewer.
edited by

4 Answers

Best answer
20 votes
20 votes

Let Array element be $\{4,3,2,1,7,5,6,9,10,8\}$ and $K$ be $3$ here no element is more than $3$ distance away from its final position 
So if we take
$arr(1 \ to \ 6)$ and sort then surely first three element will be sorted in its final position$\{12345769108\}$ $O(6 \log 6)$
then sort $arr(3 \ to \ 9)$ then $3$ to $6$ will be sorted  $\{12345679108\}$  $O(6 \log 6$)
then at last $arr(6 \ to \ 9)$  less than $O(6 \log6) \ \ \{12345678910\}$

in general  
Sort $arr(0 \ to \ 2k)$
Now we know that $arr[0 \ to \ k)$ are in their final sorted positions
and  $arr(k \ to \ 2k)$ may be not sorted.

Sort $arr(k \ to \ 3k)$
Now we know that $arr[k \ to \ 2k)$ are in their final sorted positions
and  $arr(2k \ to \ 3k)$ may be not sorted.
.
.
.
.

sort till $arr(ik..N)$
in final sorting there will be less than $2k$ element.

in each step it will take $O(2k \log2k)$ 
and there will $\frac{n}{k}$ steps so $O(n \log k)$
option D.
 

edited by
11 votes
11 votes

Since every element can be misplaced at max by k indices, hence element 1 can be atmost at index k, element 2 at k+1,...so on. 
Create a min heap of size k out of  first k elements of input A. Now remove min & insert k+1th element  of A & continue till the last element.
Hence a total running time of O(n logk).

O(k) time for building the heap out of the first k elements + O(1) time for removing the min each time + O(logk) time for each insertion of remaining n-k elements

=> O(k) + O(1)*n + O(logk)(n-k)

=> O(nlogk)  {n-k ≈ n since given k<<n}

edited by
4 votes
4 votes

Let's tie some pieces together. If we take the textbooks at word-value, then

Quicksort is often the best practical choice.


But Insertion sort beats quick sort for nearly sorted input.


Insertion sort is practically "optimal" only when the "range" of being nearly sorted is small.

(the max distance each element is at from being sorted; $k$ in this question)

Quoting from stackoverflow

As Bob Sedgewick showed in his dissertation work (and follow-ons), insertion sort absolutely crushes the "almost-sorted array". In this case your asymptotics look good but if k < 12 I bet insertion sort wins every time. I don't know that there's a good explanation for why insertion sort does so well, but the place to look would be in one of Sedgewick's textbooks entitled Algorithms (he has done many editions for different languages). 
Insertion sort in case of large $k$ would give a time complexity of $O(k*n)$
When this $k$ is small, we can ignore it and say that the time complexity is $O(n)$

For a large $k$, we use this asymptotically optimal $O(nlogk)$ algorithm.

1) Build a min heap of $k+1$ elements.

2) Extract min. /*This is guaranteed to sort the first element of the array. Think.*/

3) Add the next element from the array to the heap.

Repeat 2) and 3).

 

Step 1) takes $O(k) \ time$

Step 2) takes $O(logk) \ time$

Step 2) takes $O(logk) \ time$ (heapify)

We repeat this for n elements, hence the total algorithm takes $O(k+nlogk+nlogk) = O(nlogk) \ time$


Final verdict

For a k-sorted array, when k is small, it takes linear time. $O(n)$ or $O(kn)$ via insertion sort.

When k is large, we can't multiply n by k in the overall time complexity, as this k becomes intolerant. We devise an algorithm in which we'd have to multiply n by logk, ie, $O(nlogk)$

 

Option D

1 votes
1 votes


// C program for implementation of binary insertion sort
#include <stdio.h> 

// A binary search based function to find the position
// where item should be inserted in a[low..high]
int binarySearch(int a[], int item, int low, int high)
{
    if (high <= low)
        return (item > a[low])?  (low + 1): low; 

    int mid = (low + high)/2; 

    if(item == a[mid])
        return mid+1; 

    if(item > a[mid])
        return binarySearch(a, item, mid+1, high);
    return binarySearch(a, item, low, mid-1);
} 

// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
    int i, loc, j, k, selected; 

    for (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i]; 

        // find location where selected sould be inseretd
        loc = binarySearch(a, selected, 0, j); 

        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = selected;
    }
} 

// Driver program to test above function
int main()
{
    int a[] = {37, 23, 0, 17, 12, 72, 31,
              46, 100, 88, 54};
    int n = sizeof(a)/sizeof(a[0]), i; 

    insertionSort(a, n); 

    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
        printf("%d ",a[i]); 

    return 0;
} 

// C program for implementation of binary insertion sort 

We can use binary search to reduce the number of comparisons in normal insertion sort. Binary Insertion Sort uses binary search to find the proper location to insert the selected item at each iteration.
In normal insertion sort, it takes O(n^2) comparisons(at nth iteration) in worst case. We can reduce it to O(log n) by using binary search. as log(n) here bounded by k we can do this is nlogk comparisons ans is D

 

Answer:

Related questions

18 votes
18 votes
3 answers
1
makhdoom ghaya asked Nov 2, 2015
3,621 views
Consider the quick sort algorithm on a set of $n$ numbers, where in every recursive subroutine of the algorithm, the algorithm chooses the median of that set as the pivot...
3 votes
3 votes
2 answers
4
makhdoom ghaya asked Oct 30, 2015
1,352 views
The maximum value of the function$f\left(x, y, z\right)= \left(x - 1 / 3\right)^{2}+ \left(y - 1 / 3\right)^{2}+ \left(z - 1 / 3\right)^{2}$subject to the constraints$x +...