วิธีเขียน QuickSort ใน Python

วิธีเขียน QuickSort ใน Python

QuickSort ใน Python เลือกองค์ประกอบ pivot และแยกองค์ประกอบของ array ออกเป็นสอง array ใหม่ ตัวเลขมากกว่า pivot ไป array หนึ่ง ตัวเลขน้อยกว่า pivot ไปอีก array แต่ละ array ถูกจัดเรียง แล้วรวมทั้งหมดเป็นหนึ่ง

วิธีเขียน Python QuickSort

มีอัลกอริทึมจัดเรียงมากมายที่ใช้จัดเรียงลิสต์ในการเขียนโปรแกรม มี Insertion sorts, Bubble sorts, และอื่นๆ QuickSort เป็นหนึ่งในประเภทการจัดเรียงที่พบบ่อยที่สุด

ในคู่มือนี้ เราจะพูดถึง QuickSorts คืออะไร และทำงานอย่างไร เราจะเดินทางผ่านตัวอย่าง Python QuickSort เพื่อให้คุณเรียนรู้การนำไปใช้

โดยไม่ต้องพูดเยอะ เริ่มกันเลย!

Python QuickSort คืออะไร?

อัลกอริทึม QuickSort ใน Python แบ่งอาร์เรย์ออกเป็น sub-arrays อัลกอริทึมนี้เรียก sub-arrays แบบ recursive เพื่อจัดเรียงแต่ละองค์ประกอบในลิสต์ เนื้อหาของ sub-array ถูกกำหนดโดยองค์ประกอบ pivot ที่ไม่ถูกย้ายไป sub-array ใหม่

อัลกอริทึม QuickSort ใช้ divide-and-conquer (แบ่งและเอาชนะ) หมายถึงงานจัดเรียงลิสต์ถูกแยกเป็นหลาย subtasks ที่ท้ายการจัดเรียง ผลลัพธ์ของ subtasks รวมกันคืนลิสต์ที่จัดเรียงแล้ว

ใน QuickSort subtask คือ การตั้ง pivot สำหรับแต่ละ sub-list และจัดเรียงองค์ประกอบตามค่า relative to pivot

เมื่อไหร่ควรใช้ Python QuickSort?

QuickSort มีประโยชน์เมื่อ time complexity สำคัญ เพราะ QuickSort ใช้หน่วยความจำน้อยกว่าอัลกอริทึมอื่นๆ ให้ประสิทธิภาพดียิ่งขึ้น

คุณควรใช้ QuickSort ก็ต่อเมื่อคุ้นเคยกับ Python recursion เพราะอัลกอริทึม QuickSort ขึ้นอยู่กับ recursive functions

QuickSort มีประสิทธิภาพมากกว่า Merge sort บนอาร์เรย์ขนาดเล็ก อย่างไรก็ตาม บนชุดข้อมูลขนาดใหญ่ Insertion sort หรือ Merge sort อาจเร็วกว่า

QuickSort ทำงานอย่างไร?

QuickSort เลือกองค์ประกอบหนึ่งเป็น pivot สามารถเป็นองค์ประกอบใดๆ ในลิสต์ สำหรับบทช่วยสอนนี้ เราจะเลือกไอเทมสุดท้ายในลิสต์ (3)

QuickSort เปรียบเทียบค่า pivot กับทุกตัวเลขเมื่อเราวนลูปผ่านรายการในลิสต์ หากไอเทมมากกว่า pivot เราย้ายตัวเลขหลัง pivot มิฉะนั้น ย้ายตัวเลขก่อน pivot:

ค่า 3 ย้ายลงในลิสต์ของเรา รายการทั้งหมดน้อยกว่า 3 ย้ายไปซ้ายมือ ทุกค่ามากกว่า 3 ย้ายไปขวามือ

อาร์เรย์ Python ของเราแยกเป็นสองครึ่ง: ไอเทมมากกว่า pivot และไอเทมน้อยกว่า pivot

เมื่อกระบวนการเริ่มต้น Pivot ใหม่เริ่มต้นบนแต่ละครึ่งของสองครึ่ง Pivot นี้เริ่มแยกกัน และใช้อัลกอริทึมเดียวกันข้างต้น ก่อนอื่น เราจะตั้งค่า pivot เท่ากับค่าสุดท้ายในแต่ละลิสต์:

ต่อไป เราจะย้ายค่าทั้งหมดมากกว่า pivot ไปขวาของ pivot ย้ายค่าทั้งหมดน้อยกว่า pivot ไปซ้ายของ pivot

กระบวนการนี้ทำต่อจนกว่าเราจะจัดเรียงลิสต์:

อาร์เรย์สุดท้ายของเราเป็น:

ตัวอย่าง Python QuickSort

QuickSort ต้องการสองฟังก์ชัน: ฟังก์ชัน partition และฟังก์ชัน QuickSort

เริ่มต้นด้วยฟังก์ชัน partition ฟังก์ชันนี้จะ partition (เตรียม) อาร์เรย์ dựa trênค่าของ pivot element

ฟังก์ชัน partition ของเราจะ:

1. เลือก pivot element
2. ย้ายไอเทมทั้งหมดมากกว่า pivot ไปขวาของ pivot
3. ย้ายไอเทมทั้งหมดน้อยกว่า pivot ไปซ้ายของ pivot

