Algorytm dla danych czesciowo posortowanych

Jaki jest najszybszy algorytm sortowania dla danych już częściowo posortowanych?
Quick sort zupełnie się nie nadaje bo dla takich danych ma zlozonosc n^2, merge sort będzie zawsze działał ze złożonością n log n heap sort podobnie (chyba).
Może bubble sort nie jest złym wyborem?

A to nowość że quicksort ma n^2 dla częściowo posortowanych danych. Możesz przybliżyć kto ci takich głupot naopowiadał? Pesymistyczny przypadek quicksorta zależy choćby od doboru pivota i tego czy to Lomuto czy Hoar...
Moim zdaniem quicksort z pivotem jako środkowym elementem byłby najlepszym wyjściem bo dla częściowo posortowanych danych, wręcz przeciwnie, jest całkiem niezły.
Bąbelki? :D Bubblesort jest zły zawsze! Chyba nie istnieje przypadek kiedy byłby najlepszym rozwiązaniem ;] Jak już chcesz proste sortowanie (bo np. masz prawie całkiem posortowane dane) to proste wstawianie - insertionsort.

Shalom - zastanow sie zanim zaczniesz pisać, że ktoś wygaduje bzdury.
QuickSort działa dobrze dla danych o rownomiernym rozkładzie. Dla danych częściowo posortowanych zaczyna się degenerować (chociażby dlatego powstało takie sortowanie: http://en.wikipedia.org/wiki/Introsort). Nie mówie, że zawsze będzie osiągać n^2 ale prawdopodobieństwo, że osiągnie jest większe niż w przypadku losowych danych.
Insertionsort mógłbym się zgodzić ale z bubble sort znowu pierdzielisz.

Pesymistyczny przypadek quicksorta zależy od sposobu wybierania pivota (nie wierzysz? to wymyśl sobie jakiś zbiór liczb i ułóż z nich pesymistyczny ciąg dla quicksorta choćby z pivotem jako środkowym elementem i powiedz czy wygląda ci to na posortowany ciąg). Jeśli będzie to element skrajny to faktycznie dla posortowanych danych dostaniesz O(n^2). No ale kto normalny, wiedząc że dane mogą być częściowo posortowane, będzie go tak wybierał...
A co do bąbelków, to prosze bardzo, wykaż że sie mylę (a bardzo prawdopodobne że tak jest) i pokaż przykład danych dla których bąbelki będą szybsze od prostego wstawiania albo prostego wybierania.
Bo z tego co zapamiętałem z zajęć na których liczyliśmy złożoność tych 3 algorytmów, to niestety ale bąbelki wypadały znacznie gorzej (jeśli chodzi o stałe ukryte w notacji O).

Pesymistyczny przypadek quicksorta zależy od sposobu wybierania pivota (nie wierzysz? to wymyśl sobie jakiś zbiór liczb i ułóż z nich pesymistyczny ciąg dla quicksorta choćby z pivotem jako środkowym elementem i powiedz czy wygląda ci to na posortowany ciąg). Jeśli będzie to element skrajny to faktycznie dla posortowanych danych dostaniesz O(n^2). No ale kto normalny, wiedząc że dane mogą być częściowo posortowane, będzie go tak wybierał...

Nie kumasz... Dane częściowo posortowane mogą być na milion różnych sposobów i nie znajdziesz dobrego pivotu, który nigdy nie da pesymistycznej złożoności. Dlatego powstało chociażby introsort).

A co do bąbelków, to prosze bardzo, wykaż że sie mylę (a bardzo prawdopodobne że tak jest) i pokaż przykład danych dla których bąbelki będą szybsze od prostego wstawiania albo prostego wybierania.

LOL. Sortowanie przez wybieranie to jedzie pełną parą O(n^2) nawet dla danych całkowicie posortowanych. Bąbelki dla danych całkowicie posortowanych mają złożoność O(n). A nad przykładem pomyśle jutro, ale generalnie liczyłem, że ktoś na 4p będzie miał jakieś doświadczenia z takim problemem.

@nzz w ogóle o co sie tak puszysz ?
dostałeś odpowiedź od Shalom-a która jest poprawna. Upierasz sie przy sortowaniu bąbelkowym. Zatem średni z Ciebie programista (bez urazy), lepiej by było jakbyś chociąz Shake Sort popierał. Bąbelkowe ma O(n) tylko dla przypadku całkowicie posortowanego ale i tu zauważ ze musi wykonac n-1 porównań. Innaczej będzie w sortowaniu przez wstawianie. Niezmiennikiem pętli jest posiadanie dwóch tablic - jednej posortowanej a drugiej nie. Więc jeżeli masz GDZIEŚ w zbiorze wejściowym (do posortowania) podzbiór już posortowany to wykonujesz porównania reszty tablicy z tą posortowaną częścią. Istnieje prawdobodobieństwo ze wykona sie to w czasie O(n).
Co do quick Sorta którego tak nie cierpisz - zawsze mozna dobrac tak pivota że sortowanie przebiegnie w dobrym czasie - chyba Knuth (bo Cormen raczej nie) pisał jak mozna oszacowac miejsce pivota. Jednak aparat matematyczny wykorzystywany w celu jego oszacowania do prostych nie należy.
Pozdrawiam

