Kolejna Największa Wartość

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:

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

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.

1. static 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.

1. static 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.MinValue;
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.

1. static void Main(string[] args) {
2.   Console.Write("Podaj długość tablicy:\n n = ");
3.   int n = Convert.ToInt32(Console.ReadLine());
4.   int[] lista = new int[n];
5.   Console.WriteLine("Podaj kolejne elementy tablicy:");
6.   for (int i = 0; i < n; i++)
7.     lista[i] = Convert.ToInt32(Console.ReadLine());
8.   Console.Write("Który największy element podać?\n k = ");
9.   int k = Convert.ToInt32(Console.ReadLine());
10.   int wynik = kNajwiekszaWartosc(k, lista, n);
11.   if (wynik == int.MinValue) {
12.     Console.WriteLine("Nie istnieje {0} element", k);
13.   } else {
14.     Console.WriteLine("Szukany element to {0}", wynik);
15.   }
16.   Console.ReadKey();
17. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

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

• Kod źródłowy Zadanie 1