Yazan : Şadi Evren ŞEKER

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
int siralimi(int *a , int boyut){
	for(int i = 0;i<boyut-1;i++)
		if(a[i]>a[i+1])
			return 0;
	return 1;
}
int permsirala (int * a, int boyut,int konum) {
            	int temp;
            	int ok = 1;
	 	if(konum <= 0){
			return siralimi(a,boyut);
            	}
 
	    printf(" konum : %dn",konum);
            for(int k =0;k< boyut;k++)
                  printf("%d " , a[k]);
            printf("n");
            for (int i = konum; i >= 0; i--){
                    temp = a[konum];
                    a[konum] = a[i];
                    a[i] = temp;
                ok = permsirala (a, boyut, konum-1);
                if (ok==1)
                    return 1;
                else {
                    temp = a[konum];
                    a[konum] = a[i];
                    a[i] = temp;
                }
            }
            return 0;
    }
int main(){
        int a[6] = {2,6,8,1,7,4};
        permsirala (a,6,5);
			printf(" nihai : " );
                        for(int k =0;k< 6;k++)
                                printf("%d " , a[k]);
                        printf("n");
        return 0;
}

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.

 

Yorumlar

  1. Özcan YARDIMCI

    Merhaba hocam; Düzeltilmiş
    1....n arasındaki sayıların permütasyonu a1,a2,a3....an olsun if i küçük j ve ai büyük aj ise (ai,aj) tersine çevrilebilir çiftlerdir. verilen permütasyon da tersine çevrilebilir çiftleri bulan java kodu nasıl yazabiliriz. teşekkür edrim. birde böl ve fethet ile algoritmasını nasıl düşünürüm

  2. Şadi Evren ŞEKERŞadi Evren ŞEKER

    Birinci kısmı için kontrol edeceğiniz durum (şayet doğru anladıysam)

    for(int i =0;i<n;i++){
       for(int j=i;j<n;j++){
          if(a[i]>a[j]){
              //bu permutasyon tersine çevirilebilir ve çift aşağıdaki şekilde bastırılabilir:
              System.out.println(a[i] + " ile " + a[j] + " cifti");
          }
       }
     }

    Bu problemi böl fethet ile yazmak için (tabi öncelikle ilgili yazıya bir bakmakta fayda olabilir: Parçala Fethet Yöntemi) öncelikle yapılan kontrolün ikili bir operatör olduğunun farkına varmak gerekiyor. Yani basitçe büyüktür (>) operatörünü kullanıyoruz. Bu durumda dizinin bir ikili ağaç (binary tree) şeklinde yerleştiğini ve ağacın her düğümünde kendinden önceki değerleri kontrol ettiğini düşünebiliriz.

    Yani önce yan yana olan sayılara bakacağız sonra her sonucu diğer komşu sonuçla karşılaştıracağız. Daha iyi anlaşılması için bir örnek üzerinden durumu anlatalım. Örneğin dizi aşağıdaki sayılardan oluşsun:

    1,2,4,5,7,8,3,4

    şimdi ilk yapacağımız iş diziyi tek eleman kalana kadar ikiye bölmek ve ardından her ikili grubu kendi içerisinde karşılaştırmak. Bu durum aşağıdaki şekilde görselleştirilebilir:

    Ardından ikilileri kendi arasında karşılaştırmamız gerekiyor. Durumu özetlemek açısından ilk karşılaştırmada kontrol edilen gruplar aşağıdaki gibidir.


    Şimdi yapılacak olan karşılaştırma bu ikililer arasında olacaktır. Yani yapılacak karşılaştırma şu şekilde düşünülebilir:

    Soru işareti olan kutuları doldurmak için sormamız gereken soru, ilk grubun büyük üyesinin, ikinci grubun küçük üyesinden küçük olup olmadığıdır. Çünkü zaten ilk aşamada iklileri kontrol ettik ve her grup için true durumunu döndürdük. O halde aslında bakılacak iki tane değer var:
    2,4 ve 8,3 karşılaştırmaları

    Örneğimizde ilk ikili için küçüklük şartı sağlanırken ikinci ikili için sağlanmamıştır. Dolayısıyla bu permütasyon için tersine çevrilebilir çiftlerdir denilebilir.

    Ancak yine de diyelim ki bu ikililer için de koşul sağlanmamış olsun ve örnek olarak matrisimizin sayılarını aşağıdaki şekilde değiştirerek bu durumu da görelim:

    7,8,9,10,1,2,4,5

    Yeni dizi için karşılaştırma sonucu ikililer için de sorunsuz olacaktı:


    Şimdi dörtlüleri karşılaştırma seviyesine geçilebilir. Yine benzer bir yaklaşımla soldaki dörtlünün en büyüğü ile sağdaki dörtlünün en küçüğünü karşılaştırmamız yeterli olacaktır:


    Sonuç olarak eleman sayısına göre problemi ikili parçalara bölerek her komşu grup için karşılaştırma yapmamız yeterlidir. Problem ikili, dörtlü, sekizli, onaltılı şeklinde grupları birbiri ile karşılaştıracak her karşılaştırmada komşu iki grup için soldakinin en büyüğü ile sağdakinini en küçüğünü karşılaştırarak ilerleyecektir.

    Performans Karşılaştırması
    ilk yaklaşımda iç içe iki döngü halinde her elemanı, kendisinden sonraki elemanlar ile karşılaştırdık. Bu durumda karşılaştırılan eleman sayısı n elemanlı bir matris için:
    1. elemanda n-1
    2. elemanda n-2
    ...
    n-1. elemanda 1
    n. elemanda 0

    olacaktır. Bu durumda 1'den n'e kadar olan sayıların toplamı olan n x (n+1) / 2 değeri kadar karşılaştırma yapılacak ve karmaşıklık analizi O(n2) olacaktır.

    ikinci yaklaşımda ise n elemanlı bir dizi için
    ilk denemede n/2
    ikinci denemede n/4
    üçüncü denemede n/8
    ...

    şeklinde karşılaştırma yapılacaktır. Toplam kaç deneme olduğu ise log2n ile bulunacaktır.

    Dolayısıyla toplam karşılaştırma sayısı log2n eleman için her deneme n/2'den küçük değerlerden oluşacak (en büyüğü n'den küçük) ve dolayısıyla karmaşıklığı O(n logn) olarak bulunacaktır.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


+ 7 = ondört