Kabarcık sıralama

Python'da Veri Yapıları ve Algoritmalar

Miriam Antona

Software engineer

Sıralama algoritmaları

{{1}} derinlemesine incelenir
Sıralanmamış bir koleksiyonu artan/azalan düzende nasıl sıralayacağınızı çözer
Sorunların karmaşıklığını azaltabilir
Bazı sıralama algoritmaları:
- bubble sort
- selection sort
- insertion sort
- merge sort
- quicksort

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Bir işaretçi ilk öğeyi, diğeri ikinci öğeyi gösteriyor.

İlk değer ikinciden büyükse

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Bir işaretçi ilk öğeyi, diğeri ikinci öğeyi gösteriyor. İlk ve ikinci öğeler yer değiştirmiş.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İkinci öğeyi gösteren bir işaretçi ve üçüncü öğeyi gösteren başka bir işaretçi var.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Üçüncü öğeyi gösteren bir işaretçi ve dördüncü öğeyi gösteren başka bir işaretçi var.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Üçüncü öğeyi gösteren bir işaretçi ve dördüncü öğeyi gösteren başka bir işaretçi var. Üçüncü ve dördüncü öğeler yer değiştirmiş.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Dördüncü öğeyi gösteren bir işaretçi ve beşinci öğeyi gösteren başka bir işaretçi var.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Dördüncü öğeyi gösteren bir işaretçi ve beşinci öğeyi gösteren başka bir işaretçi var. Dördüncü ve beşinci öğeler yer değiştirmiş.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Dördüncü öğeyi gösteren bir işaretçi ve beşinci öğeyi gösteren başka bir işaretçi var. Beşinci öğe sıralı olduğu için mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Bir işaretçi ilk öğeyi, diğeri ikinci öğeyi gösteriyor. Son öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İkinci öğeyi gösteren bir işaretçi ve üçüncü öğeyi gösteren başka bir işaretçi var. Son öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İkinci öğeyi gösteren bir işaretçi ve üçüncü öğeyi gösteren başka bir işaretçi var. İkinci ve üçüncü öğeler yer değiştirmiş. Son öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Üçüncü öğeyi gösteren bir işaretçi ve dördüncü öğeyi gösteren başka bir işaretçi var. Son öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Üçüncü öğeyi gösteren bir işaretçi ve dördüncü öğeyi gösteren başka bir işaretçi var. Son iki öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Bir işaretçi ilk öğeyi, diğeri ikinci öğeyi gösteriyor. Son iki öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Bir işaretçi ilk öğeyi, diğeri ikinci öğeyi gösteriyor. İlk ve ikinci öğeler yer değiştirmiş. Son iki öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İkinci öğeyi gösteren bir işaretçi ve üçüncü öğeyi gösteren başka bir işaretçi var. Son iki öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İkinci öğeyi gösteren bir işaretçi ve üçüncü öğeyi gösteren başka bir işaretçi var. Son üç öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Bir işaretçi ilk öğeyi, diğeri ikinci öğeyi gösteriyor. Son üç öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Bir işaretçi ilk öğeyi, diğeri ikinci öğeyi gösteriyor. Son dört öğe mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Bir işaretçi ilk öğeyi, diğeri ikinci öğeyi gösteriyor. Tüm öğeler mavi renkte.

İlk değer ikinciden büyükse
- Yer değiştirin
İkinci değer birinciden büyükse
- Hiçbir şey yapmayın

Kabarcık sıralama - uygulama

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]

Kabarcık sıralama - uygulama

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

Kabarcık sıralama - karmaşıklık

En kötü durum: $O(n^2)$
En iyi durum - geliştirilmeyen sürüm: $\Omega(n^2)$
En iyi durum - geliştirilmiş sürüm: $\Omega(n)$
Ortalama durum: $\Theta(n^2)$
Çok sırasız büyük listelerde iyi değildir
İyi olduğu durumlar:
- büyük sıralı/neredeyse sıralı listeler
- küçük listeler

Hadi pratik yapalım!

Python'da Veri Yapıları ve Algoritmalar