Jakie są kryteria wyboru algorytmu sortowania?

Question

Czytałem metodę sortowania, która obejmuje sortowanie bąbelkowe, sortowanie sortowania, sortowanie scalone, sortowanie sterty, sortowanie wiadra itp. Zawierają również złożoność czasową, która pomaga nam określić, które sortowanie jest wydajne. Więc miałem podstawowe pytanie. Jeśli mamy dane, to w jaki sposób będziemy sortować. Złożoność czasowa jest jednym z parametrów, które pomagają nam w wyborze metody sortowania. Ale czy mamy inny parametr do wyboru metody sortowania ?.

Po prostu staram się rozgryźć, żeby lepiej zrozumieć.

Mając jakieś zapytanie o sterty sortowania:

1. Jeżeli używamy sterty sortowania?

2. Co stanowi większą zaletę sortowania sterty (z wyjątkiem złożoności czasowej O (n log n))?

3. Co jest wadą sortowania sterty?

4. Co to jest czas budowy sterty? (Słyszałem O (n), ale nie jestem pewien.)

5. Każdy scenariusz, w którym musimy użyć sortowania sterty lub sortowania sterty jest lepszą opcją (z wyjątkiem kolejki priorytetowej)?

6. Przed zastosowaniem sortowania sterty na danych, jaki jest parametr, który będziemy analizować dane?

Answer 1

Dwie główne teoretyczne cechy algorytmów sortowania to złożoność czasu i złożoność przestrzeni.

Ogólnie rzecz biorąc, time complexity informuje nas, jak zmienia się wydajność algorytmu w miarę wzrostu rozmiaru zestawu danych. Rzeczy do wzięcia pod uwagę:

• Ile danych chcesz posortować? To pomoże ci dowiedzieć się, czy potrzebujesz algorytmu o bardzo małej złożoności czasowej.
• Jak posortowane będą twoje dane? Czy zostanie częściowo posortowany? Losowo posortowane? Może to wpłynąć na złożoność czasową algorytmu sortowania. Większość algorytmów będzie mieć najgorsze i najlepsze przypadki - chcesz się upewnić, że nie używasz algorytmu w najgorszym zestawie danych.
• Złożoność czasu to nie to samo co czas pracy. Należy pamiętać, że złożoność czasu opisuje jedynie, w jaki sposób wydajność algorytmu zmienia się wraz ze wzrostem rozmiaru zestawu danych. Algorytmem, który zawsze przejdzie przez wszystkie wejścia, będzie O (n) - jego wydajność jest liniowo skorelowana z rozmiarem wejścia. Ale algorytm, który zawsze wykonuje dwa przejścia przez zbiór danych, to także O (n) - korelacja jest nadal liniowa, nawet jeśli stała (i rzeczywisty czas działania) jest inna.

Podobnie, złożoność przestrzeni opisuje, ile przestrzeni potrzebuje algorytm do uruchomienia. Na przykład sortowanie proste, takie jak insertion sort, wymaga dodatkowej stałej przestrzeni do przechowywania wartości aktualnie wstawianego elementu. Jest to pomocnicza złożoność przestrzeni O (1) - nie zmienia się wraz z rozmiarem wejścia. Jednak merge sort tworzy dodatkowe tablice w pamięci podczas działania, ze złożonością pomocniczą O (n). Oznacza to, że wymagana dodatkowa przestrzeń jest liniowo skorelowana z rozmiarem wejścia.

Oczywiście projektowanie algorytmów często jest kompromisem między czasem i przestrzenią - algorytmy o małej złożoności przestrzeni mogą wymagać więcej czasu, a algoytmy o niskiej złożoności czasowej mogą wymagać więcej miejsca.

Aby uzyskać więcej informacji, przydatna może być funkcja this tutorial.

---

Aby odpowiedzieć na zaktualizowane pytanie, może okazać się przydatna strona wikipedia pod numerem Heap Sort.

Answer 2

Jeśli masz na myśli kryteria wyboru rodzaju, oto kilka innych elementów do rozważenia.

Ilość posiadanych danych: Masz dziesięć, sto, tysiące lub miliony przedmiotów do posortowania.

Złożoność algorytmu: im bardziej złożony, tym więcej testów należy wykonać, aby upewnić się, że jest poprawny. W przypadku niewielkich ilości, sortowanie bąbelkowe lub szybkie sortowanie jest łatwe do kodowania i testowania, wersety innych rodzajów, które mogą być przesadzone dla ilości danych, które należy posortować.

Ile czasu potrzeba na sortowanie: Jeśli masz duży zestaw, bąbelkowanie/szybkie sortowanie zajmie dużo czasu, ale jeśli masz dużo czasu, może to nie być problemem. Jednak użycie bardziej złożonego algorytmu skróci czas sortowania, ale kosztem większego wysiłku w zakresie kodowania i testowania, co może być warte, jeśli sortowanie będzie trwać od długich (godzin/dni) do krótszego czasu.

Dane same w sobie: Czy dane są zbliżone do wszystkich. W przypadku niektórych rodzajów możesz otrzymać listę liniową, więc jeśli wiesz coś o składzie danych, może to pomóc w określeniu, który algorytm wybierze dla danego wysiłku.

Ilość dostępnych zasobów: Czy masz dużo pamięci, w której przechowujesz wszystkie elementy, czy też chcesz przechowywać elementy na dysku. Jeśli wszystko nie mieści się w pamięci, sortowanie scalone może być najlepsze, gdzie inne mogą być lepsze, jeśli pracujesz ze wszystkim w pamięci.