Quicksort

Python'da Veri Yapıları ve Algoritmalar

Miriam Antona

Software engineer

Quicksort

Böl ve fethet ilkesini uygular
Birçok programlama dilinde kullanılır
Bölümleme tekniği
- Pivot
- pivotdan küçük öğeler -> sol
- pivotdan büyük öğeler -> sağ
Sol taraf özyinelemeli sıralanır
Sağ taraf özyinelemeli sıralanır

Quicksort - uygulama

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

Quicksort - uygulama

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

Hoare bölümleme

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi renkte. İki imleç var. Sol imleç ikinci öğeyi, sağ imleç son öğeyi gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi renkte. İki imleç var. Sol imleç üçüncü öğeyi, sağ imleç son öğeyi gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi renkte. İki imleç var. Sol imleç üçüncü öğeyi, sağ imleç beşinci öğeyi gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi renkte. İki imleç var. Sol imleç üçüncü öğeyi, sağ imleç beşinci öğeyi gösteriyor. Üçüncü ve beşinci öğelerin yer değiştireceğini gösteren iki ok var.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi renkte. İki imleç var. Sol imleç dördüncü öğeyi, sağ imleç beşinci öğeyi gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi renkte. İki imleç var. Sol ve sağ imleç dördüncü öğeyi gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi renkte. İki imleç var. Sol imleç dördüncü öğeyi, sağ imleç üçüncü öğeyi gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi renkte. İki imleç var. Sol imleç dördüncü öğeyi, sağ imleç üçüncü öğeyi gösteriyor. Birinci ve üçüncü öğelerin yer değiştireceğini gösteren iki ok var.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Üçüncü öğe mavi renkte. Birinci ve üçüncü öğeler yer değiştirmiş.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Üçüncü öğe yeşil renkte.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Üçüncü öğe yeşil, ilk iki öğe turuncu renkte; listenin sol kısmını temsil ediyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi, ikinci turuncu, üçüncü yeşil. Sol ve sağ imleç ikinci öğeyi gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi, ikinci turuncu, üçüncü yeşil. Sol ve sağ imleç ikinci öğeyi gösteriyor. Birinci ve ikinci öğelerin yer değiştireceğini gösteren iki ok var.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. İlk öğe mavi, ikinci turuncu, üçüncü yeşil. Sol ve sağ imleç ikinci öğeyi gösteriyor. Birinci ve ikinci öğeler yer değiştirmiş.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

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

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Birinci, ikinci ve üçüncü öğeler yeşil renkte.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Birinci, ikinci ve üçüncü öğeler yeşil. Listenin sağ kısmı turuncu renkte.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Birinci, ikinci ve üçüncü öğeler yeşil. Sağ kısmın ilk öğesi mavi. Sol imleç sağ kısmın ikinci öğesini, sağ imleç sağ kısmın son öğesini gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Birinci, ikinci ve üçüncü öğeler yeşil. Sağ kısmın ilk öğesi mavi. Sol ve sağ imleç listenin sağ kısmının ikinci öğesini gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Birinci, ikinci ve üçüncü öğeler yeşil. Sağ kısmın ilk öğesi mavi. Sol imleç sağ kısmın ilk öğesini, sağ imleç ikinci öğesini gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Birinci, ikinci, üçüncü ve dördüncü öğeler yeşil, beşinci ve altıncı öğeler turuncu renkte.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Birinci, ikinci, üçüncü ve dördüncü öğeler yeşil. Bir öğe mavi renkte. Sol ve sağ imleç son öğeyi gösteriyor.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Birinci, ikinci, üçüncü ve dördüncü öğeler yeşil. Bir öğe mavi renkte. Sol ve sağ imleç son öğeyi gösteriyor. Beşinci ve altıncı öğelerin yer değiştireceğini gösteren iki ok var.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama

Sırasız sayılardan oluşan bir listenin şematik gösterimi. Tüm öğeler sıralandığı için yeşil renkte.

Hoare bölümleme
- Pivotdan büyük bir değer bulunana kadar sol imleci ilerletin
- Pivotdan küçük bir değer bulunana kadar sağ imleci geri alın

Quicksort - uygulama kodu

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)

Quicksort - uygulama kodu

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer

Quicksort - uygulama kodu

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]

Quicksort - karmaşıklık

En kötü durum: $O(n^2)$
Çok verimli!
- Ortalama durum: $\Theta(n\log{}n)$
- En iyi durum: $\Omega(n\log{}n)$
Uzay karmaşıklığı: $O(n\log{}n)$

Hadi pratik yapalım!

Python'da Veri Yapıları ve Algoritmalar