การเรียงลำดับแบบโนม
การเรียงลำดับแบบโนม (อังกฤษ: 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.