Strona główna » Algorytmy » Artykuły » Kolejna Największa Wartość
1..k
 

Kolejna Największa Wartość

https://mattomatti.com/a0058

Algorytm

W celu znalezienia k-tej największej wartości wystarczy posortować dane i wybrać k-ty element. Jednak często zapisana lista i tak nie zostanie zapisana, więc można zastosować bardziej optymalny algorytm.

Opis

W celu optymalizacji wyszukiwania k-tego elementu można pominąć sortowanie tablicy. Algorytm polega na utworzeniu k elementowej tablicy pomocniczej do której będą dopisywane kolejne elementy z tablicy głównej. W tablicy pomocniczej elementy będą zawsze posortowane malejąco, więc po przejrzeniu całej tablicy wystarczy zwrócić ostatni element.

Oszczędność tutaj dotyczy zasobów. Niektóre z algorytmów sortowania wymagają dodatkowej tablicy tej samej długości co tablica główna. W tym przypadku potrzeba zaledwie O(k) dodatkowej pamięci. Dodatkowym atutem algorytmu jest fakt, że w trakcie wyszukiwania można wykluczyć powtarzające się wystąpienia tych samych elementów.

Przykład

Przykład 1

Weźmy na początek tablice L := {5, 2, 4, 1, 3}. Szukamy drugiego największego elementu, więc tymczasowa tablica będzie składać się z dwóch miejsc. Wybierając kolejne elementy otrzymujemy:

Element
listy		Lista
Tymczasowa		Komentarz
5{_, _}Dodaj na pierwsze miejsce tablicy tymczasowej
2{5, _}2 jest mniejsze niż 5 dopisz na drugie miejsce tablicy
4{5, 2}4 < 5 i 4 > 2, więc wstawiamy 4 przed 2, ponieważ tablica ma maksymalną długość dwa to usuwamy element 2
1{5, 4}1 jest mniejsze od 5 i 4, więc nie wstawiamy do tablicy
3{5, 4}podobnie jak z 1, 3 nie jest większe od jakiegokolwiek elementu na liście

Ostateczna tablica tymczasowa to {5, 4}. Po wykonaniu wszystkich instrukcji otrzymujemy, że drugim największym elementem na liście jest 4, ponieważ jest to ostatni element w tablicy tymczasowej.

Przykład 2

Weźmy na początek tablice L := {1, 2, 3, 2, 1, 4}. Ponownie szukamy trzeciego największego elementu. Tym razem na liście są dwa elementy występujące dwa razy. Oznacza to, że drugie wystąpienia danego elementu nie będziemy uwzględniać w celu wstawienia do tablicy

Element
listy		Lista
Tymczasowa		Komentarz
1{_, _, _}Dodaj na pierwsze miejsce tablicy tymczasowej
2{1, _, _}wstaw 2 na pierwszą pozycję przesuwając 1 w prawo
3{2, 1, _}wstaw 3 na pierwszą pozycję
2{3, 2, 1}2 występuje w tablicy, więc nie dopisuj
1{3, 2, 1}1 występuje w tablicy, więc nie dopisuj
4{3, 2, 1}wstaw 4 na pierwszej pozycji i przesuń pozostałe

Ostateczna lista tymczasowa to {4, 3, 2}, więc trzecim największym elementem jest 2.

Implementacja

Wstawianie elementu

Wstawiając element do tablicy tymczasowej trzeba znać pozycję na którą go wstawić. Funkcja podajPozycje() przyjmuje trzy argumenty: wartosc - wartość, którą chcemy wstawić, lista - lista w której szukamy pozycji oraz dl jej długość. Wynikiem działania funkcji jest pozycja na której element powinien zostać wstawiony, aby lista dalej była posortowana. Jeśli element nie pasuje do tablicy to zwrócona zostanie długość tablicy.

C++
C#
  1. int podajPozycje(int wartosc, int* lista, int dl) {
  2.   for (int i = 0; i < dl; i++)
  3.     if (wartosc >= lista[i])
  4.       return i;
  5.   return dl;
  6. }

Funkcja Główna

Funkcja wyszukująca k-ty największy element wymaga podania trzech argumentów: k - który kolejny element z lista - lista elementów, która ma długość n.

C++
C#
  1. int kNajwiekszaWartosc(int k, int* lista, int n) {
  2.   int* temp = new int[k];
  3.   for (int i = 0; i < k; i++)
  4.     temp[i] = INT_MIN;
  5.   for (int i = 0; i < n; i++) {
  6.     int poz = podajPozycje(lista[i], temp, k);
  7.     if (poz < k && lista[i] != temp[poz]) {
  8.       for (int j = k - 2; j >= poz; j--)
  9.         temp[j + 1] = temp[j];
  10.       temp[poz] = lista[i];
  11.     }
  12.   }
  13.   return temp[k - 1];
  14. }

Na początku działania funkcji (2.) tworzona jest tymczasowa tablica na przechowanie kolejnych elementów. Domyślnie (3. - 4.) każde pole ma zainicjowaną wartość na minimalną wartość zmiennej typu int. Potem (5.) dla każdego elementu z listy: (6.) szukamy gdzie dany element by trafił. (7.) Zanim go wstawiamy to sprawdzamy czy pasuje do tablicy oraz czy na znalezionym miejscu nie znajduje się identyczna wartość. Jeśli warunki są spełnione to (8. - 9.) przesuwamy wartości na prawo od miejsca gdzie wstawiamy i (10.) wstawiamy element. (13.) Na koniec zwracamy ostatni element tablicy.

Testowanie funkcji

W celu przetestowania działania funkcji wystarczy przedstawiony poniżej kod. Poprosi on użytkownika o wprowadzenie danych i zinterpretuje wynik zwrócony przez funkcje.

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "Podaj dlugosc tablicy:\n n = ";
  4.   cin >> n;
  5.   int* lista = new int[n];
  6.   cout << "Podaj kolejne elementy tablicy:\n";
  7.   for (int i = 0; i < n; i++)
  8.     cin >> lista[i];
  9.   int k;
  10.   cout << "Ktory najwiekszy element podac?\n k = ";
  11.   cin >> k;
  12.   int wynik = kNajwiekszaWartosc(k, lista, n);
  13.   if (wynik == INT_MIN) {
  14.     cout << "Nie istnieje " << k << " element\n";
  15.   } else {
  16.     cout << "Szukany element to " << wynik << endl;
  17.   }
  18.   system("pause");
  19.   return 0;
  20. }

Zadania

Zadanie 1

Napisz funkcję kNamniejszaWartosc(), która poda k-ty najmniejszy na liście lista o n elementach. Przetestuj napisany kod.