Selection Sort dan Insertion Sort

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Selection sort

• Tentukan nilai terendah

Selection sort

• Tentukan nilai terendah

Selection sort

• Tentukan nilai terendah

Selection sort

• Tentukan nilai terendah

Selection sort

• Tentukan nilai terendah

Selection sort

• Tentukan nilai terendah

Selection sort

• Tentukan nilai terendah

Selection sort

• Tentukan nilai terendah

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort

• Tentukan nilai terendah
• Tukar nilai terendah dengan elemen tak terurut pertama

Selection sort - implementasi

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 - kompleksitas

• Kasus terburuk: $O(n^2)$
• Rata-rata: $\Theta(n^2)$
• Kasus terbaik: $\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 - implementasi

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 - kompleksitas

• Kasus terburuk: $O(n^2)$
• Rata-rata: $\Theta(n^2)$
• Kasus terbaik: $\Omega(n)$

Ayo berlatih!

Struktur Data dan Algoritma di Python