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.
0
2
std::nth_element
0
Okej, ale mam napisać algorytm, a nie korzystać z gotowych funkcji czy bibliotek.
0
No to dla piątego elementu po prostu utworzyłbym sobie tablicę tymczasową do przetrzymywania pięciu największych i po przejechaniu całego zestawu wybrał najmniejszą liczbę z tej tablicy.
0
A pomógłbyś mi napisać algorytm? Bo jestem całkiem zielony w tym i nie mam pomysłu na to.
2
Napisz sobie max Heap. Zbudujesz go z tablicy arr[n]w czasie O(n) i Wyciągasz z niego piąty element - sumarycznie złożoność O(n).
1
kaktus123 napisał(a):
Witam, mam napisać program, który wskaże 5 co do wielkości element w tabeli.
Nie w tabeli, a w tablicy – tabele to elementy baz danych lub widoku witryny.
Bez sortowania tablicy? Hmm… Możesz sobie zadeklarować tablicę na pięć elementów o najwyższej wartości i podczas iteracji po wszystkich pobranych z klawiatury liczbach dodawać do niej bieżący, jeśli jest wikęszy od któregoś elementu. Aby dodać nowy element do takiej tablicy, trzeba będzie napisać sobie kod, który najpierw znajdzie dla niego odpowiednie miejsce, przesunie elementy (kasując ten o najmniejszej wartości) i wpisze bieżący. Sporo zachodu.
3
Pewnie.
- TablicaMax ⟵ WczytajPierwszePięć()
- N ⟵ WczytajLiczbę()
- jeśli N = 0, idź do kroku 3.
- dodaj N do TablicaMax
- posortuj TablicaMax
- usuń najmniejszą liczbę z TablicaMax
- idź do kroku 2.
- Wypisz najmniejszą liczbę z TablicaMax
0
Okej rozumiem, i teraz pytanie czy lepiej sortować jest na początku całą tablicę np bąbelkowo i wypisać 10 element tabeli czy zrobić sobie tablicę 5-elementową i sortować ją za każdym razem jeśli dodaję do niej element mniejszy od największego w niej?
0
Jeśli możesz skorzystać z sortowania to posortuj sobie od razu tablicę liczb wczytanych z klawiatury. Wtedy żadna inna tablica nie będzie Ci potrzebna i cały kod drastycznie się uprości.
0
W sumie dobrze napisany bubblesort dla tablicy kilkuelementowej jest całkiem sensownym rozwiązaniem. Dla całej tablicy może okazać się zabójczy, bo to ogółem beznadziejny algorytm sortowania jest.
0
kaktus123 napisał(a):
zrobić sobie tablicę 5-elementową i sortować ją za każdym razem jeśli dodaję do niej element mniejszy od największego w niej?
tak jak napisal furious programming nie musisz jej sortowac - ona juz jest posortowana z dokladnoscia do jednego elementu. czyli wystarczy ten jeden element wstawic w odpowiednie miejsce. a jesli skorzystasz z list to nie bedzie trzeba zadnych elementow kopiowac.
a przewidziales ze na wejsciu mozesz miec mniej niz 5 elementow?
1
Jeśli zrobisz tak jak napisał @kq tutaj i wstawianie do tablicy tymczasowej przez Sortowanie przez wstawianie to masz:
- złożoność czasową algorytmu O(5*n) = O(n)
- złożoność pamięciową algorytmu O(5) = O(1)
Takie rozwiązanie myślę że będzie wystarczająco wydajne na zajęcia uczelniane, być może nawet porównywalne wydajnościowo z nth_element (przy m = 5).
A jeszcze jakby Ci się chciało te dwa rozwiązania porównać (dla n = 100, 1000, 10000, 100000... elementów) to pewnie byś dostał ocenę maksymalną.