Python ile pratik sıralama

Geçen hafta bir sıralama algoritmasının içini görmek için insertion sort’u kendimiz yazdık. Gerçek programlarda ise sıralama algoritmasını çoğu zaman kendimiz yazmayız. Python’la birlikte gelen, iyi test edilmiş yerleşik araçları kullanırız.

Bu hafta sorted(), list.sort(), key, reverse ve çok ölçütlü sıralamayı öğreneceğiz. Python’ın sıralaması kararlıdır (stable). Bunun ne işe yaradığını da göreceğiz.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

• sorted() ile list.sort() arasındaki davranış farkını açıklayabilmeli,
• Artan ve azalan sıralama yapabilmeli,
• key parametresiyle kayıtları istediğiniz alana göre sıralayabilmeli,
• Kısa lambda ifadelerini okunabilir biçimde kullanabilmeli,
• Birden fazla ölçüte göre sıralayabilmeli,
• Kararlı sıralamanın eşit anahtarlı kayıtlara etkisini açıklayabilmeli,
• Sıralarken orijinal listenin değişip değişmemesi gerektiğine karar verebilmelisiniz.

2 sorted() yeni bir liste döndürür

sorted() verilen listeye dokunmaz. Sıralanmış hâlini yeni bir liste olarak döndürür, orijinal liste eski sırasıyla kalır.

3 list.sort() mevcut listeyi değiştirir

list.sort() listeyi yerinde (in-place) değiştirir ve None döndürür.

Warning

Şu satır sık yapılan bir hatadır:

ordered = numbers.sort()

Burada ordered sıralı liste değil, None olur. Yeni bir liste istiyorsanız ordered = sorted(numbers) kullanın.

4 Azalan sıralama

reverse=True, sıralama yönünü tersine çevirir.

5 String sıralaması

String’ler karakter karakter, her karakterin kod değerine göre karşılaştırılır. Bu yüzden büyük ve küçük harfler karışınca ya da Türkçe karakterler (ç, ğ, ı, ö, ş, ü) girince sonuç, alfabe sırasından beklediğinizle aynı olmayabilir. Dile göre (locale tabanlı) sıralamayı bu derste ayrıntılı işlemeyeceğiz.

6 key: neye göre sıralıyoruz?

Sözlüklerden oluşan bir listeyi sıralarken Python’a her kayıtta hangi alana bakacağını söyleriz. Bunun için key parametresine bir anahtar fonksiyonu veririz:

Buradaki lambda ifadesi (tek satırlık, adsız bir fonksiyon) şu soruyu cevaplar:

Her kayıt için karşılaştırmada hangi değeri kullanayım?

Bu örnekte cevap student["grade"] değeridir.

7 Lambda yerine normal fonksiyon

lambda yazmak zorunda değilsiniz. Aynı işi normal bir fonksiyon da görür:

Kural uzadıkça normal fonksiyon daha kolay okunabilir. Biz lambda’yı tek ifadelik kısa anahtarlar için kullanacağız.

8 Nota göre azalan sıralama

9 Alıştırma: ürünleri fiyata göre sırala

Ürünleri price alanına göre küçükten büyüğe sıralayıp ordered değişkenine atayın.

Beklenen sıra:

['Silgi', 'Kalem', 'Defter', 'Çanta']

key fonksiyonu her ürün için price değerini döndürmelidir.

ordered = sorted(products, key=lambda product: product["price"])

10 Çok ölçütlü sıralama

Öğrencileri önce bölüme, aynı bölümdekileri de nota göre sıralamak istiyoruz. Bunun için key bir tuple döndürebilir:

Tuple karşılaştırması soldan sağa ilerler:

1. Önce department,
2. Eşitse grade.

11 Bir ölçüt artan, diğeri azalan olsun

Sayısal bir ölçütün yönünü ters çevirmek için başına eksi koyabilirsiniz:

