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

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