Find largest 3 max numbers

[JohnnyJoestar21]

Hello all, I am running a code to find 3 largest numbers in an array.
I got the hang of the first 2 but for some reason the third number is equal to itself.

Here is my code, also would love to make the code better.

#include <iostream>
#include <string>
using namespace std;


int main() {

	int arr[] = { 20,8,6,5,3,12,15 };
	int max = arr[0], max2, max3;
	max2 = arr[6];
	max3 = arr[1];
	for (int i = 0; i < 7; ++i) {
		if (arr[i] > max) {
			max = arr[i];
			arr[++i];
			
			
		}
		else if (arr[i] > max2) {
			arr[++i];
			max2 = arr[i];

		}
		else if (arr[i] > max3) {
			arr[++i];
			max2 = arr[i];
		}

	
	}
	cout << "Max: " << max << " \n";
	cout << "Max2: " << max2 << " \n";
	cout << "Max3: " <<max3<<" \n";
  

[George P]

make the code better

Using some modern C++ language features -- std::sort, std::begin, std::end and a lambda expression -- can make finding the 3 largest values in an array very easy.

#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <iterator>     // std::begin, std::end (requires C++17)

int main()
{
   int arr[] { 20, 8, 6, 5, 3, 12, 15 };

   std::sort(std::begin(arr), std::end(arr), [] (int a, int b) { return a > b; });

   std::cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << '\n';
}

[JohnnyJoestar21]

Personally I have never heard of these, I am quite new to programming. Would like an alternative method.

[dutch]

What do you think this statement does?

arr[++i];

Also, you are initializing the max vars in a strange way. I'm not sure what the idea is behind that.

You could do something like the following. The idea is that whenever you find a new max value you need to move all the max values below it down one element to make room for it.

#include <iostream>
#include <string>
#include <limits>
using namespace std;

int main() {
    int arr[] = { 20, 8, 6, 5, 3, 12, 15 };
    const int arrsize = sizeof arr / sizeof arr[0];
    const int minval = numeric_limits<int>::min();
    int max[3] = { minval, minval, minval };

    for (int i = 0; i < arrsize; ++i) {
        if (arr[i] > max[0]) {
            max[2] = max[1];
            max[1] = max[0];
            max[0] = arr[i];
        }
        else if (arr[i] > max[1]) {
            max[2] = max[1];
            max[1] = arr[i];
        }
        else if (arr[i] > max[2]) {
            max[2] = arr[i];
        }
    }

    cout << "Max1: " << max[0] << '\n';
    cout << "Max2: " << max[1] << '\n';
    cout << "Max3: " << max[2] << '\n';
}

[jonnin]

Personally I have never heard of these, I am quite new to programming. Would like an alternative method.

the better method is the stuff you had not heard of, and you asked for a better way :) Both ideas are critical to learning, its useful to know how to do it yourself the hard way, and its critical to know the right way using the tools. I encourage you to try to follow what he did there, sooner you do, the better your code will be long term.

another way without any tools: break it down into small bits...
what it does is loop, find largest, swap largest to the end of array, repeat on array with size -1 so the old largest is excluded... over and over.

#include<iostream>
using namespace std; 
void swap(int &a, int &b) //this is built into c++ already
{
   int tmp = a;
   a = b;
   b = tmp;	
}

int max(int* ip, int size) //so is a version of this
{
	int max = 0;
	for(int i = 1; i < size; i++)
	  if (ip[i] > ip[max])
		  max = i;
	  return max;	  
}

int main()
{
  int arr[] = { 20,8,6,5,3,12,15 };  
  int size = 7;
  int m;
  for(int i = 0; i < 3; i++, size--)
  {
	 m = max(arr, size);
	 cout << arr[m] << endl;
	 swap(arr[m], arr[size-1]);
  }	
}

if you used the built in ones, it would be as small as furry's above code.
and, both would have the same issue: they do too much work (its not important for so small a problem). Doing it in a single iteration over the data would be better than going thru the array over and over to sort it or find max on it, etc. The only way I know to do that is to do it yourself, circling back to what I first said (you need to know how to do it yourself, and how to use built in tools for it too). Note that if you kept going for all 7 max values, it would sort the array -- this is a modified sorting algorithm.

I apologize for the awful max name reuse. Its late, and it works, but that was not good. Its also not good to use names build into the language, so swap, max, etc are troublesome. Again, its late and it was off the cuff.

[mbozzi]

The only way I know to [avoid unnecessary work] is to do it yourself

The suitable algorithm here is std::nth_element if the ordering of the top n is irrelevant. Otherwise call std::partial_sort instead.

SA introselect:
https://en.wikipedia.org/wiki/Introselect

[jonnin]

ah, nice. ^^^

[George P]

@mbozzi, two sorting algorithms I didn't know much about before you mentioned them. Thank you for the mention and the nudge for playing around with using them.

#include <iostream>     // std::cout
#include <algorithm>    // std::sort

bool sort_greater(int i, int j)
{
   return (i > j);
}

int main()
{
   int arr[] { 20, 8, 6, 5, 3, 12, 15 };

   for (const auto& itr : arr)
   {
      std::cout << itr << ' ';
   }
   std::cout << '\n';

   std::partial_sort(arr, arr + 3, arr + 7, sort_greater);

   for (const auto& itr : arr)
   {
      std::cout << itr << ' ';
   }
   std::cout << '\n';

   std::cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << '\n';
}

[George P]

Personally I have never heard of these

Now you have heard of a few C++ standard library algorithms and other features. They can make code a lot more elegant and robust.

Brute force method rewrite of my previous code snippet using a reverse selection sort, a lot more code that can go wrong:

#include <iostream>

// a reverse selection sort
void ReverseSort(int a[], int n)
{
   for (int i = 0; i < n - 1; i++)
   {
      int max = i;

      for (int j = i + 1; j < n; j++)
      {
         if (a[j] > a[max]) // normal selection sort comparison is <
         {
            max = j;
         }
      }

      int temp = a[i];
      a[i]     = a[max];
      a[max]   = temp;
   }
}

int main()
{
   const int arrSize = 7;

   int arr[arrSize] { 20, 8, 6, 5, 3, 12, 15 };

   for (int i = 0; i < arrSize; i++)
   {
      std::cout << arr[i] << ' ';
   }
   std::cout << '\n';

   ReverseSort(arr, arrSize);

   for (int i = 0; i < arrSize; i++)
   {
      std::cout << arr[i] << ' ';
   }
   std::cout << '\n';

   std::cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << '\n';
}

[lastchance]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#include <iostream> #include <set> using namespace std; template <typename T> multiset<T> biggest_n( T arr[], int size, int n ) { multiset<T> S; for ( int i = 0; i < size; i++ ) { S.insert( arr[i] ); if ( S.size() > n ) S.erase( S.begin() ); } return S; } int main() { int a[] = { 20, 8, 6, 5, 3, 12, 15 }; int size = sizeof a / sizeof a[0]; multiset<int> S = biggest_n( a, size, 3 ); for ( auto e : S ) cout << e << ' '; }

12 15 20