Selection Sort และ Insertion Sort

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

Miriam Antona

Software engineer

Selection sort

• หาค่าที่น้อยที่สุด

Selection sort

• หาค่าที่น้อยที่สุด

Selection sort

• หาค่าที่น้อยที่สุด

Selection sort

• หาค่าที่น้อยที่สุด

Selection sort

• หาค่าที่น้อยที่สุด

Selection sort

• หาค่าที่น้อยที่สุด

Selection sort

• หาค่าที่น้อยที่สุด

Selection sort

• หาค่าที่น้อยที่สุด

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

Selection sort

• หาค่าที่น้อยที่สุด
• สลับค่าที่น้อยที่สุดกับสมาชิกตัวแรกที่ยังไม่เรียง

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

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

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list

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

• กรณีเลวร้ายที่สุด: $O(n^2)$
• กรณีเฉลี่ย: $\Theta(n^2)$
• กรณีดีที่สุด: $\Omega(n^2)$

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

Insertion sort

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

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list

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

• กรณีเลวร้ายที่สุด: $O(n^2)$
• กรณีเฉลี่ย: $\Theta(n^2)$
• กรณีดีที่สุด: $\Omega(n)$

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

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