Sortowanie przez podział
Mariusz:
Sortowanie przez podział , rozdzielanie listy
https://imgur.com/a/3rHRVD4
Jeżeli głowa listy jest różna od ogona listy to
1. Wybierz element rozdzielający
2. Rozdziel listę np w ten sposób jak na obrazku
3. Wywołaj rekurencyjnie procedurę sortującą dla podlist zawierających węzły o kluczach
różnych od klucza elementu rozdzielającego
4. Połącz posortowane podlisty w jedną listę
Macie jakiś inny pomysł na rozdzielenie listy niż ten na obrazku ?
Jest to partycjonowanie Lomuto ale dla listy dwukierunkowej
możliwe jest też partycjonowanie Hoare