การเรียงลำดับแบบสปาเกตตี

การเรียงลำดับแบบสปาเกตตี (อังกฤษ: Spaghetti sort) คือ ขั้นตอนวิธีการเรียงลำดับโดยมีวิธีคิด สมมุติให้ค่าของรายการแต่ละรายการ เป็นความยาวของเส้นสปาเกตตีแต่ละเส้น แล้วรวบเส้นสปาเกตตีทั้งหมดตั้งบนโต๊ะ หยิบเส้นสปาเกตตีที่ยาวที่สุดออกมาวางเรียง หยิบออกมาเรื่อย ๆ วางเรียงกันไปเรื่อย ๆ จนเส้นสปาเกตตีที่รวบไว้หมด ก็จะได้เส้นสปาเกตตีที่เรียงกันจากยาวไปสั้น หรือก็คือได้รายการที่เรียงลำดับจากมากไปน้อย

การนำมาใช้

ตัวอย่างภาษาไพทอน

def spaghetti_sort(array):
	if len(array) == 0:
		return 0
	arrayS = []
	for i in range(len(array)):
		A = max(array)   
		arrayS.append(A)  
		array.remove(A)
	return arrayS

A = [186, 1455, 33, 420, 12, 71, 99, 10]
print(spaghetti_sort(A))

จากโค้ดข้างบนจะมีความซับซ้อน (complexity) เป็น O(n^2) แต่ถ้าในกรณีที่เป็นการเรียงเส้นสปาเกตตีด้วยมือจะมีความซับซ้อนเป็น O(1) เพราะเรามองเห็นเส้นที่สูงที่สุดอยู่แล้วไม่ต้องมีความซับซ้อนในทำการค้นหาเส้นที่สูงที่สุดเหมือนในโค้ด

อ้างอิง

• Adamatzky, Andrew (July 1, 2006), From Utopian to Genuine Unconventional Computers, Luniver Press, p. 96, ISBN 0-9551170-9-7