ja się też dziwie zadałeś pytanie dostałeś odpowiedź i się dąsasz. Jak wiesz lepiej to po co pytasz?
Ostatecznie, jak masz wątpliwości to napisz jakieś benchmarki dla najczęściej występującego w twoim programie zestawu danych i je porównaj. Nie jest to trudne ani bardzo czasochłonne, a będziesz miał odwiedź, z którą raczej nie będziesz dyskutował :P.

dla danych czesciowo posortowanych w specyficzny sposob: bitonic sort - wymaga, aby ciag danych byl dwumonotoniczny, tzn. zeby byl wstepnie posortowany w "trojkat": wartosci rosna-potem-maleja, albo maleja-potem-rosna

mimo mocnego ograniczenia a dane wejsciowe, mozna go latwo uogolnic - po 'zagniezdzeniu' hmmm... chyba log(n).. instancji algorytmu, otrzymuje sie sortowanie bez zalozenia na dane wejsciowe (lub, zaleznie jak mocno go sie zagniezdzi 'w sobie', pozostaje wymaganie dwumonotonicznosci na rozlacznych przedzialach). no i owa ogolna postac calkiem niezle sie zrownolegla, a na architekturze hiperkostki to juz w ogole:)

• niemniej, uwaga: bitonic sort w każdj postaci ma złozoność czasową niezalezna od wartosci danych! ona zalezy od N i od wybranej przez Ciebie liczby zagniezdzen. fakt, ze Twoje dane sa czesciowo posortowane jest informacja dla Ciebie, i dzieki nej mozesz wybrac mniejszy poziom zagniezdzen lub po prostu narzucic swoj sposob podzialu na podzbiory bitoniczne, ktore potem beda łączone - podstaowwy algorytm tego sam za Ciebie nie zrobi!

Nie dąsam się tylko mnie takie teksty denerwują:

Możesz przybliżyć kto ci takich głupot naopowiadał

I to co Shalom odpowiedział wcale nie jest poprawne nie mówiąc już o polecaniu sortowania przez wybór [rotfl]

A pytam się bo może ktoś miał już doświadczenia z takimi algorytmami, sam przeprowadzał benchmarki i ma ochotę się podzielić wiedzą.

Shalom napisał(a)

Bąbelki? Bubblesort jest zły zawsze! Chyba nie istnieje przypadek kiedy byłby najlepszym rozwiązaniem Jak już chcesz proste sortowanie (bo np. masz prawie całkiem posortowane dane) to proste wstawianie - insertionsort.

sortowanie dwóch liczb ;p

a może zdradź na czym polega to częściowe posortowanie. Wtedy może się okazać, że odpowiedź jest prostsza niż ci się wydaje.

IMHO, autor pod tym rozumieuklad danych wejsciowych, ktory w pewnych przedzialach (pewnie szerokosci wiekszej niz 2 elementy :))))) ) jest juz posortowany zgodnie z oczekiwanymi zalozeniami, np. rzucenie kota na klawiature wygenerowalo takie cos, klamry oznaczaja "czesciowe posortowane podciagi o n.el.>2":
(uwaga: podciąg w rozumieniu przedzial.. )

6 5 9 8 5 6 3 (2 2 3 7 9) 4 7 3 8 4 2 7 3 9 4 7 2 (1 3 4 9) (2 3 4)
(oczywiscie to bez sensu.. w takim przypadku poszukaloby sie juz obu przypadkow: pod-posortowania zgodnego- i przeciwnego-, poneiwaz podciagi posortowane przeciwnie sa banalne w odwroceniu i wiedze o nich moznaby rownie latwo wykorzystac)

tylko, w takim ujeciu, czym to sie niby mialo roznic od klasycznego problemu sortowania? i czym ciag wejsciowy roznilby sie od kompletnie losowego? przeciez nawet w kompletnie losowych liczbach trafiaja sie gdzieniegdzie kilku-kilkunastoelementowe monotoniczne grupy..

jesli mialo by to cos dac, to musielibysmy ALBO apriori znac pozycje tychze posortowanych podciagow: majac je, wstepne podzielenie dziedziny problemu i algo pokroju mergesort sie klaniaja "i tyle". ALBO wiedzac ze wystapia sensownej dlugosci podciagi, przed wlasciwym sortowainem (lub w trakcie) sobie "szybko" przeleciec po zestawie i patrz wyzej.

pytanie, czy to nie zarżnie algorytmu dorzucajac ekstra N krokow zwiazanych z porownywaniem, przerzucaniem podciagow?
pytanie, jak tragiczna bedzie zlozonosc dla pesymistycznego przypadku (max. posort podciag = 2 elementy)