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

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา
Sorting gnomesort anim.gif

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

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

GnomeSort.png

หลักการทำงาน[แก้]

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

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

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

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

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

 1 def gnomeSort(arr):
 2     n = len(arr)
 3     index = 0
 4     round = 0
 5 
 6     while index < n:
 7 
 8         if index == 0:
 9             index +=1
10 
11         if arr[index] >= arr[index - 1]:
12             index +=1
13 
14         else:
15             temp = arr[index]
16             arr[index] = arr[index - 1]
17             arr[index - 1] = temp
18             index -=1
19 
20         round +=1
21     return arr

อ้างอิง[แก้]

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