[C] Sortowanie listy dwukierunkowej

Question

Hejo, wiem że są podobne tematy, ale nie znalazłem satysfakcjonującej odpowiedzi.
Mam sobie listę dwukierunkową, milion różnych danych w niej (typu imię, nazwisko, wiek itd itd). Jak napisać funkcje sortującą tą listę wg zadanego parametru?
Bardziej niż na kodzie zależy mi na omówieniu jakiegoś schematu/algorytmu, nie musi być nlogn. Tym razem prostota > efektywność. (raczej nie quick, chciałbym załatwić to bez rekursji, napisałem już swoją wersję funkcji swap)
Nie odsyłajcie proszę do googla, chciałbym żeby wytłumaczył to ktoś przedstawiając swój sposób myślenia.

Answer 1

Siemka,

Rozwiązanie poniżej jest pierwszym, w miarę sensownym które "wpadło" mi do głowy. Myślę, że bez kartki papieru i dobrego rozplanowania jak to ma działać (pseudokod) nie zabierałbym się do pisania kodu

METODA :

Zaalokuj tablicę wskaźników na elementy tej listy następnie ją posortuj i "po przepinaj" wskaźniki elementów listy na kolejny posortowany element(czli ustaw wskaźnik elementu na kolejny wskaźnik w posortowanej tablicy) natomiast ostatni będzie pokazywał na pierwszy.

Pozdrawiam

Comments

Tyle jeszcze da się zrobić, ale chciałbym to ogarnąć bez tworzenia więcej niż kilku dodatkowych zmiennych. Tablica odpada :/

---

Jeszcze słówko o złożoności. Średnia złożoność czasowa takiego algorytmu, jeśli posortujemy qsortem, dalej powinna być ~2log(n) ale algorytm w praktyce będzie działał dłużej z powodu samych operacji tworzenia tablicy czy ustawiania wskaźników. Warto również wspomnieć, że złożoność pamięciowa także wzrośnie chyba wiemy dlaczego. Powodzenia

---

W takim razie sortowanie przez wstawianie ale przy rozmiarach list o których mówiłeś to może być róznie z czasem działania

---

Z tym "milionem" bardziej symbolicznie było, nie chodziło o liczbę elementów w liście, tylko w pojedynczej strukturze. Postaram się jakoś bąbelkowo to ogarnąć, zobaczymy jak wyjdzie.

---

@Wi_ktos, przez wstawianie ... chyba do drzewa binarnego
Po wstawieniu węzłów do drzewa musimy jeszcze przekształcić drzewo binarne
w listę przechodząc drzewo in-order

---

@Łukasz Świtaj,  jeśli koniecznie chcesz bąbelkowo to proponowałbym zastąpić 
zamianę wstawianiem i usuwaniem
Gdybyś chciał jednak bardziej efektywnie to chyba jednak rekursja będzie jednak dobrym pomysłem

Answer 2

 

Sortowanie przez scalanie 

Jeśli na liście znajduje się więcej niż jeden węzeł 

     Rozdzielasz listę mniej więcej na połowy
     Sortujesz rekurencyjnie obydwie połowy
     Scalasz dwie posortowane połowy w jedną posortowaną listę

Rozdzielanie listy 

        Szukasz środkowego węzła 
        (przechodząc listę dwoma wskaźnikami jeden iterujesz dwa razy drugi tylko raz w pojedynczym przejściu pętli)
        Inicjujesz głowy dla rozdzielanych list i przerywasz je

Scalanie dwóch posortowanych list 

      Sprawdzasz czy któraś z list jest pusta i jeśli jest to głowie listy wynikowej przypisujesz głowę drugiej listy
      Ustawiasz głowę dla listy wynikowej porównując wartości pól kluczowych w głowach list które scalasz
      Porównujesz wartości pól kluczowych w kolejnych węzłach dopóki nie przejdziesz co najmniej jednej z list
      Po przejściu jednej z list dołączasz resztę węzłów z pozostałej listy
      Dla listy dwukierunkowej musisz poprawnie ustawić wskaźniki na poprzedniki inaczej
      lista będzie poprawnie iterowana tylko w jedną stronę

Sortowanie drzewem binarnym

• Z węzłów listy dwukierunkowej budujemy drzewo binarne w ten sposób że
         pierwszy element listy dwukierunkowej wstawiamy do korzenia drzewa binarnego
         Kolejne elementy wstawiamy następująco
         Jeśli wartość wartość klucza korzenia poddrzewa jest równa
         wartości klucza wstawianego węzła to mamy wybór
         możemy wstawić węzeł albo do lewego poddrzewa albo do prawego poddrzewa
         jednak proponowałbym abyśmy w swym wyborze byli konsekwentni
        Jeśli wartość wartość klucza korzenia poddrzewa jest mniejsza od
        wartości klucza wstawianego węzła  to wstawiamy węzeł do prawego poddrzewa
        Jeśli wartość wartość klucza korzenia poddrzewa jest większa od
        wartości klucza wstawianego węzła  to wstawiamy węzeł do lewego poddrzewa
• Przekształcamy drzewo binarne w listę dwukierunkową przechodząc je „ in order”
  czyli w kolejności L -> P -> R (Lewy potomek -> Rodzic -> Prawy potomek)

   

Sortowanie przez podział

1. Wybór elementu rozdzielającego , tzw pivota
   Dla listy najszybszy dostęp mamy do głowy i ogona
   inne węzły musielibyśmy wyszukać

2. Rozdzielenie listy na trzy podlisty

   1. na podlistę o kluczach mniejszych niż klucz pivota

   2. na podlistę o kluczach równych kluczowi pivota

   3. na podlistę o kluczach większych niż klucz pivota

3. Rekurencyjne sortowanie podlist o kluczach różnych od klucza pivota

4. Połączenie podlist w listę wynikową
   To łączenie bywa nazywane konkatenacją

 

Bez rekursji to może łączenie naturalne ?

.kassad mógłby ten algorytm dokładnie opisać

Co prawda łączenie naturalne jest stosowane do sortowania plików

ale można ten algorytm przystosować do sortowania listy