Sortowanie stabilne

Cześć, mam pytanie. Jakiego algorytmu powinienem użyć do sortowania stabilnego w czasie liniowym?

Co chcesz sortować?

Zwykle dobrze radzi sobie std::sort z <algorithm>
Możesz też potestować _{» Kursy ♦} Algorytmy ^{zbiór algorytmów}

Dzięki za info. Wolałbym nie używać std, ani gotowych funkcji.

Mam na wejściu n par liczb. Wczytuje je do tablicy i chce je posortować. Myślałem o sortowaniu bąbelkowym ale czy te sortowanie jest stabilne w czasie liniowym?

Złożoność algorytmów sortowania zależna jest od stopnia pomieszania.
Szybciej wykona się sortowanie, gdy wystarczy zamienić jedną parę liczb,
a wolniej jeśli kolejność będzie całkiem odwrotna.
Zwykle najlepszym i najszybszym algorytmem jest QuickSort.
W dziale algorytmów (link) opisana jest złożoność każdego z nich.
Kwestia doboru odpowiedniego sortowania zależy głównie od spodziewanego stopnia wymieszania danych.
Algorytmu o złożoności liniowej O(n)? Nie znam (jeszcze :)).

@ultra

Wolałbym nie używać std, ani gotowych funkcji.

Używanie gotowych funkcji ma masę zalet. Jeżeli nie chcesz, to rozumiem, że w celach edukacyjnych?

Myślałem o sortowaniu bąbelkowym ale czy te sortowanie jest stabilne w czasie liniowym?

Ma złożoność kwadratową a nie liniową. Nie ma sortowania o złożoności czasowej liniowej.

http://cs.stackexchange.com​/questions/3​/why-is-quicksort-better-than-other-sorting-algorithms-in-practice
https://en.wikipedia.org/wiki​/Category:Stable_sorts

@karambaHZP

Zwykle dobrze radzi sobie std::sort z <algorithm>

To sortowanie nie jest stabilne. Stabilne jest .

Złożoność algorytmów sortowania zależna jest od stopnia pomieszania.

Nie. Złożoność algorytmów jest stała. Tak samo stałe są worst case scenario oraz best case scenario.

Szybciej wykona się sortowanie, gdy wystarczy zamienić jedną parę liczb, a wolniej jeśli kolejność będzie całkiem odwrotna.

Ale to nie jest złożoność obliczeniowa.

Kwestia doboru odpowiedniego sortowania zależy głównie od spodziewanego stopnia wymieszania danych.

Od stopnia wymieszania ale i od rodzaju danych czy sposobu ich porównywania.

Algorytmu o złożoności liniowej O(n)? Nie znam (jeszcze :)).

Algorytm odczytania tablicy.

Jeśli liczby mają stałą wielkość, to radix sort jest stabilny i liniowy.

@Bielan, otóż to. Mam do napisania projekt, nie wykorzystując gotowych funkcji i std.

Dzięki za link. Czyli ogólnie najlepiej nadaje się do tego sortowanie przez zliczanie? Stabilne i ma złożoność O(n + k).
Lub też jak @Alueril pisze, sortowanie pozycyjne. Które z tych jest bardziej wydajnościowe?

@ultra: nie kpij. Nie masz zielonego pojęcia o złożoności obliczeniowej, a chcesz dbać o wydajność. Zaimplementuj cokolwiek i najpierw zdobądź dużo doświadczenia w klepaniu kodu. Nawet jeżeli wybierzesz potencjalnie najbardziej wydajny algorytm nie oznacza to wcale, że będzie to optymalne w wykonaniu słabo kodującego dewelopera.