Bubble sort

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

Miriam Antona

Software engineer

อัลกอริทึมการจัดเรียง

ศึกษาอย่างละเอียด
แก้ปัญหาการจัดเรียงข้อมูลในคอลเลกชันที่ไม่เป็นระเบียบตามลำดับน้อยไปมาก/มากไปน้อย
สามารถลดความซับซ้อนของปัญหาได้
ตัวอย่างอัลกอริทึมการจัดเรียง:
- bubble sort
- selection sort
- insertion sort
- merge sort
- quicksort

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

ภาพแสดงลิสต์ที่มีตัวเลขไม่เป็นระเบียบ มีตัวชี้หนึ่งชี้ไปที่สมาชิกตัวที่สอง และอีกตัวชี้ไปที่สมาชิกตัวที่สาม โดยสมาชิกตัวที่สองและตัวที่สามได้ถูกสลับตำแหน่งกันแล้ว สมาชิกตัวสุดท้ายถูกไฮไลต์สีน้ำเงิน

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort

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

ค่าแรกมากกว่าค่าที่สอง
- สลับตำแหน่ง
ค่าที่สองมากกว่าค่าแรก
- ไม่ต้องทำอะไร

Bubble sort - การนำไปใช้

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]

Bubble sort - การนำไปใช้

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list

Bubble sort - ความซับซ้อน

กรณีแย่ที่สุด: $O(n^2)$
กรณีดีที่สุด - เวอร์ชันที่ยังไม่ปรับปรุง: $\Omega(n^2)$
กรณีดีที่สุด - เวอร์ชันที่ปรับปรุงแล้ว: $\Omega(n)$
กรณีเฉลี่ย: $\Theta(n^2)$
ประสิทธิภาพต่ำกับลิสต์ขนาดใหญ่ที่ไม่เป็นระเบียบมาก
ทำงานได้ดีกับ:
- ลิสต์ขนาดใหญ่ที่เรียงแล้วหรือเกือบเรียงแล้ว
- ลิสต์ขนาดเล็ก

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

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