Çevrimdışı

Bu yazının amacı, permütasyon sıralaması (permutation sort) olarak bilinen sıralama algoritmasını (sorting algorithm) açıklamaktır. Algoritma asılnda oldukça basit bir yapıya sahiptir. Basitçe bir sayı dizisinin bütün permütasyonları sırasıyla denenir ve bunlardan birisinin sıralı olarak bulunması halinde algoritma sona erer.

Algoritmayı basitçe aşağıdaki adımlar şeklinde yazmak mümkündür:

Dizi sıralı olana kadar,
Dizinin permütasyonunu al
Bu durumu aşağıdaki kod ile gerçeklemek mümkündür. Örneğin, sıralamak istediğimiz dizi aşağıdaki şekilde verilmiş olsun:

2 6 8 1
Bu dizinin permütasyonları alınarak sıralanmış olana kadar permütasyon işlemi devam ettirilir, bu sayı n! ile hesaplandığına göre 4 elemanlı dizi için 4! = 24 ihtimal bulunmaktadır. Bu ihtimaller sırasıyla işlenir:
2 6 8 1
2 8 6 1
2 6 8 1
8 6 2 1
2 6 8 1
2 6 1 8
2 1 6 8
1 2 6 8
Yukarıdaki permütasyonlardan sonuncusu sıralanmış halidir dolayısıyla çalışma durdurulur.
Yukarıdaki algoritmanın C dilinde kodlanmış hali aşağıdaki şekildedir:


Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir.


Yukarıdaki kodda, siralimi fonksiyonu, basitçe bir dizide bulunan elemanları baştan sona kontrol etmektedir. Bu kontrol sırasında dizideki herhangi bir eleman, sağındaki elemandan büyükse, olumsuz, şayet bütün elemanlar küçükse olumlu sonuç döndürmektedir.
İkinci fonksiyonumuz olan permsirala fonksiyonu ise, dizinin bütün alternatif permütasyonlarını oluşturmaktadır. Bu sırada diziyi ve boyutunu parametre aldığı gibi, özyineli (recursive) olarak çalışıtğı için en son kaldığı konumu da üçüncü bir parametre olarak almaktadır.
Ayrıca her permütasyon ihtimalini denedikten sonra dizinin sıralı olup olmadığını da kontrol etmektedir.

Alıntı