TIFR CSE 2012 | Part B | Question: 13

Question

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$?

• A. $A$ can be sorted with constant $\cdot kn$ comparison but not with fewer comparisons.
• B. $A$ cannot be sorted with less than constant $\cdot n \log n$ comparisons.
• C. $A$ can be sorted with constant $\cdot n$ comparisons.
• D. $A$ can be sorted with constant $\cdot n \log k$ comparisons but not with fewer comparisons.
• E. $A$ can be sorted with constant $\cdot k^{2}n$ comparisons but not fewer.

Comments

It could be done via Heap also refer  Aryabhatta's answer on -->

https://stackoverflow.com/questions/2726785/sorting-an-almost-sorted-array-elements-misplaced-by-no-more-than-k

But yes important question is --> could it be improved further or not ?

---

@srestha Ma'am Please check.

1.I came up with something that consider the " no. of inversions " 

2.Is the given order give max inversion possible ?

3.Is it okay if I go with this ?

4.Any flaw ?

 

---

It’s not possible to think various method suggested in answers, in exam. Maximum I can think of using insertion sort which will take O(nk) time complexity in worst case.

Answer 1

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.
 

Comments

@VS true . we have to solve lot of standard questions for this

---

@mehul vaidya

What do you actually mean by standard questions?

---

This is nothing but sorting a k-sorted array.

https://www.geeksforgeeks.org/nearly-sorted-algorithm/

Answer 2

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+1^th 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}

Comments

Sorry my bad...

But still the total running time would be O(nlogk).

Reason: 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}

---

is build heap not includes insertion?

---

@srestha 

Nope. In build heap ,we already have elements in our hand so "O(n)" if "n" elements are considered is the time required for rearranging the heap.

Answer 3

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

Comments

you are missing comparisons to build mean heap

Answer 4

// 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

 

Comments

if possible can anyone explain the Question, please