Find second largest number in an array

Question

i was trying to find the largest number in an array
:this c++ program (that i used internet help to complete it)able to find largest number in an array
it works just fine but i want to make program same way to find the second largest number.
i was thinking if we can make it same way with ignoring the largest one so it gives the second largest number but it just not working.
//code:
https://code.sololearn.com/cBVb34ldSKBE/?ref=app

Answer 1

@Netkos Ent Sort takes O(log n log) though, so it would not always be efficient in this case of just finding the 2nd largest, and is slow for a very large amount of numbers compared to an algorithm like this that I made real quick:

#include <iostream>
#include <algorithm>
#include <time.h>
#include <memory>

void sortAndFind(int arr[], size_t size)
{
std::sort(arr, arr + size);

std::cout << arr[size - 2] << "\n";
}

void find2ndLargest(int arr[], size_t size)
{
int max = arr[0];
int submax = 0;

for (int i = 0; i < size; i++)
{
if (arr[i] > max)
{
submax = max;
max = arr[i];
continue;
}

else if (arr[i] > submax)
submax = arr[i];
}

std::cout << submax << "\n";
}

int main()
{
srand(time(NULL));

const int n = 100000000;

std::unique_ptr<int[]> arr(new int[n]);

for (int i = 0; i < n; i++)
{
arr[i] = rand() % 800 + 100;
}

//make copy of original arry
std::unique_ptr<int[]> arr2(new int[n]);

for (int i = 0; i < n; i++)
{
arr2[i] = arr[i];
}

time_t start = clock();
sortAndFind(arr.get(), n);
std::cout << "Sort took: " << (clock() - start) << " ms\n";

start = clock();
find2ndLargest(arr2.get(), n);
std::cout << "non sort took: " << (clock() - start) << " ms\n";

std::cin.get();
}

Tested using 100000000 (100 million) random ints, your method takes 4402 ms (4.4 seconds), while mine takes only 141 ms (0.14 seconds). Just thought I'd share :p

Answer 2

You could always just sort the array (std::sort) and then just grab the number that's -1 from the array length. (sizeof)

-----------------------------
(from stack)

To sort an array in ascending, use:

#include <algorithm>

int main()
{
//...
std::sort(array, array+n); //where n is the number of elements you want to sort
}

To sort it in descending, use

#include <algorithm>
#include <functional>

int main()
{
//...
std::sort(array, array+n, std::greater<int>());
}