Python Cartesian Tree Sort Algoritması

Herkese merhaba, Python yazılarımıza kaldığımız yerden devam ediyoruz. Bu yazımızda sıralama algoritmalarından biri olan Cartesian Tree Sort Algoritması’nı anlatacağım. Hadi başlayalım !

Cartesian Tree Sort Algoritması

Cartesian Tree, bir dizi içindeki elemanların bir ağaç şeklinde düzenlendiği bir veri yapısıdır. Bu ağacın her bir düğümü, kökten itibaren sırayla gelen elemanların bir alt dizisi ile eşleştirilir. Yani, her düğüm, altındaki elemanların hepsinden daha küçük bir anahtar değere sahiptir.

Cartesian Tree oluşturmak için, öncelikle bir dizi içindeki en küçük elemanı bulunur ve bu elemanın kök düğümü olduğu bir ağaç oluşturulur. Sonra, dizinin geri kalan elemanları, bu ağaca eklenecek yeni düğümler olarak ele alınır. Her bir yeni eleman, önceden oluşturulmuş ağaç içinde uygun bir konuma yerleştirilir. Bu konum, yeni elemanın anahtarının, ebeveyn düğümün anahtarından küçük olması şartıyla belirlenir.

Cartesian Tree Sort, bir dizi içindeki elemanları sıralamak için Cartesian Tree kullanır. Öncelikle, Cartesian Tree oluşturulur ve ardından ağaç simetrik sıraya göre gezilerek elemanlar sıralanır.

Sıralama işlemi, ağacın simetrik sırasına uygun olarak bir düğümden başlayarak yapılır. İlk olarak, sol alt alt ağaca gitmeye başlanır ve burada aynı işlem tekrarlanır. Sol alt alt ağaçta sıralama işlemi tamamlandığında, düğümün anahtar değeri yazdırılır ve ardından sağ alt alt ağaca geçilir. Sağ alt alt ağaçta da aynı işlem tekrarlanır ve düğümün anahtar değeri yazdırılır.

Python Kod Örnekleri

Aşağıda, Cartesian Tree Sort algoritması için Python kod örnekleri yer almaktadır. İlk olarak, Cartesian Tree oluşturmak için gereken sınıfı tanımlayacağız.

class CartesianTreeNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

Daha sonra, Cartesian Tree oluşturmak için gerekli olan işlevi tanımlayacağız.

def build_cartesian_tree(arr):
    stack = []
    for i in range(len(arr)):
        node = CartesianTreeNode(arr[i], i)
        while len(stack) > 0 and stack[-1].key > node.key:
            node.left = stack.pop()
            if len(stack) > 0:
                stack[-1].right = node
                stack.append(node)
    return stack[0]

Kod Açıklamaları

Bu işlev, bir dizi alır ve bu diziyi kullanarak Cartesian Tree oluşturur. İlk olarak, her eleman için bir düğüm oluşturulur ve bu düğümler bir yığın (stack) içinde saklanır. Yığın, ağacın oluşturulması sırasında kullanılacak bir veri yapısıdır.

Sonra, dizi içindeki elemanlar yavaş yavaş işlenir ve her eleman için bir düğüm oluşturulur. Bu düğümün sol alt ağacına gitmek için, yığın içindeki tüm düğümlerden daha büyük olan düğümler çıkartılır ve son olarak çıkartılan düğüm, yeni düğümün sol çocuğu olarak atanır.

Daha sonra, yeni düğümün sağ çocuğu olarak, yığın içindeki en son düğüm atanır. Bu, yeni düğümün ebeveyn düğümüdür.Son olarak, yığın içindeki yeni düğüm eklenir ve işlem, bir sonraki eleman için tekrarlanır. Bu şekilde, tüm elemanlar ağaca eklenir ve Cartesian Tree oluşturulur.

Tüm Kodlar

Şimdi, Cartesian Tree Sort algoritması için gereken işlevi tanımlayalım.

def cartesian_tree_sort(arr):
    root = build_cartesian_tree(arr)
    result = []
    stack = [root]
    while len(stack) > 0:
        node = stack.pop()
        result.append(arr[node.value])
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)
    return result

Bu işlev, bir dizi alır ve bu diziyi sıralamak için Cartesian Tree Sort algoritmasını kullanır. İlk olarak, Cartesian Tree oluşturulur ve ağaç simetrik sıraya göre gezilir.

Sıralama işlemi, bir yığın (stack) kullanarak gerçekleştirilir. İlk olarak, yığına ağacın kök düğümü eklenir. Daha sonra, yığın içindeki son düğüm çıkartılır ve düğümün anahtar değeri sonuç dizisine eklenir.

Sonra, düğümün sol ve sağ çocukları yığına eklenir. Bu, ağacın simetrik sırasına uygun olarak gerçekleştirilir. Sol alt ağaçtan başlanarak sıralama işlemi yapılır ve ardından sağ alt ağaca geçilir.

İşlem, yığın içinde düğüm kalmayana kadar tekrarlanır ve sonuç dizisi sıralı bir şekilde döndürülür.

Örnek Kullanım

Şimdi, Cartesian Tree Sort algoritmasını bir örnek ile gösterelim.

arr = [5, 2, 7, 1, 8, 6, 3, 9, 4]
result = cartesian_tree_sort(arr)
print(result)

Bu örnekte, Cartesian Tree Sort algoritması, bir dizi içindeki elemanları sıralamak için kullanılmıştır. Algoritma, öncelikle her eleman için bir düğüm oluşturarak Cartesian Tree oluşturur.

Daha sonra, ağaç simetrik sıraya göre gezilir ve düğümler bir yığın içinde saklanır. Son olarak, yığın içindeki elemanlar çıkartılır ve sonuç dizisine eklenir.

Sonuç

Cartesian Tree Sort algoritması, en kötü durumda O(n log n) zaman karmaşıklığına sahiptir. Bu nedenle, daha hızlı sıralama algoritmaları mevcuttur. Ancak, bu algoritma, özellikle küçük boyutlu diziler için oldukça etkilidir.

Evet Python’da Cartesian Tree Sort Algoritması bu şekilde yazılmakta. Tüm Python yazılarımıza buraya, diğer sıralama algoritmaları ile ilgili yazılarımıza buraya tıklayarak ulaşabilirsiniz. Herkese hayırlı günler.