Шпагетно сортирање

Шпагетно сортирање је аналогни алгоритам са линеарном временском сложеношцу, који сортира низ предмета. Први га је представио Алеxандер Деwднеy у својој колумни за магазин Сциентифиц Америцан (или краће СциАм).^[1]^[2]^[3]

Алгоритам[уреди | уреди извор]

Ради једноставности, претпоставимо да сортирамо листу природних бројева. Метод сортирања је приказан тако да користи некуване штапиће шпагета:

За сваки број x из листе, добијамо штапић дужине x. (Практичан начин за одабир јединице је да пустимо да највећи број m у листи одговара једном целом штапићу шпагета. У овом случају цео штапић је једнак m јединица шпагета. Да би добили штапић дужине x, једноставно поделимо штапић на два дела како би један део био дужине x јединица; други део уклонимо.)
Једном кад добијемо све штапиће шпагета, ставимо их лабаво у шаку и спустимо их на сто, тако да сви штапићи стоје усправно, ослањајући се на површину стола. Сада спуштамо руку ка штапићима, док не додирнемо један. Онај кога прво додирнемо је наравно најдужи. Уклонимо овај штапић, и ставимо га у предњем делу излазне листе (која је иницијално празна), (или еквивалентно, сместимо га на задњем неискоришћеном месту у излазном низу.). Овај поступак понављамо све док имамо штапиће које треба уклонити.

Анализа[уреди | уреди извор]

Припрема n штапића шпагета одузима линеарно време. Спуштање штапића на сто има константно време, О(1). Ово је могуће због руке, док штапици шпагета и сто функционишу као уређај који паралелно рачуна. Ако имамо n штапића које је потребно уклонити, претпостављајући да свака операција додиривања и уклањања захтева константно време, сложеност најгорег случаја је О(н).

Просторна сложеност је исто минимална: О(н), измерено штапићима шпагета.

Референце[уреди | уреди извор]

^ Деwднеy, А. К. (јун 1984), „Он тхе спагхетти цомпутер анд отхер аналог гадгетс фор проблем солвинг”, Сциентифиц Америцан, 250 (6), стр. 19—26
^ Стауффер, Диетрицх (15. 5. 1999), Аннуал Ревиеwс оф Цомпутатионал Пхyсицс VI, Wорлд Сциентифиц, стр. 260, ИСБН 978-981-02-3563-5
^ Адаматзкy, Андреw (1. 7. 2006), Фром Утопиан то Генуине Унцонвентионал Цомпутерс, Лунивер Пресс, стр. 96, ИСБН 978-0-9551170-9-1

Спољашње везе[уреди | уреди извор]

[1] Деwднеy, А. К. (јун 1984), „Он тхе спагхетти цомпутер анд отхер аналог гадгетс фор проблем солвинг”, Сциентифиц Америцан, 250 (6), стр. 19—26

[2] Стауффер, Диетрицх (15. 5. 1999), Аннуал Ревиеwс оф Цомпутатионал Пхyсицс VI, Wорлд Сциентифиц, стр. 260, ИСБН 978-981-02-3563-5

[3] Адаматзкy, Андреw (1. 7. 2006), Фром Утопиан то Генуине Унцонвентионал Цомпутерс, Лунивер Пресс, стр. 96, ИСБН 978-0-9551170-9-1

[1]

[2]

[3]