Jak scalić cztery listy dwukierunkowe w jedną z uwzględnieniem kolejności?

Question

Witam, mam problem z połączeniem czterech list dwukierunkowych w jedną. Mam w każdej zapisany czas odczytu jako tablicę char (data, godzina) i muszę brać z czterech list po jednym elemencie, ustawić w odpowiedniej kolejności (rosnąco), potem wziąć drugą czwórkę elementów itd. aż do utworzenia listy dwukierunkowej.

Comments

Podaj łańcuch, który zawiera twoją datę i godzinę i napisz kod listy jakiej używasz.

Answer 1

Hej. Czy używasz własnej listy, czy gotowej w STL? Załącz jakiś kod ;)

Michał

Answer 2

Z czym konkretnie masz problem? Z treści zadania dokładnie wynika co należy zrobić.

Jeżeli po prosu brakuje ci pomysłu na algorytm to możesz zastosować następujący:

wynik = nowa_lista
while (wszystkie listy nie są puste) {
    element1 = zdejmij_pierwszy_element(lista1);
    element2 = zdejmij_pierwszy_element(lista2);
    element3 = zdejmij_pierwszy_element(lista3);
    element4 = zdejmij_pierwszy_element(lista4);

    tablica = [ element1, element2, element3, elelemt4 ] 
    sortuj(tablica)
    wynik.dodaj(tablica[0])
    wynik.dodaj(tablica[1])
    wynik.dodaj(tablica[2])
    wynik.dodaj(tablica[3])
}

Algorytm zadziała tylko wtedy gdy listy maja tą samą długość

Comments

Cześć. Twoje rozwiązanie jest niestety wadliwe. Elementy jednej listy mogą być wszystkie przed elementami innej.

Można albo wrzucić wszystkie elementy wszystkich list do vectora i posortować, albo zastosować dziel i rządź

Michał

---

Nie, nie mogą. Zdejmuję po jednym elemencie z każdej listy. Wkładam do tablicy i sortuję.
W kolejnej iteracji pętli zaczynam z nową (pustą) tablicą.

Szczerze dziwi mnie to zadanie. Gdyby to zależało ode mnie kazałbym złączyć te 4 listy zgodnie z porządkiem w czasie liniowym (żeby nikt nie kombinował z sortowaniem w osobnym kontenerze).

---

Szkoda, że mówisz że nie mogą, chociaż nie rozumiesz tego co mówię. Pierwsza lista może mieć same zera a inne liczby większe od zera. Jak weźmiesz po jednym elemencie to rozrzucisz te zera po całej liście...

---

Nie rozumiem co mówisz bo jesteś nieprecyzyjny.
Musisz zdecydować, czy chcesz scalić te 4 tablice w porządku rosnącym, czy chcesz sortować czwórkami, tak jak napisałeś

muszę brać z czterech list po jednym elemencie, ustawić w odpowiedniej kolejności (rosnąco), potem wziąć drugą czwórkę elementów

Jeżeli chcesz mieć jedną posortowaną listę to możesz użyć takiego algorytmu:

wynik = nowa_lista
while (wszystkie listy nie są puste) {
    minimalny = zdejmij_najmniejszy_element(lista1, lista2, lista3, lista4);
    wynik.dodaj(minimalny);
}

// funkcja pomocnicza
zdejmij_najmniejszy_element(lista1, lista2, lista3, lista4) {
    tablica_pomocnicza = [ lista1, lista2, lista3, lista4 ] // tablica wskaźników lub referencji będzie najwydajniejsza
    int index = -1;
    int min;
    for (int i=0; i<4; i++) {
        lista = tablica_pomocnicza[i]
        if (lista jest pusta)
            continue;
        if (index == -1) {
            index = i;
            min = pierwszy_element(lista);
            continue;
        }
        auto element = pierwszy_element(lista);
        if (element < min) {
            index = i;
            min = pierwszy_element(lista);
        }
    }
}

 

---

żeby posortować całą liste w kolejności sortowania nie można brać czwórki tylko tak jak napisałem post niżej

---

Widzę, że pomyliłem cię z osobą zadającą pytanie.

ullortnaci pytał o algorytm scalający 4 tablice dokładnie w taki sposób jaki przedstawiłem. Być może chodziło mu o takie scalanie jakie zaproponowałeś, ale treść pytania mówiła zupełnie o czym innym. Dlatego odpowiedziałem zgodnie z zadanym pytaniem.

Pseudoalgorytm który zaproponowałem w poprzednim komentarzu robi to samo co algorytm zaproponowany przez ciebie, ale obrabia naraz cztery tablice zamiast dwóch.

---

Rozumiem. Ok :)

Answer 3

Lista nowa1;

while (!lista1.empty() || !lista2.empty())
{
  if (lista1.empty())
  {
    nowa1.pushBack(lista2.popFront());
    continue;
  }

  if (lista2.empty())
  {
    nowa1.pushBack(lista1.popFront());
    continue;
  }

  if(strcmp(lista1.front(), lista2.front()) > 0)
    nowa1.pushBack(lista2.popFront());
  else
    nowa1.pushBack(lista1.popFront());
}

Tak samo posortować listy 3 i 4. A potem nowa1 i nowa2.

Sory za literówki. 

Michał 

Comments

Innymi słowy: sortowanie przez scalanie.

Answer 4

w STL to tak no może nie optymalnie

#include <iostream>
#include <set>
#include <list>

using namespace std;

int main() {

    std::list<int> l1= {1,5,8,37,3,5,54,9,2};
    std::list<int> l2= {1,25,8,27,3,5,4,99,2,10,12};
    std::list<int> l3= {1,75,8,7,3,25,54,9,2,55};
    std::list<int> l4= {1,65,8,7,3,5,4,49,2};

    std::list<int> lconcat;

    int licz = 0;

    while(
        l1.begin()!=l1.end()||
        l2.begin()!=l2.end()||
        l3.begin()!=l3.end()||
        l4.begin()!=l4.end()
    ) {
        std::multiset<int> s;
        if(l1.begin()!=l1.end()){
             s.insert(*l1.begin());
            l1.pop_front();
        }

        if(l2.begin()!=l2.end()) {
             s.insert(*l2.begin());
            l2.pop_front();
        }
        if(l3.begin()!=l3.end()) {
             s.insert(*l3.begin());
            l3.pop_front();
        }

        if(l4.begin()!=l4.end()) {
             s.insert(*l4.begin());
            l4.pop_front();
        }
        for(auto &x:s)lconcat.push_back(x);

    }

    for(const auto &x:lconcat )cout<<x<<'\n';
    return 0;
}