Double dimension array sorting in O(n) time

Question

I was asked a question in interview for sorting a double dimension array in O(n) time.How is it possible to do it in O(n).Can someone shed some light on it.. Thank you.

Input:

3 5 7 1
4 9 2 0
9 3 6 2

Output

0 1 2 2 
3 3 4 5  
6 7 9 9

You need to tell us what sorting a two-dimensional array means before we can answer this question. — Yonatan N
– Yonatan N, Commented May 4, 2012 at 19:52
What exactly is a double dimension array? A 2D one? If so, what is the size of that array (n x n?) — NPE
– NPE, Commented May 4, 2012 at 19:52
similar to stackoverflow.com/questions/749585/sorting-in-linear-time — hatchet - done with SOverflow
– hatchet - done with SOverflow, Commented May 4, 2012 at 20:11
Given your example, I see no difference between that array and a single dimension representation of 12 elements that would have any effect on sorting complexity. — hatchet - done with SOverflow
– hatchet - done with SOverflow, Commented May 4, 2012 at 20:35

fbafelipe · Accepted Answer · 2012-05-04 22:37:55Z

1

Don't know what did you actually mean by double dimension array, but there are sorting algorithms specific for some situations that can achieve O(n). An example of that is Counting sort, if you want to sort an array with 1000 integers in the range 1 to 1000, it can sort in O(n).

EDIT: The fact that it's a multidimensional array does not change logic of the sorting. You can convert the index (using by the sorting) to the bidimensional index like this:

array[i / N][i % N];

Where N is the size of the first dimension.

edited May 4, 2012 at 22:37

answered May 4, 2012 at 19:56

fbafelipe

4,9523 gold badges28 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Manlio Over a year ago

+1 For correct answer. However you'd be better wait what the OP actually means before answering...:)

BLUEPIXY · Accepted Answer · 2012-05-05 11:54:58Z

0

You can sort as a plain array.
E.g.

#include <stdio.h>
#include <stdlib.h>


int cmp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}

#define ROW_SIZE 3
#define COL_SIZE 4

int main(void){
    int M[ROW_SIZE][COL_SIZE]={{3,5,7,1},{4,9,2,0},{9,3,6,2}};
    int c,r,*p;

    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){
        for(c=0;c<COL_SIZE;++c){
            printf("%d ",*p++);
        }
        printf("\n");
    }
    printf("\n");
    qsort(&M[0][0], ROW_SIZE*COL_SIZE, sizeof(int), cmp);
    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){
        for(c=0;c<COL_SIZE;++c){
            printf("%d ",*p++);
        }
        printf("\n");
    }

    return 0;
}

answered May 5, 2012 at 11:54

BLUEPIXY

40.2k7 gold badges37 silver badges73 bronze badges

Collectives™ on Stack Overflow

Double dimension array sorting in O(n) time

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related