implementing an algorithm that requires minimal memory

Question

I am trying to implement an algorithm to find N-th largest element that requires minimal memory.

Example: List of integers: 1;9;5;7;2;5. N: 2 after duplicates are removed, the list becomes 1;9;5;7;2. So, the answer is 7, because 7 is the 2-nd largest element in the modified list.

In the below algorithm i am using bubble sort to sort my list and then removing duplicates without using a temp variable, does that make my program memory efficient ? Any ideas or suggestion

type Integer_array is Array (Natural range <>) of Integer;

 procedure FindN-thLargestNumber (A : in out Integer_Array) is
 b : Integer;
 c:Integer;
 begin

//sorting of array
    for I in 0 to length(A) loop
       for J in 1 to length(A) loop
          if A[I] > A[J] then
             A[I] = A[I] + A[J];
             A[J] = A[I] - A[J];
             A[I] = A[I] - A[J];
          end if;
       end loop;
    end loop;

//remove duplicates
    for K in 1 to length(A) loop
       IF A[b] != A[K] then
       b++;
       A[b]=A[K];
     end loop;
    c = ENTER TO FIND N-th Largest number

    PRINT A[b-(c-1)] ;
 end FindN-th Largest Number 

Answer 1

If you need the N-th largest element, then you don't need to sort the complete array. You should apply selection sort, but only for the required N steps.

Answer 2

To find the n'th largest element you don't need to sort the main list at all. Note that this algorithm will perform well if N is smaller than M. If N is a large fraction of the list size then then you will be better off just sorting the list.

You just need a sorted list holding your N largest, then pick the smallest from that list (this is all untested so will probably need a couple of tweaks):

int[n] found = new int[n];

for (int i = 0;i<found.length;i++) {
   found[i] = Integer.MIN_VALUE;
}


for (int i: list) {
   if (i > found[0]) {
       int insert = 0;

       // Find the point in the array to insert the value
       while (insert < found.length && found[insert] < i) {
           insert++;
       }

       // If not at the end we have found a larger value, so move back one before inserting
       if (found[insert] >= i) {
          insert --;
       }

       // insert the value and shuffle everything BELOW it down.
       for (int j=insert;j<=0;j--) {
            int temp = found[j];
            found[j]=i;
            i=temp;
       }
   }
}

At the end you have the top N values from your list sorted in order. the first entry in the list is Nth value, the last entry the top value.

Answer 3

Instead of using bubble sort, use quicksort kind of partial sorting.

1. Pick a key and using as a pivot move around elements (move all the elements>= pivot to the left of the array)
2. Count how many unique elements are there that are greater than equal to pivot.
3. If the number is less than N, then the answer is to the right of the array. Otherwise it is in the left part of the array (left or right as compared to pivot)
4. Iteratively repeat with smaller array and appropriate N

Complexity is O(n) and you will need constant extra memory.

Answer 4

HeapSort uses constant additional memory, so it has minimal space complexity, albeit it doesn't use a minimal number of variables.

It sorts in O(n log n) time which I think is optimal time complexity for this problem because of the needed to ignore duplicates. I may be wrong.

Of course you don't need to complete the heapsort -- just heapify the array and then pop out the first N non-duplicate largest values.

If you really do want to minimise memory usage to the point that you care about one temporary variable one way or the other, then you probably have to accept terrible performance. This becomes a purely theoretical exercise, though -- it will not make your code more memory efficient in practice, because in non-recursive code there is no practical difference between using, say 64 bytes of stack vs using 128 bytes of stack.