how to find/print 'n' largest element of array?

Question

my problem is for print n largest element from array.

1. use single loop
2. value dynamic(I change array and length and number that last 3/5/10),
3. not use array sorting or bubble sorting.
4. make a function

I tried this program

#include <stdio.h>
int main()
{
    int length;
    int data[] = {5, -2, 0, -3, 3}; //.it can be changable
    length = sizeof(data) / sizeof(int);
    int i = 0;
    int number = 3; //.it mean print how many largest number to print.
    int temp;
    
    for (i = 0; i < length; i++)
    {
        if (data[i] > data[i+1])
        {
            temp = data[i];
            data[i] = data[i+1];
            data[i+1] = temp;
            
        }
        else
        {
            temp = data[i+1];
            data[i+1] = data[i];
            data[i] = temp;
        }
    }
    printf("%d",data[i]);

    return 0;
}

my output is 3.

Answer 1

An obvious solution would be to sort the array but...

Given the constrains:

1. use single loop
2. Array size and number of elements is dynamic
3. do not use array sorting or bubble sorting.
4. make a function

You can do:

void print_largest_ints(int* p, unsigned nelem, unsigned n)
{
    if (n == 0) return;
    if (n > nelem) n = nelem;
    unsigned index = 0;
    for (unsigned i = 1; i < nelem; ++i)
    {
        if (p[i] > p[index])
        {
            index = i;
        }   
    }
    
    printf("%d ", p[index]);
    int saved = p[index];
    p[index] = INT_MIN;
    print_largest_ints(p, nelem, n-1);
    p[index] = saved;
}

and call it like

int main(){
    int arr[] = {7, 3, 5, 9};
    unsigned elements_to_print = 2;
    print_largest_ints(arr, sizeof arr / sizeof arr[0], elements_to_print);
    return 0;
}

Output:

9 7

This should be inaccordance with your constraints, i.e.

• It's implemented in a function (#4)
• The function can accept any array size and N-value (#2)
• The function has a single loop (#1)
• and the array isn't sorted (#3)

The array is changed while the function is executed but the array is unchanged when the function returns to main.

Answer 2

You could use the quickselect algorithm to find the n-th largest element in an unordered array. It is based on the quick sort sorting algorithm but instead of doing a complete quicksort it stops at the point where pivot itself is the n-th largest element. Also, it does not to recurse for both left and right sides of pivot, but only recurses for the part that contains the n-th largest element.

Here's an implementation in C:

#include <stdio.h>
#include <limits.h>

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int arr[], int l, int r)
{
    // use last element as pivot
    int x = arr[r], i = l;

    // move larger elements to left of pivot and smaller elements to right of it
    for (int j = l; j <= r - 1; j++) {
        if (arr[j] >= x) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]);
    return i;
}

int nthLargest(int arr[], int l, int r, int n)
{
    // if n is smaller than number of elements in array
    if (n > 0 && n <= r - l + 1) {

        // partition the array around last element
        int index = partition(arr, l, r);

        // if position is same as n, return element
        if (index - l == n - 1)
            return arr[index];

        // if position is more, recur for left subarray
        if (index - l > n - 1)
            return nthLargest(arr, l, index - 1, n);

        // otherwise recur for right subarray
        return nthLargest(arr, index + 1, r, n - index + l - 1);
    }

    return INT_MAX;
}

int main()
{
    int data[] = {5, -2, 0, -3, 3, 6, -6};
    int n = sizeof(data)/sizeof(int);
    printf("%d", nthLargest(data, 0, n - 1, 1));
    printf("\n");
    return 0;
}

Output:

6

Demo

Quickselect has O(n) average complexity with worse case of O(n^2).