Finding Nth largest element in huge 2D array

Question

I'm trying to find the N-th largest element in a large 2-D array( approximately 850,000 elements). The method I'm using now is converting it into a 1-D array and then using the selection sort algorithm and finding it that way but it takes way too long.

Does anybody know a good way to find the N-th largest element while just looking through the matrix without sorting it, like finding the largest element.

Answer 1

I think this is some kind of homework or interview question, so I would just lay out the steps for you.

1. find an appropriate structure to store N nodes. Say X. (hint, fast search , insert, delete...)

2. travel through the matrix in one pass, save the value larger than those in your X, and save it to X, and delete the minimum in X.

3. at the end, the minimum of X is the N-largest.

The the extra space is O(N), time is O(size of the matrix).

Answer 2

I think randomized quickselect should be fine

https://en.wikipedia.org/wiki/Quickselect

average case O(n)

Answer 3

Unless you change your data structure to a better one (either a sorted array, or something else), it will be quite hard for you to not iterate through all elements of the array.

From this stackoverflow question (Print largest number in a 2d array - why do my code print three numbers) i got this code and move it to C language:

#include<limits.h>

(...)

int twodArray[XXX][YYY];
int maxValue = INT_MIN;
int yForMaxValue, xForMaxValue;
int i = 0;
    for (i = 0; i < XXX; i++) {
        for (int j = 0; j < YYY; j++)
            if (twodArray[i][j] > maxValue) {
                maxValue = twodArray[i][j];
                yForMaxValue = j;
                xForMaxValue = i;
            }
        }
    }

yForMaxValue and yForMaxValue are the index of the position to the maxValue.

Answer 4

A priority queue with a limited size of N should do the job.

Put each element of the 2D array in the queue.
O(Arraysize * log2(N)) complexity.
Then the first element in the queue is the Nth smallest (assuming arry size >= N)

#include <stdio.h>
#include <stdlib.h>
typedef int PriorityQueue_T;

typedef struct {
  PriorityQueue_T *A;
  size_t Length;
  size_t Size;
} PriorityQueue;

void PriorityQueue_Remove(PriorityQueue *Q) {
  if (Q->Length > 0) {
    size_t Index = 0;
    while (1) {
      size_t Mother = Index * 2 + 1;
      size_t Father = Mother + 1;
      if (Mother >= Q->Length) break;
      if ((Q->A[Mother] < Q->A[Father]) || (Father >= Q->Length)) {
        Q->A[Index] = Q->A[Mother];
        Index = Mother;
      } else {
        Q->A[Index] = Q->A[Father];
        Index = Father;
      }
    }
    Q->Length--;
    Q->A[Index] = Q->A[Q->Length];
    while (Index > 0) {
      size_t Child = (Index + 1)/ 2 - 1;
      if (Q->A[Index] >= Q->A[Child]) {
        break;
      }
      PriorityQueue_T tmp = Q->A[Index];
      Q->A[Index] = Q->A[Child];
      Q->A[Child] = tmp;
      Index = Child;
    }
  }
}

void PriorityQueue_Insert(PriorityQueue *Q, PriorityQueue_T x) {
   if (Q->Length < Q->Size || x > Q->A[0]) {
    if (Q->Length >= Q->Size) {
      PriorityQueue_Remove(Q);
    }
    size_t Index = Q->Length++;
    Q->A[Index] = x;
    while (Index > 0) {
      size_t Child = (Index + 1)/ 2 - 1;
      if (Q->A[Index] >= Q->A[Child]) {
        break;
      }
      PriorityQueue_T tmp = Q->A[Index];
      Q->A[Index] = Q->A[Child];
      Q->A[Child] = tmp;
      Index = Child;
    }
  }
}

// Pseudo code here to end
void PQ_FindNthSmallest(PriorityQueue_T Array[W][H], size_t N) {
  PriorityQueue Q;
  Q.Length = 0;
  Q.Size = N;
  Q.A = malloc(Q.Size * sizeof(PriorityQueue_T));

  For each element in the array
    PriorityQueue_Insert(&Q, Array[x][y]);

  printf("Nth smallest: %CorrespondingFormat", Q.A[0]);
  free(Q.A);
}