Scalanie Posortowanych List

Zadanie

Napisz algorytm, który scali wszystkie podane listy w jedną. Wszystkie podane listy zawierają tylko liczby całkowite i są posortowane. Mogą mieć różną ilość elementów. Napisz optymalne rozwiązanie. W tym artykule zostanie omówiony przykładowy algorytm to realizujący.

Przykład

Dane są następujące listy {[1, 6, 9], [3, 4], [7, 8, 9]}. Po scaleniu otrzymana lista to [1, 3, 4, 6, 7, 8, 9, 9]. Podczas przepisywania elementów zaniedbujemy kolejność takich samych elementów z różnych list tj. w przykładzie wystąpiły dwie 9, ale nie ma znaczenie z której tablicy, która była wcześniej przepisana.

Analiza Zadania

Zadanie można rozwiązać na dwa sposoby. Pierwszy z nich zakłada, że scalamy 2 listy, a następnie wynikową z kolejną itd. Przykładowo {[1, 6, 9], [3, 4], [7, 8, 9]} zostałoby kolejno przekształcone w {[1, 3, 4, 6, 9], [7, 8, 9]}, a potem do ostatecznego wyniku. Takie rozwiązanie jest wygodne, ponieważ algorytm do scalania dwóch list można było poznać przy okazji sortowania przez scalanie.

Drugi pomysł polega na napisaniu algorytmu, który będzie przekształcał wszystkie listy równocześnie. Jego działanie polegałoby na utworzeniu pustej listy wynikowej i dołączaniu do niej aktualnie najmniejszej wartości ze wszystkich list, aż chociaż jedna lista nie jest pusta. Po zdjęciu wszystkich elementów zwracana jest utworzona lista. Zakładając, że jest k list po n elementów to złożoność wynosi O(kn).

Implementacja

Poniższy algorytm scala wszystkie listy naraz. Jako argument przyjmuje listę list liczb całkowitych, a zwraca scaloną, posortowaną listę liczb.

1. vector<int> ScalListy(vector<vector<int>> listy) {
2.   vector<int> wynik;
3.   int indeks = 0;
4.   int * poz = new int[listy.size()] {0};
5.   while (indeks != -1) {
6.     indeks = -1;
7.     int min = INT32_MAX;
8.     for (int i = 0; i < listy.size(); i++) {
9.       if (poz[i] < listy[i].size() && listy[i][poz[i]] < min) {
10.         min = listy[i][poz[i]];
11.         indeks = i;
12.       }
13.     }
14.     if (indeks != -1) {
15.       wynik.push_back(min);
16.       poz[indeks]++;
17.     }
18.   }
19.   return wynik;
20. }

W pętli wyszukiwany jest minimalny element, a następnie zostaje dopisany na koniec aktualnej listy wynikowej. Jeśli okaże się, że domyślna wartość minimalnego elementu nie zostanie zmieniona oznacza to, że wszystkie listy są puste, a więc można przerwać wyszukiwanie. Do wybierania elementów z kolejnych pozycji list służą wskaźniki na odpowiednie pozycje. Dla danej listy jest on zwiększany kiedy zostanie z niej pobrany element.

Testowanie funkcji

Do przetestowania napisanej funkcji można skorzystac z poniższego fragmentu programu:

1. vector<int> WczytajListe(int i) {
2.   int ile, tmp;
3.   cout << "Ile elmentow ma lista " << i << "?\n n" << i << " = ";
4.   cin >> ile;
5.   vector<int> lista;
6.   cout << "Podaj elementy listy " << i << ":" << endl;
7.   while (ile-- > 0) {
8.     cin >> tmp;
9.     lista.push_back(tmp);
10.   }
11.   return lista;
12. }
14. int main () {
15.   int k;
16.   cout << "Ile jest list?\n k = ";
17.   cin >> k;
18.   vector<vector<int>> listy;
19.   for(int i = 0; i < k; i++) {
20.     listy.push_back(WczytajListe(i + 1));
21.   }
22.   vector<int> wynik = ScalListy(listy);
23.   for (int i = 0; i < wynik.size(); i++) {
24.     cout << wynik[i] << " ";
25.   }
26.   system("pause");
27.   return 0;
28. }

• Kod źródłowy Implementacja