Tak sobie czytam o algorytmach i chciałbym zapytać jak to wygląda w praktyce.
Których prócz Quicksortu faktycznie się używa.
Patrząc na złożoność obliczeniową, to porównywalne, jak nie lepsze są:
Których faktycznie się używa?
Zależy od zbioru, który chcesz posortować każde z nich ma swoją złożoność pesymistyczną i optymistyczną, oraz sposób "skakania" po pamięci, lub dodatkową pamięć, której nie zawsze można sobie zażyczyć w każdej ilości np. masz duży plik do posortowania, którego na raz nie można załadować do pamięci, lub posiadasz dane częściowo posortowane tylko trzeba je "dosortować"
przez scalanie
Wymaga dodatkowej pamięci jeżeli sortujesz tablice. Jeżeli sortujesz listy, to nie wymaga dodatkowej pamięci, a ponadto zachowuje swoją złożoność, bo nie wymaga wydajnego dostępu do losowej pozycji elementu.
introspektywne
To jest przecież quicksort z kontrolą głębokości stosu i fallbackiem do jakiegoś sortowania z gwarantowaną złożonością O(n lg n), czyli zwykle heapsort. Wydaje mi się, że dość często jest właśnie stosowany jako główny algorytm.
przez zliczanie
Opłaca się tylko wtedy, kiedy rozmiar uniwersum kluczy jest porównywalny do rozmiaru danych.
przez kopcowanie
Ogólnie jest wolniejsze od sortowania szybkiego czy sortowania przez scalanie, gdyż wykonuje wiele dostępów do losowych pozycji pamięci. Losowych oczywiście dla procesora, który nie radzi sobie z przewidywaniem adresów. W przypadku sortowania szybkiego, a dokładniej partycjonowania mamy skanowanie liniowe i z tym procesory sobie bardzo dobrze radzą.
kubełkowe
Nie zawsze się opłaca. Jeśli mamy relatywnie mało elementów do porównania, ale każdy element jest bardzo długi i ponadto elementy mają długie wspólne prefiksy, to złożoność tego sortowania może stać się wysoka.
A co z sortowaniem przez wstawianie?
chciałbym zapytać jak to wygląda w praktyce.
W praktyce nie myśli się o algorytmach, tylko odpala jakąś gotową w bibliotece funkcjęsort(), która jest zazwyczaj quicksortem, ewentualnie introsortem (czyli quicksort+heapsort).