0

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?

R Sahu
  • 204,454
  • 14
  • 159
  • 270
Mee
  • 1,413
  • 5
  • 24
  • 40
  • You need to sort the array in the opposite direct if you want `a[0]` to be the largest element. – NathanOliver Oct 10 '18 at 21:58
  • the problem that i think it is not sorting either ascending or descending; it gets the index of a itself without sorting it. – Mee Oct 10 '18 at 22:01
  • 3
    Look into [array decaying](https://stackoverflow.com/questions/1461432/what-is-array-decaying). Your `sizeof(a)` is providing you the size of a **pointer**, which is not what you want in that context. – Drew Dormann Oct 10 '18 at 22:02
  • What if the array contains duplicates? – Fureeish Oct 10 '18 at 22:02
  • 4
    after fixing your own you should take a look at [std::nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element) – 463035818_is_not_an_ai Oct 10 '18 at 22:02
  • Hello. If any answer here helped you, would you please consider marking one of them as accepted? It signals that the question was answered, and rewards the author of the question and the author of the answer with some reputation points. You can read more about this at [https://meta.stackexchange.com/q/5234/347897](https://meta.stackexchange.com/q/5234/347897). – giusti Sep 07 '19 at 21:06

4 Answers4

3

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);
R Sahu
  • 204,454
  • 14
  • 159
  • 270
  • omg thank you so much this worked! but what if i want to calculate the length of an array without putting it as a parameter in the function, is there a way?! – Mee Oct 10 '18 at 22:08
  • @Mee, you can use a function template with the size as the non-type parameter. See [this SO post](https://stackoverflow.com/questions/437150/can-someone-explain-this-template-code-that-gives-me-the-size-of-an-array) that uses a non-type template parameter to get the size of an array. You can use a similar method for implementing `largest`. – R Sahu Oct 10 '18 at 22:11
2

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.

giusti
  • 3,156
  • 3
  • 29
  • 44
1
#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;
}
abelenky
  • 63,815
  • 23
  • 109
  • 159
1

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);
}
Angelicos Phosphoros
  • 2,469
  • 9
  • 24