การเรียงลำดับแบบโนม

การเรียงลำดับแบบโนม (อังกฤษ: gnome sort) เป็น ขั้นตอนวิธีการเรียงลำดับประเภทหนึ่ง หรืออีกชื่อหนึ่งคือ Stupid Sort มาจากหลักการที่ภูติโนม ซึ่งเป็นภูติตัวเล็กๆในที่อาศัยอยู่ในสวนได้ทำการจัดเรียงกระถางดอกไม้ โดยที่เขาพิจารณาตรงกระถางที่เค้าอยู่กับกระถางก่อนหน้า และถ้าทั้ง 2 อยู่ในตำแหน่งที่ถูกต้องแล้ว เขาจะย้ายไปดูกระถางถัดไป และถ้าเขาทำการสลับกระถางแล้ว เขาจะทำการกลับไปดูกระถางก่อนหน้าด้วย ถ้าไม่มีกระถางก่อนหน้า เขาจะย้ายไปยังกระถางถัดไปทันที ถ้าเขาย้ายไปจนไม่มีกระถางถัดไปแล้ว นั่นแสดงว่าเขาได้จัดเรียงกระถางดอกไม้เสร็จสิ้นแล้ว

Gnome sort มีความคล้ายคลึงกับ การเรียงลำดับแบบแทรก ( Insertion sort ) ยกเว้นการย้ายข้อมูลซึ่งจะเหมือนกับ การเรียงลำดับแบบฟอง ( Bubble sort ) แต่แตกต่างจากทั้งสองประเภท คือ Gnome Sort จะไม่มี Nested Loop หรือลูปซ้อน

หลักการทำงาน

• ถ้าอยู่ตำแหน่งแรกสุดให้ ย้ายไปตำแหน่งถัดไปทันที

• เปรียบเทียบข้อมูลในตำแหน่งปัจจุบันกับตำแหน่งก่อนหน้า ถ้าข้อมูลที่ตำแหน่งปัจจุบันน้อยกว่าให้สลับ

• ถ้าเกิดการสลับ ต้องกลับไปเทียบตำแหน่งของข้อมูลที่สลับแล้วกับตำแหน่งก่อนหน้านั้นด้วย และทำการสลับแบบเดิม ถ้าข้อมูลที่ตำแหน่งปัจจุบันน้อยกว่าให้สลับ

• ถ้าเปรียบเทียบข้อมูลแล้ว ถูกต้อง ให้ย้ายไปตำแหน่งถัดไป

• ถ้าย้ายจนถึงตำแหน่งสุดท้าย หรือตำแหน่งถัดไปไม่มีแล้ว แสดงว่าจบการจัดเรียงข้อมูลแล้ว

ความซับซ้อนในการทำงาน

ถึง Gnome Sort จะมี loop เดียว แต่ก็กลับไปทำตำแหน่งเดิมซ้ำ เมื่อเกิดการสลับข้อมูล ดังนั้น Big(o) = O(n^2) จะได้ Best Case คือ ข้อมูลเรียงใกล้จะเสร็จ หรือข้อมูลเรียงอยู่แล้ว และ Worst Case คือ ข้อมูลเรียงจากมากไปน้อย จะทำให้ต้องสลับทุกตัว และเปรียบเทียบทุกตัว

ตัวอย่างการเขียนโปรแกรม

ตัวอย่างการเขียนโปรแกรมการเรียงลำดับแบบโนม ( Gnome Sort ) โดยใช้ภาษาไพทอน ( Python )

def gnomeSort(arr):  n = len(arr)  index = 0  round = 0   while index < n:   if index == 0:  index +=1   if arr[index] >= arr[index - 1]:  index +=1   else:  temp = arr[index]  arr[index] = arr[index - 1]  arr[index - 1] = temp  index -=1   round +=1  return arr 

อ้างอิง

"Gnome Sort". GeeksforGeeks. Retrieved 30 April 2018.