Quicksort

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Miriam Antona

Software engineer

Quicksort

  • ใช้หลักการ แบ่งแล้วเอาชนะ
  • นำไปใช้ในภาษาโปรแกรมมิ่งหลายภาษา
  • เทคนิคการแบ่งพาร์ทิชัน
    • Pivot
    • ค่าที่น้อยกว่า pivot -> ซ้าย
    • ค่าที่มากกว่า pivot -> ขวา
  • สมาชิกทางซ้ายจะถูกเรียงลำดับแบบเรียกซ้ำ
  • สมาชิกทางขวาจะถูกเรียงลำดับแบบเรียกซ้ำ
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ โดยสมาชิกตัวแรกแสดงเป็นสีน้ำเงิน

  • การแบ่งพาร์ทิชันแบบ Hoare
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน มีตัวชี้สองตัว ตัวชี้ซ้ายชี้ที่สมาชิกตัวที่ 2 และตัวชี้ขวาชี้ที่สมาชิกตัวสุดท้าย

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน มีตัวชี้สองตัว ตัวชี้ซ้ายชี้ที่สมาชิกตัวที่ 3 และตัวชี้ขวาชี้ที่สมาชิกตัวสุดท้าย

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน มีตัวชี้สองตัว ตัวชี้ซ้ายชี้ที่สมาชิกตัวที่ 3 และตัวชี้ขวาชี้ที่สมาชิกตัวที่ 5

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน มีตัวชี้สองตัว ตัวชี้ซ้ายชี้ที่สมาชิกตัวที่ 3 และตัวชี้ขวาชี้ที่สมาชิกตัวที่ 5 มีลูกศรแสดงว่าสมาชิกตัวที่ 3 และตัวที่ 5 จะถูกสลับกัน

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน มีตัวชี้สองตัว ตัวชี้ซ้ายชี้ที่สมาชิกตัวที่ 3 และตัวชี้ขวาชี้ที่สมาชิกตัวที่ 5 สมาชิกตัวที่ 3 และตัวที่ 5 ถูกสลับกันแล้ว

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน มีตัวชี้สองตัว ตัวชี้ซ้ายชี้ที่สมาชิกตัวที่ 4 และตัวชี้ขวาชี้ที่สมาชิกตัวที่ 5

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน มีตัวชี้สองตัว ตัวชี้ซ้ายและตัวชี้ขวาต่างชี้ที่สมาชิกตัวที่ 4

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน มีตัวชี้สองตัว ตัวชี้ซ้ายชี้ที่สมาชิกตัวที่ 4 และตัวชี้ขวาชี้ที่สมาชิกตัวที่ 3

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน มีตัวชี้สองตัว ตัวชี้ซ้ายชี้ที่สมาชิกตัวที่ 4 และตัวชี้ขวาชี้ที่สมาชิกตัวที่ 3 มีลูกศรแสดงว่าสมาชิกตัวที่ 1 และตัวที่ 3 จะถูกสลับกัน

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 3 สีน้ำเงิน สมาชิกตัวที่ 1 และตัวที่ 3 ถูกสลับกันแล้ว

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 3 แสดงเป็นสีเขียว

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 3 สีเขียว และสมาชิก 2 ตัวแรกสีส้ม แสดงถึงส่วนซ้ายของลิสต์

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน สมาชิกตัวที่ 2 สีส้ม สมาชิกตัวที่ 3 สีเขียว ตัวชี้ซ้ายและตัวชี้ขวาต่างชี้ที่สมาชิกตัวที่ 2

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน สมาชิกตัวที่ 2 สีส้ม สมาชิกตัวที่ 3 สีเขียว ตัวชี้ซ้ายและตัวชี้ขวาต่างชี้ที่สมาชิกตัวที่ 2 มีลูกศรแสดงว่าสมาชิกตัวที่ 1 และตัวที่ 2 จะถูกสลับกัน

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีน้ำเงิน สมาชิกตัวที่ 2 สีส้ม สมาชิกตัวที่ 3 สีเขียว ตัวชี้ซ้ายและตัวชี้ขวาต่างชี้ที่สมาชิกตัวที่ 2 สมาชิกตัวที่ 1 และตัวที่ 2 ถูกสลับกันแล้ว

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวแรกสีส้ม สมาชิกตัวที่ 2 และตัวที่ 3 สีเขียว

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 1, 2 และ 3 แสดงเป็นสีเขียว

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 1, 2 และ 3 สีเขียว ส่วนขวาของลิสต์แสดงเป็นสีส้ม

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 1, 2 และ 3 สีเขียว สมาชิกตัวแรกของส่วนขวาสีน้ำเงิน ตัวชี้ซ้ายชี้ที่สมาชิกตัวที่ 2 ของส่วนขวา และตัวชี้ขวาชี้ที่สมาชิกตัวสุดท้ายของส่วนขวา

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 1, 2 และ 3 สีเขียว สมาชิกตัวแรกของส่วนขวาสีน้ำเงิน ตัวชี้ซ้ายและตัวชี้ขวาต่างชี้ที่สมาชิกตัวที่ 2 ของส่วนขวา

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 1, 2 และ 3 สีเขียว สมาชิกตัวแรกของส่วนขวาสีน้ำเงิน ตัวชี้ซ้ายชี้ที่สมาชิกตัวแรกของส่วนขวา และตัวชี้ขวาชี้ที่สมาชิกตัวที่ 2 ของส่วนขวา

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 1, 2, 3 และ 4 สีเขียว สมาชิกตัวที่ 5 และ 6 สีส้ม

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 1, 2, 3 และ 4 สีเขียว สมาชิกหนึ่งตัวสีน้ำเงิน ตัวชี้ซ้ายและตัวชี้ขวาต่างชี้ที่สมาชิกตัวสุดท้าย

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 1, 2, 3 และ 4 สีเขียว สมาชิกหนึ่งตัวสีน้ำเงิน ตัวชี้ซ้ายและตัวชี้ขวาต่างชี้ที่สมาชิกตัวสุดท้าย มีลูกศรแสดงว่าสมาชิกตัวที่ 5 และตัวที่ 6 จะถูกสลับกัน

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกตัวที่ 1, 2, 3 และ 4 สีเขียว สมาชิกหนึ่งตัวสีน้ำเงิน ตัวชี้ซ้ายและตัวชี้ขวาต่างชี้ที่สมาชิกตัวสุดท้าย สมาชิกตัวที่ 5 และตัวที่ 6 ถูกสลับกันแล้ว

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ตัวอย่างการทำงาน

ภาพแสดงลิสต์ที่มีตัวเลขไม่เรียงลำดับ สมาชิกทุกตัวแสดงเป็นสีเขียว เนื่องจากเรียงลำดับเรียบร้อยแล้ว

  • การแบ่งพาร์ทิชันแบบ Hoare
    • เลื่อนตัวชี้ซ้ายจนพบค่าที่มากกว่า pivot
    • เลื่อนตัวชี้ขวาจนพบค่าที่น้อยกว่า pivot
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - การ implement

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - การ implement

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - การ implement

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Quicksort - ความซับซ้อน

  • กรณีเลวร้ายที่สุด: $O(n^2)$
  • มีประสิทธิภาพสูง!
    • กรณีเฉลี่ย: $\Theta(n\log{}n)$
    • กรณีดีที่สุด: $\Omega(n\log{}n)$
  • ความซับซ้อนเชิงพื้นที่: $O(n\log{}n)$
โครงสร้างข้อมูลและอัลกอริทึมใน Python

มาฝึกกันเถอะ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Preparing Video For Download...