Selection Sort ve Insertion Sort

Python'da Veri Yapıları ve Algoritmalar

Miriam Antona

Software engineer

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğeyi gösteren bir imleç var.

En küçük değeri belirleyin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğeyi gösteren bir imleç var. İlk öğe turuncu renkte.

En küçük değeri belirleyin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İkinci öğeyi gösteren bir imleç var. İlk öğe turuncu renkte.

En küçük değeri belirleyin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İkinci öğeyi gösteren bir imleç var. İkinci öğe turuncu renkte.

En küçük değeri belirleyin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Üçüncü öğeyi gösteren bir imleç var. İkinci öğe turuncu renkte.

En küçük değeri belirleyin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Dördüncü öğeyi gösteren bir imleç var. İkinci öğe turuncu renkte.

En küçük değeri belirleyin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Dördüncü öğeyi gösteren bir imleç var. Dördüncü öğe turuncu renkte.

En küçük değeri belirleyin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Beşinci öğeyi gösteren bir imleç var. Dördüncü öğe turuncu renkte.

En küçük değeri belirleyin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Dördüncü öğe turuncu renkte. Birinci ve dördüncü öğelerin yer değiştireceğini gösteren iki ok var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe turuncu renkte. Birinci ve dördüncü öğelerin yeri değişmiştir.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi, ikinci öğe turuncu. İkinci öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi, ikinci öğe turuncu. Üçüncü öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi, ikinci öğe turuncu. Dördüncü öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi. Üçüncü öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi. Üçüncü öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi, üçüncü öğe turuncu. Üçüncü öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi, üçüncü öğe turuncu. Dördüncü öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi, dördüncü öğe turuncu. Dördüncü öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi, dördüncü öğe turuncu. Beşinci öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi, dördüncü öğe turuncu. Üçüncü ve dördüncü öğelerin yer değiştireceğini gösteren iki ok var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi, üçüncü öğe turuncu. Üçüncü ve dördüncü öğelerin yeri değişmiştir.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi. Dördüncü öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi, dördüncü öğe turuncu. Dördüncü öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi, dördüncü öğe turuncu. Beşinci öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi, beşinci öğe turuncu. Beşinci öğeyi gösteren bir imleç var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi, beşinci öğe turuncu. Dördüncü ve beşinci öğelerin yer değiştireceğini gösteren iki ok var.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi, dördüncü öğe turuncu. Dördüncü ve beşinci öğelerin yeri değişmiştir.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci, üçüncü ve dördüncü öğeler mavi.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Tüm öğeler mavi renkte.

En küçük değeri belirleyin
En küçük değeri ilk sırasız öğe ile değiştirin

Selection sort - uygulama

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 - karmaşıklık

En kötü durum: $O(n^2)$
Ortalama durum: $\Theta(n^2)$
En iyi durum: $\Omega(n^2)$

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi, ikinci öğe diğerlerinin üstüne kaldırılmış.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi, ikinci öğe diğerlerinin üstüne kaldırılmış. İlk öğe sağa kaydırılmış.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İkinci öğe mavi. Yükseltilen öğe artık ilk konumda.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk ve ikinci öğeler mavi. Üçüncü öğe diğerlerinin üstüne kaldırılmış.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi. Üçüncü öğe diğerlerinin üstüne kaldırılmış.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi. Üçüncü öğe diğerlerinin üstüne kaldırılmış. Üçüncü öğe sağa kaydırılmış.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi. Üçüncü öğe diğerlerinin üstüne kaldırılmış. Üçüncü ve ikinci öğeler sağa kaydırılmış.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci ve üçüncü öğeler mavi. Üçüncü öğe diğerlerinin üstüne kaldırılmış. Üçüncü, ikinci ve üçüncü öğeler sağa kaydırılmış.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci, üçüncü ve dördüncü öğeler mavi.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci, üçüncü ve dördüncü öğeler mavi. Beşinci öğe diğerlerinin üstüne kaldırılmış.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci, üçüncü ve dördüncü öğeler mavi. Beşinci öğe diğerlerinin üstüne kaldırılmış. Dördüncü öğe sağa kaydırılmış.

Insertion sort

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk, ikinci, üçüncü ve dördüncü öğeler mavi. Beşinci öğe diğerlerinin üstüne kaldırılmış. Yükseltilen öğe artık dördüncü konumda.

Insertion sort - uygulama

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 - karmaşıklık

En kötü durum: $O(n^2)$
Ortalama durum: $\Theta(n^2)$
En iyi durum: $\Omega(n)$

Ayo berlatih!

Python'da Veri Yapıları ve Algoritmalar