Кіріспе
Сызықтық уақыт, элементтер тізбесін сұрыптаудың аналогты алгоритмі. Спагетти сұрыптау – А. К. Дьюдни Scientific American бағанында ұсынған элементтер тізбесін сұрыптаудың сызықтық уақыт, аналогты алгоритмі. Бұл алгоритм O(n) көлемді стектік жадты пайдаланып, элементтер тізбесін тұрақты түрде сұрыптайды. Оны жүзеге асыру үшін параллель процессор қажет.
Spaghetti sort is a linear time, analog algorithm for sorting a sequence of items, introduced by A. K. Dewdney in his Scientific American column. This algorithm sorts a sequence of items requiring O(n) stack space in a stable manner. It requires a parallel processor.
Алгоритм
Қарапайымдылық үшін, табиғи сандар тізімін сұрыптаймыз деп есептейік. Сорталау әдісі пісірілмеген спагетти таяқшаларын қолдану арқылы көрсетілді: тізімдегі әр x саны үшін x ұзындығындағы таяқшаны алыңыз. (Бірлікті таңдаудың бір ыңғайлы жолы – тізімдегі ең үлкен сан m бір толық спагетти таяқшасына сәйкес келсін. Бұл жағдайда, толық таяқша m спагетти бірлігіне тең болады. x ұзындығындағы таяқша алу үшін, бір таяқшаны екіге бөліп, x бірлігінен тұратын бөлігін алыңыз, ал қалғанын тастаңыз.) Барлық спагетти таяқшаларын жинағаннан кейін, оларды біраз бос ұстап, үстелге түсіріңіз, осылай барлығы тік тұрып, үстел бетіне тіреледі. Енді, әр таяқша үшін, екінші қолыңызды жоғарыдан төмен түсіріңіз, таяқшаға тигенше – бұл әрине ең ұзын таяқша. Бұл таяқшаны алып, оны (бастапқыда бос) шығыс тізімінің басына қосыңыз (немесе, балама ретінде, оны шығыс массивтің соңғы бос орнына орналастырыңыз). Барлық таяқшалар алынып тасталғанша қайталаңыз.
For each number x in the list, obtain a rod of length x. (One practical way of choosing the unit is to let the largest number m in the list correspond to one full rod of spaghetti. In this case, the full rod equals m spaghetti units. To get a rod of length x, break a rod in two so that one piece is of length x units; discard the other piece.) Once you have all your spaghetti rods, take them loosely in your fist and lower them to the table, so that they all stand upright, resting on the table surface. Now, for each rod, lower your other hand from above until it meets with a rod—this one is clearly the longest. Remove this rod and insert it into the front of the (initially empty) output list (or equivalently, place it in the last unused slot of the output array). Repeat until all rods have been removed.
Талдау
Макаронның n таяғын дайындау сызықтық уақытты қажет етеді. Таяқтарды үстелге төсеу тұрақты уақытты қажет етеді, O(1). Мұның себебі – қол, спагетти таяқтары және үстел толыққанды параллель есептеу құрылғысы ретінде жұмыс істейді. Содан кейін n таяқты алып тастау керек, сондықтан әрбір байланыс және алып тастау операциясы тұрақты уақытты қажет етеді деп есептесек, алгоритмнің ең нашар жағдайдағы уақыт күрделілігі O(n) болады.