โปรแกรม QuickSort Python

มาเขียนโปรแกรมที่นำอัลกอริทึมนี้ไปใช้:

def prepare(numbers, low, high):
    pivot = numbers[high]
    item = low - 1
    for i in range(low, high):
        if numbers[i] <= pivot:
            item = item + 1
            (numbers[item], numbers[i]) = (numbers[i], numbers[item])
    (numbers[item + 1], numbers[high]) = (numbers[high], numbers[item + 1])
    return item + 1

ก่อนอื่น เราเลือก pivot element ค่ามันเท่ากับตัวเลขสูงสุดในลิสต์ของเรา

ต่อไป เราวนลูปผ่านทุกไอเทมในลิสต์ด้วยลูป for ของ Python หากตัวเลขน้อยกว่าหรือเท่ากับ pivot จะถูกย้ายไปซ้ายของ pivot มิฉะนั้น ไปขวาของ pivot

ฟังก์ชัน Python ของเราคืนค่า high ใหม่ ค่า high ใหม่เท่ากับ item + 1

ต่อไป เราต้องรันอัลกอริทึม เราสามารถทำได้ด้วยการเขียนฟังก์ชันแยก:

def quick_sort(numbers, low, high):
    if low < high:
        pivot = prepare(numbers, low, high)
        quick_sort(numbers, low, pivot - 1)
        quick_sort(numbers, pivot + 1, high)

ฟังก์ชันนี้ตรวจสอบว่าค่า low น้อยกว่าค่า high หรือไม่ หากใช่ การจัดเรียงของเราสามารถทำต่อได้ มิฉะนั้น การจัดเรียงหยุด หากการจัดเรียงหยุด หมายถึงเราจัดเรียงลิสต์แล้ว

ต่อไป ฟังก์ชันเรียกเมธอด prepare() ระบุ pointer สำหรับ pivot และย้ายไอเทมไปตำแหน่งที่ถูกต้อง

ฟังก์ชันของเราเรียกเมธอด quick_sort() สองครั้ง ครั้งแรก เรารัน QuickSort บนองค์ประกอบทางซ้ายของ pivot ครั้งที่สอง เรารัน QuickSort บนองค์ประกอบทางขวาของ pivot ดังนั้น ฟังก์ชันของเราเป็น recursive เพราะมันเรียกตัวเอง

สิ่งนี้ทำต่อจนกว่าทุกรายการในลิสต์จะจัดเรียงแล้ว

การเขียน Main Method

มาเขียนโปรแกรมหลักที่กำหนดลิสต์ที่จะจัดเรียง:

values = [8, 4, 5, 2, 1, 3]
total_values = len(values)
quick_sort(values, 0, total_values - 1)
print(values)

ก่อนอื่น เราระบุลิสต์ค่าที่จะจัดเรียง เราใช้เมธอด len() ของ Python คำนวณความยาวลิสต์ค่าของเรา ต่อไป เราเรียกเมธอด quick_sort()

เราส่ง values เป็นตัวเลขที่ต้องการจัดเรียง เราส่ง 0 เป็น low number ความยาวของ values ลบ 1 คือ high value ที่เราระบุ high value คือความยาว values ลบ 1 เพราะไอเทมแรกในลิสต์มีหมายเลขดัชนี 0

มาลองรันโปรแกรม:

[1, 2, 3, 4, 5, 8]

โค้ดคืนลิสต์ที่จัดเรียงแล้ว! เราทำได้ เต้านั้วมือให้ตัวเอง QuickSort ไม่ง่ายต่อการเข้าใจหรือนำไปใช้

ภาพรวมความซับซ้อน (Complexity Overview)

ในเฉลี่ย อัลกอริทึมนี้ทำงานที่ O(n* log n) เกิดขึ้นเมื่อ pivot element ไม่ใช่องค์ประกอบมากที่สุดหรือน้อยที่สุด และเมื่อ pivot element ไม่อยู่ใกล้ middle element

QuickSort มี worst case complexity เป็น O(n²) เกิดขึ้นเมื่อองค์ประกอบที่เลือกเป็น pivot เป็นมากที่สุดหรือน้อยที่สุด หากเป็นเช่นนี้ pivot element จะอยู่ท้าย sorted array เสมอ สร้าง sub-arrays ที่ไม่จำเป็นหลายตัว

Best case complexity สำหรับอัลกอริทึมนี้คือ O(n* log n) เกิดขึ้นเมื่อ pivot element เท่ากับ middle element หรืออยู่ใกล้ middle element

เพื่อเรียนรู้เพิ่มเติมเกี่ยวกับความซับซ้อนของอัลกอริทึม ดูคู่มือ Big O Notation ของเรา

สรุป

Python QuickSorts ใช้ recursion แยกลิสต์เป็นลิสต์ย่อยๆ ที่จัดเรียงได้ แต่ละลิสต์จัดเรียงรอบ pivot element องค์ประกอบมากกว่า pivot ย้ายไปขวา องค์ประกอบน้อยกว่า pivot ย้ายไปซ้าย

สำหรับคำแนะนำแหล่งเรียนรู้ Python ชั้นนำ คอร์สออนไลน์ และหนังสือ อ่านคู่มือ How to Learn Python ฉบับสมบูรณ์ของเรา