Slowsort - Slowsort - Wikipedia

Slowsort Бұл сұрыптау алгоритмі. Бұл әзіл-оспақты, пайдалы емес. Бұл принципіне негізделген көбейту және тапсыру, тілдің қалжыңы бөлу және жеңу. Оны 1986 жылы Андрей Бродер мен Хорхе Стольфи өз мақалаларында жариялады Пессимальды алгоритмдер және қарапайымдылықты талдау[1] (пародия оңтайлы алгоритмдер және күрделілікті талдау ).

Алгоритм

Slowsort - бұл рекурсивті алгоритм.

Ан орында жалған кодқа енгізу:

рәсім баяулату (A, i, j) // A [i], ..., A [j] массивін сұрыптайды егер i ≥ j содан кейін        қайту    m: = ⌊ (i + j) / 2⌋ баяулату (A, i, m) // (1.1) баяулау (A, m + 1, j) // (1.2) егер A [j] содан кейін        ауыстыру A [j] және A [m] // (1.3) баяулату (A, i, j-1) // (2)

Іске асыру Хаскелл (таза функционалды) келесідей көрінуі мүмкін.

баяу сұрыптау :: (Орд а) => [а] -> [а]баяу сұрыптау xs  | ұзындығы xs <= 1 = xs  | басқаша      = баяу сұрыптау xs ' ++ [макс лласт рласт]  -- (2)  қайда м     = ұзындығы xs `див` 2        л     = баяу сұрыптау $ алу м xs  -- (1.1)        р     = баяу сұрыптау $ түсіру м xs  -- (1.2)        лласт = соңғы л        рласт = соңғы р        xs '   = ішінде л ++ мин лласт рласт : ішінде р

Күрделілік

Орындалу уақыты Slowsort үшін .Төмен асимптоталық байланысты үшін жылы Ландау жазбасы болып табылады кез келген үшін . Slowsort сондықтан емес көпмүшелік уақыт. Тіпті ең жақсы жағдай одан да жаман Көпіршікті сұрыптау.

Әдебиеттер тізімі

  1. ^ «CiteSeerX - пессимальды алгоритмдер және қарапайымдылықты талдау». CiteSeerX  10.1.1.116.9158. Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)