Napisz program, który wskaże 5 element co do wilekości w tabeli.

Witam, mam napisać program, który wskaże 5 co do wielkości element w tabeli. Użytkownik wpisuje liczby naturalne zakończone zerem , który stanowi tylko i wyłącznie znacznik końca danych. Można założyć że użytkownik podał przynajmniej 5 lioczb naturalnych i zakończył wpisywanie 0. Czyli dla np danych wejściowych: 3 5 4 1 2 0 pogram powinien zwrócić wartość 5. Nie chce sortować całej tabeli tylko potrzebny mi jest szybszy sposób tylko nie mam pomysłu za bardzo.

std::nth_element().

Ale mam napisać algorytm a nie korzystać z gotowych funkcji czy bibliotek.

To weź pierwsze 6 liczb i posortuj je malejąco. Każdą następną liczbę wstaw na ostatnią pozycję i posortuj ponownie. Drugie i dalsze sortowania można wykonać szybko korzystając z tego, że pierwsze 5 liczb jest już posortowane. Piąta liczba to wynik. Tak na prawdę operacja sortowania jako taka nie jest tu w ogóle potrzebna, po prostu łatwiej wytłumaczyć ten algorytm korzystając z tego konceptu.