Burada bölüm artan, not ise bölüm içinde azalan sıralanır.

12 Kararlı sıralama ne işe yarar?

Python’ın yerleşik sıralaması kararlıdır (stable): anahtarı eşit olan elemanlar, sıralamadan önceki sıralarını korur.

80 alan Ayşe listede Cem’den önceydi. Anahtarları eşit olduğu için sıralamadan sonra da Cem’den önce geliyor. 90 alan Bora ile Deniz için de durum aynı.

Kararlılık sayesinde birden fazla ölçüte göre sıralamayı art arda sıralamalarla da yapabiliriz. Önce ikincil ölçüte, sonra birincil ölçüte göre sıralarız:

Çoğu zaman tek bir tuple anahtarı daha sadedir; bu örneği kararlılığın etkisini göstermek için verdik.

13 operator.itemgetter

Sözlükten ya da tuple’dan bir alanı seçmek için standart kütüphanedeki itemgetter da kullanılabilir:

Bu derste lambda yeterli. itemgetter’ı bir kodda gördüğünüzde tanımanız yeter.

14 Orijinal veri değişsin mi?

Sıralamadan önce kendinize şunu sorun:

Sıralama sonucunda mevcut listenin düzeni değişmeli mi?

• Evet → list.sort() kullanabilirsiniz,
• Hayır, orijinal sıra da lazım → sorted() daha güvenlidir.

Aliasing’e (iki değişkenin aynı listeyi göstermesine) dikkat edin:

İki değişken aynı listeyi gösterdiği için değişikliği ikisinde de görürsünüz.

15 Yerleşik sıralama neden tercih edilir?

Gerçek programlarda sorted() ve .sort() şu yüzden tercih edilir:

• İyi test edilmişlerdir,
• Karşılaştırılabilen her türden veriyi sıralayabilirler,
• key ve reverse ile ölçütü ve yönü seçmek kolaydır,
• Elle yazılan temel sıralamalardan çok daha hızlı çalışabilirler.

Geçen hafta insertion sort’u yerleşik araçların yerine kullanmak için yazmadık. Amacımız bir sıralama algoritmasının nasıl çalıştığını görmekti.

16 Kavram köşesi: öncelik kuyruğu ve heap

Bazı problemlerde bütün veriyi sıralamaya gerek yoktur. Her seferinde yalnızca en öncelikli elemanı (en küçüğü ya da en büyüğü) almak isteriz. Acil serviste de böyledir: kim önce geldiyse değil, durumu en ağır olan hasta önce alınır. Öncelik kuyruğu (priority queue) bu iş için tanımlanmış bir soyut veri türüdür. Heap ise öncelik kuyruğunu kodlamak için yaygın kullanılan bir veri yapısıdır.

Bu derste heap yazmayacağız, heapq modülünün ayrıntılarına da girmeyeceğiz. Aklınızda şu kalsın:

Bütün listeyi sıralamak ile her seferinde en öncelikli elemanı seçmek ayrı problemlerdir.

17 Bölüm özeti

• sorted() yeni bir sıralı liste döndürür.
• list.sort() mevcut listeyi yerinde değiştirir ve None döndürür.
• key, kayıtların hangi değere göre karşılaştırılacağını belirler.
• reverse=True sıralama yönünü tersine çevirir.
• Tuple döndüren bir key ile birden fazla ölçüte göre sıralanabilir.
• Python’ın sıralaması kararlıdır.
• Gerçek programlarda elle sıralama algoritması yazmak yerine yerleşik araçlar kullanılır.

18 Kendinizi kontrol edin

1. sorted(values) ile values.sort() arasındaki iki temel fark nedir?
2. key parametresi ne işe yarar?
3. (department, grade) anahtarı hangi sırayla karşılaştırılır?
4. Kararlı sıralama neyi korur?
5. Orijinal sırayı daha sonra kullanmanız gerekiyorsa hangi sıralama yaklaşımı daha güvenlidir?