CODEWITHSUNDEEP
c++sortingcout
Mee
Mee

Reputation: 1651

getting the nth largest number

I am trying to get the nth largest number of an array, I tried to sort the array then access the nth number by indexing; I have written this code:

#include <iostream>
using namespace std;
int largest(int a[],int k){

   for (int i=0;i<=(sizeof(a)/sizeof(*a));i++){
      for (int j=i+1;j<=(sizeof(a)/sizeof(*a));j++){

         if(a[j]>a[i]){
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;
         }
      }
   }
   return a[k-1];
}

int main()
{
   int a[]={3,2,1,0,5,10};
   int m=largest(a,4);
   cout<<m<<endl;

   return 0;
}

and when I print out m it appears to be 5 while it is expected to be 2, when I tried to replace int m=largest(a,4); with m=largest(a,1); it printed 2 so it appears that he prints the index of the array a but without sorting it, any idea?

Upvotes: 0

Views: 1182

Answers (4)

Angelicos Phosphoros
Angelicos Phosphoros

Reputation: 3057

UPD: There are STL algorithm to use: std::nth_element.

#include <iostream>
#include <algorithm>
int main(){
    int arr[] = {54, 897, 87, 4, 6,987};
    size_t length = 6, k = 3;
    std::cout<<std::nth_element(arr, arr + k, arr + length, std::greater<int>());
}

Also, if you want to implement it by yourselt you can do such thing based on quick sort:

#include <iostream>
#include <algorithm>

template<class T>
T largest_k(T* a, size_t left, size_t right, size_t k) {
  if(left>=right)
    return a[k-1];

  size_t i = left, j = right;   

  T middle = a[ i + (j-i) / 2 ];    

  do {
    while ( a[i] > middle ) i++;
    while ( a[j] < middle ) j--;

    if (i <= j) {
      std::swap(a[i], a[j]);
      i++; j--;
    }
  } while ( i<=j );

  // We need to go deeper only for needed part of a
  if ( k<=j+1 )
    return largest_k(a, left, j, k);
  if ( k>= i ) 
    return largest_k(a, i, right, k);
}

int main()
{
  int arr[] = {54, 897, 87, 4, 6,987};
  size_t length = 6, k = 3;
  std::cout<<largest_k<int>(arr, 0, length-1, k);
}

Upvotes: 1

abelenky
abelenky

Reputation: 64682

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   int a[]={3,2,1,0,5,10};
   std::sort(a, a+6, greater<int>() );  // Sort an array of 6 elements in greatest-first order.
   cout<<a[3]<<endl;                    // Show the 4th element from the front.

   return 0;
}

Upvotes: 1

giusti
giusti

Reputation: 3538

There are three problems with your code.

First, when you pass the array as an argument to your function, it decays into a pointer. So the function can never know the size of the array without additional information. It is main()'s job to find the size of the array and pass that information along to largest().

Second, you have an off-by-one error in your code, because you are attempting to iterate from 0 to the number of elements in the array.

The following will work:

#include <iostream>
using namespace std;
int largest(int a[],int k, int n){
   for (int i = 0; i < n; i++){
      for (int j = i + 1; j < n; j++){
         if (a[j] > a[i]){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
         }
      }
   }
   return a[k-1];
}

int main()
{
   int a[] = {3, 2, 1, 0, 5, 10};
   int k = 4;
   int m = largest(a, k, sizeof a/ sizeof *a);
   cout << m << endl;
}

At last but not least, you have nasty side effects in your function. If you have a function that is supposed to find the largest element of the array, it shouldn't modify the entire array in order to do so.

You can make a copy of the original array and sort it. Or you can implement a k-element sort algorithm. Either way you shouldn't change user data just to find some statistic from it.

Upvotes: 2

R Sahu
R Sahu

Reputation: 206607

The problem lies in the use of sizeof(a)/sizeof(*a) to get the number of elements of the array. sizeof(a) is the size of a pointer.

You need to pass the size of the array to the function.

int largest(int a[], int size, int k){

   for (int i=0;i<size;i++){
      for (int j=i+1;j<size;j++){

      ...
      }
   }
}

and call it with

int m = largest(a, 6, 4);

Upvotes: 3

Related Questions