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.
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.
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).
Poniższy algorytm scala wszystkie listy naraz. Jako argument przyjmuje listę list liczb całkowitych, a zwraca scaloną, posortowaną listę liczb.
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.
Do przetestowania napisanej funkcji można skorzystac z poniższego fragmentu programu: