Sortiranje liste objedinjavanjem

Lista se sortira objedinjavanjem (eng. merge sort): podeli se na dve polovine, svaka se sortira rekurzivno, pa se dve sortirane polovine učešljaju. Nijedan novi čvor se ne pravi i nijedan podatak se ne prepisuje: menjaju se samo pokazivači. Složenost $O(n \log n)$.

Rešenje napisati kao tri funkcije:

Funkcija Šta radi
Cvor<int>* ucesljaj(Cvor<int>* a, Cvor<int>* b) učešljava dve sortirane liste i vraća početak rezultata
Cvor<int>* podeli(Cvor<int>* pocetak) prekida listu na sredini i vraća početak druge polovine
Cvor<int>* sortiraj(Cvor<int>* pocetak) sortira listu i vraća njen novi početak

Pitanja za razmišljanje: Zašto je ovde rekurzija dozvoljena, kada na predavanjima kažemo da operacije nad listom pišemo iterativno? Koja je dubina rekurzije? Zašto ucesljaj mora da bude iterativna funkcija?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 2 \cdot 10^5)$, a zatim n celih brojeva.

Izlaz

Ispisati elemente liste sortirane neopadajuće.

Primer

Ulaz

6
5 1 4 2 8 2

Izlaz

1 2 2 4 5 8

Postavka

main.cpp

#include <iostream>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    // Ucesljava dve sortirane liste i vraca pocetak rezultata.
    Cvor<int>* ucesljaj(Cvor<int>* a, Cvor<int>* b)
    {
        // Ovde ide vasa implementacija
        return a;
    }

    // Prekida listu na sredini i vraca pocetak druge polovine.
    Cvor<int>* podeli(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
        return nullptr;
    }

    // Sortira listu i vraca njen novi pocetak.
    Cvor<int>* sortiraj(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
        return pocetak;
    }

} // namespace matf

Cvor<int>* ucitaj()
{
    int n;
    std::cin >> n;

    Cvor<int>* pocetak = nullptr;
    Cvor<int>* poslednji = nullptr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        Cvor<int>* novi = new Cvor<int>(x, nullptr);
        if (poslednji == nullptr)
            pocetak = novi;
        else
            poslednji->sledeci = novi;
        poslednji = novi;
    }
    return pocetak;
}

void ispisi(Cvor<int>* pocetak)
{
    for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    Cvor<int>* lista = ucitaj();

    lista = matf::sortiraj(lista);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    // Ucesljava dve sortirane liste i vraca pocetak rezultata.
    Cvor<int>* ucesljaj(Cvor<int>* a, Cvor<int>* b)
    {
        Cvor<int> privremeni(0, nullptr);
        Cvor<int>* poslednji = &privremeni;

        while (a != nullptr && b != nullptr) {
            if (a->podatak <= b->podatak) {
                poslednji->sledeci = a;
                a = a->sledeci;
            } else {
                poslednji->sledeci = b;
                b = b->sledeci;
            }
            poslednji = poslednji->sledeci;
        }

        poslednji->sledeci = (a != nullptr) ? a : b;
        return privremeni.sledeci;
    }

    // Prekida listu na sredini i vraca pocetak druge polovine.
    Cvor<int>* podeli(Cvor<int>* pocetak)
    {
        Cvor<int>* spori = pocetak;
        Cvor<int>* brzi = pocetak->sledeci;
        while (brzi != nullptr && brzi->sledeci != nullptr) {
            spori = spori->sledeci;
            brzi = brzi->sledeci->sledeci;
        }

        Cvor<int>* druga = spori->sledeci;
        spori->sledeci = nullptr;
        return druga;
    }

    // Sortira listu i vraca njen novi pocetak.
    Cvor<int>* sortiraj(Cvor<int>* pocetak)
    {
        if (pocetak == nullptr || pocetak->sledeci == nullptr)
            return pocetak;

        Cvor<int>* druga = podeli(pocetak);
        return ucesljaj(sortiraj(pocetak), sortiraj(druga));
    }

} // namespace matf

Cvor<int>* ucitaj()
{
    int n;
    std::cin >> n;

    Cvor<int>* pocetak = nullptr;
    Cvor<int>* poslednji = nullptr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        Cvor<int>* novi = new Cvor<int>(x, nullptr);
        if (poslednji == nullptr)
            pocetak = novi;
        else
            poslednji->sledeci = novi;
        poslednji = novi;
    }
    return pocetak;
}

void ispisi(Cvor<int>* pocetak)
{
    for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    Cvor<int>* lista = ucitaj();

    lista = matf::sortiraj(lista);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}