N elemanlı bir dizinin artan ve ya azalan şekilde sıralanması için kullanılan Bubble Sort, Insertion Sort, Selection Sort Algoritmaları kullanıldığın da ikinci dereceden bir zaman karmaşıklığına O(N2) sahip olduğunu görmüştük.

Makalede N elemanlı bir dizide belirli farklı konumları değiştirerek bunlara alternatif bir sıralama algoritması olan Avi Sort anlatılmıştır.

Bir dizinin veri elemanlarını artan veya azalan düzende düzenleme işlemine sıralama [1] denir.

Sıralama için kullanılan algoritmalara göre zaman karmaşıklığı değişir.

2019-05-27_17-58-02.png

Bu makalede, bir dizinin veri öğelerini artan / azalan şekilde yeniden düzenleyebilen Avi Sort’u anlatılmıştır.

  • Avi sort, baloncuk sıralama algoritması olarak çalışır.
  • Avi sıralama kullanarak, her adımda dizinin en ağır elemanı en sona ve ikinci aşamada dizinin en ağır ikinci elemanı ikinci son konuma yerleştirilir ve tüm adımlar aynı şekilde devam eder.
  • Bundan sonra çıktı olarak sıralanmış bir dizi elde ederiz.
  • Temel sebep, Avi Sort’u en kötü durumda O (N2) zamanında, en iyi durumda O (N) sıralayabilen daha etkili bir algoritma olarak sunmaktır.
  • Zaman karmaşıklığı O (N log2N) ve O (N) bazı algoritmalar var, ancak bunlar RAM’in modeline / Karşılaştırma yöntemine dayanmıyor.
  • Verileri artan veya azalan düzende sıralayan birçok sıralama algoritması vardır.
  • Avi sort algoritması, bubble sorta benzer. Avi sort, veri öğelerini belirli alternatif konumlarını değiştirerek değiştirir.
  • Elemanları sıralanacak N elemanlı bir A dizisi olduğunu düşünelim. A(N)
  • 1. adımda A [1], A [3] ile karşılaştırılır ve gerekirse değiştirilir.
  • A [2], A [4] ile karşılaştırılır ve gerekirse değiştirilir.
  • A [3], A [5] ile karşılaştırılır ve gerekirse A [4], A [6] ile karşılaştırılır ve böylece A [N] ile karşılaştırıldığında A [N-2] ‘ye kadar karşılaştırılır.
  • Sonunda A [N-1] A [N] ile karşılaştırılır.
  • Bu şekilde listenin en ağır veri öğelerini yerleştik.
  • 2. yinelemede, kalan N-1 veri elemanları ile aynı prosedür izlenecektir (son elemanı terk edin).
  • Bu şekilde en ağır 2. elementi elde ettik ve bu işlem toplam N-1 adımda devam edecek.
  • Sonuç olarak artan sırada bir A(N) dizisi elde etmiş olacağız.

2019-05-27_18-00-07.png

2019-05-27_18-00-41.png

2019-05-27_18-01-07.png

Bu yazıda karşılaştırma yöntemine dayanan, O (N2) süresine ve doğru sıralama algoritmasına sahip olan Avi Sort algoritmasını tanıttık. Avi sort, belirli alternatif pozisyonlarının değiş tokuşuna dayanır. Bu yöntem kabarcık sıralama gibi çalışır. Bu yöntem tam olarak Bubble sıralama ile aynı karmaşıklığa sahip, teorik ve ampirik yöntemimiz Avi sınıflamanın karmaşıklığının O (N2) olduğunu gösteriyor. Ortalama durumda, Avi sıralama yürütme süresi, yerleştirme sırasına eşittir ve en kötü durumda; yürütme süresi seçim ve ekleme sıralama arasındadır. En iyi durumda, zaman ve Avi sıralama karmaşıklığı O (N) ‘dir.

Bu algoritmanın en büyük kısıtlılığı, veri öğelerini sıralamak için çok zaman harcayan ikinci dereceden doğasıdır. Gelecekte, algoritmayı değiştirerek veya yeni bir algoritma tasarlayarak Avi sıralama algoritmasının karmaşıklığını azaltmaya çalışacağız.

avisort.m %matlab ile

%A=rand(1,1500);
%A=[99,88,77,66,55,44,33,22];
A=round(1000*rand(1,1500));
B=A;
disp(A);
tmp=0;
%disp(length(A));
tic;
j=0;

for i=1:length(A)-1
for j=1:length(A)-i-1
if A(1,j)>A(1,j+2)
tmp=A(j);
A(1,j)=A(1,j+2);
A(1,j+2)=tmp;
end
end
%disp(‘j=’);
%disp(j);
if A(1,j+1)>A(1,j+2)
tmp=A(1,j+1);
A(1,j+1)=A(1,j+2);
A(1,j+2)=tmp;
end
end
wtime=toc;
disp(A);
fprintf(1,’Hesaplama Zamanı: %f saniye \n’,wtime);
%disp(A(1));

avisort.java //java ile

class siralama{
public void avisort(int [] A) // bir diziyi parametre alan fonksiyon
{
int tmp;
int j;

for(int i=0; i<A.length; i++)//8
{
for(j=0 ; j<A.length-i-2;j++) //7
{

if(A[j]>A[j+2])
{

tmp=A[j];
A[j]=A[j+2];
A[j+2]=tmp;
}
}
if(A[j]>A[j+1])
{

tmp=A[j];
A[j]=A[j+1];
A[j+1]=tmp;
}

}
}
}
public class avisiralama {
public static void main(String args[]){
int [] x = { 99,88,77,66,55,44,33,22};
siralama s = new siralama();
s.avisort(x);
for(int i : x){
System.out.println(i);
}
}
}

bublesort.m   %matlab ile

%A=rand(1,1500);
%A=[99,188,77,66,55,44,33,22];
A=round(1000*rand(1,1500));
B=A;
disp(A);
tmp=0;
%disp(length(A));
tic;
j=0;

for i=1:length(A)-1
sirali=0;
j=length(A);
while(j>i)
%disp(j);
if A(1,j-1)>A(1,j)
sirali=1;
tmp=A(j-1);
A(1,j-1)=A(1,j);
A(1,j)=tmp;
end
j=j-1;
end
%disp(‘j=’);
%disp(j);
%if sirali==0;
% break;
%end
end
wtime=toc;
disp(A);
fprintf(1,’Hesaplama Zamanı: %f saniye \n’,wtime);
%disp(A(1));

iyilestirilmisbublesort.m

%A=rand(1,1500);
%A=[99,188,77,66,55,44,33,22];
A=round(1000*rand(1,1500));
B=A;
disp(A);
tmp=0;
%disp(length(A));
tic;
j=0;

for i=1:length(A)-1
sirali=0;
j=length(A);
while(j>i)
%disp(j);
if A(1,j-1)>A(1,j)
sirali=1;
tmp=A(j-1);
A(1,j-1)=A(1,j);
A(1,j)=tmp;
end
j=j-1;
end
%disp(‘j=’);
%disp(j);
if sirali==0;
break;
end
end
wtime=toc;
disp(A);
fprintf(1,’Hesaplama Zamanı: %f saniye \n’,wtime);
%disp(A(1));

mergesort.m
function [result] = MyMergeSort( x )
% Sort vector ‘x’ using the merge sort algorithm
% result is a vector consisting of the sorted values of ‘x’
% in ascended order
% Takes O( n log n ) time
% Requires extra memory for merging results

n = length(x);
if n == 1
% Stop the recursion, if we are down to one element in list
result = x;
else
m = floor(n/2); % Get the half way point

r1 = MyMergeSort( x(1:m) ); % Sort first half recursively…
r2 = MyMergeSort( x(m+1:n) ); % Sort 2nd half recursively…
result = MyMerge( r1, r2 ); % Merge the two halves in sorted order
end

function c = MyMerge( a, b )
% Merges 2 vectors a,b into a result vector c
% assumes a, b are already sorted
% ‘c’ will also be in sorted order

aLen = length(a); % get length of a
bLen = length(b); % get length of b
cLen = aLen+bLen;
c = zeros(1,cLen); % pre-allocate ‘c’ to correct size

% Initialize starting indices
aIdx = 1;
bIdx = 1;
for cIdx = 1:cLen
% Should we grab from ‘a’ or ‘b’ ???
if aIdx > aLen
% All done with ‘a’ vector, grab from ‘b’ vector.
c(cIdx) = b(bIdx);
bIdx = bIdx + 1;
elseif bIdx > bLen
% All done with ‘b’ vector, grab from ‘a’ vector
c(cIdx) = a(aIdx);
aIdx = aIdx + 1;
elseif a(aIdx) <= b(bIdx)
% a(i) <= b(i), grab from ‘a’ vector
c(cIdx) = a(aIdx);
aIdx = aIdx + 1;
else
% b(i) < a(i), grab from ‘b’ vector
c(cIdx) = b(bIdx);
bIdx = bIdx + 1;
end
end

Hespsi.m %çaışma zamanı hesaplaması:

%A=rand(1,1500);
A=[99,88,77,66,55,44,33,22];
%A=[9999:-1:1];
A=round(1000*rand(1,15000));
B=A;
C=A;
D=A;
%disp(A);
tmp=0;
%disp(length(A));
%avisort
tic;
j=0;
for i=1:length(A)-1
for j=1:length(A)-i-1
if A(1,j)>A(1,j+2)
tmp=A(j);
A(1,j)=A(1,j+2);
A(1,j+2)=tmp;
end
end
%disp(‘j=’);
%disp(j);
if A(1,j)>A(1,j+1)
tmp=A(1,j);
A(1,j)=A(1,j+1);
A(1,j+1)=tmp;
end
end
wtime=toc;
%disp(A);
fprintf(1,’avisort Hesaplama Zamanı: %f saniye \n’,wtime);
%bublesort
tic;
j=0;

for i=1:length(B)-1
sirali=0;
j=length(B);
while(j>i)
%disp(j);
if B(1,j-1)>B(1,j)
sirali=1;
tmp=B(j-1);
B(1,j-1)=B(1,j);
B(1,j)=tmp;
end
j=j-1;
end
%disp(‘j=’);
%disp(j);
%if sirali==0;
% break;
%end
end
wtime=toc;
%disp(B);
fprintf(1,’Bublesort Hesaplama Zamanı: %f saniye \n’,wtime);
%iyileştirilmiş bublesort
tic;
j=0;

for i=1:length(C)-1
sirali=0;
j=length(C);
while(j>i)
%disp(j);
if C(1,j-1)>C(1,j)
sirali=1;
tmp=C(j-1);
C(1,j-1)=C(1,j);
C(1,j)=tmp;
end
j=j-1;
end
%disp(‘j=’);
%disp(j);
if sirali==0;
break;
end
end
wtime=toc;
%disp(C);
fprintf(1,’İyileştirilmiş Bublesort Hesaplama Zamanı: %f saniye \n’,wtime);
tic;
D=MyMergeSort(D);
wtime=toc;
fprintf(1,’mergesort Hesaplama Zamanı: %f saniye \n’,wtime);

Binary earch tree kodu java;

#include <stdio.h>
#include <stdlib.h>

using namespace std;
struct n{
int data;
n *sol;
n *sag;
};
typedef n node;
node * ekle(node *agac,int x){
if(agac==NULL){
node *root=(node *)malloc(sizeof(node));
root->sol=NULL;
root->sag=NULL;
root->data=x;
return root;
}
if(agac->data<x){
agac->sag=ekle(agac->sag,x);
return agac;
}
agac->sol=ekle(agac->sol,x);
return agac;
};
void dolasinorder(node *agac){
if(agac==NULL)
return;
dolasinorder(agac->sol);
printf(“%d “,agac->data);
dolasinorder(agac->sag);
};
void dolaspreorder(node *agac){
if(agac==NULL)
return;
printf(“%d “,agac->data);
dolaspreorder(agac->sol);
dolaspreorder(agac->sag);
};
void dolaspostorder(node *agac){
if(agac==NULL)
return;
dolaspostorder(agac->sol);
dolaspostorder(agac->sag);
printf(“%d “,agac->data);

};
int bul(node *agac,int aranan){
if(agac==NULL){
return -1;
}
if(agac->data==aranan){
return 1;
}
if(bul(agac->sag,aranan)==1){
return 1;
}
if(bul(agac->sol,aranan)==1){
return 1;
}
return -1;
};
int max(node *agac){
while(agac->sag!=NULL)
agac=agac->sag;
return agac->data;

}
int min(node *agac){
while(agac->sol!=NULL)
agac=agac->sol;
return agac->data;

}
node *sil(node *agac,int x){
if(agac==NULL)
return NULL;//ağaç bossa 1.ihtimal
if(agac->data==x){
if(agac->sol==NULL && agac->sag==NULL)
return NULL;
if(agac->sag!=NULL){
agac->data=min(agac->sag);
agac->sag=sil(agac->sag,min(agac->sag));
return agac;
}

agac->data= max(agac->sol);
agac->sol=sil(agac->sol,max(agac->sol));
return agac;
}
if(agac->data<x){
agac->sag=sil(agac->sag,x);
return agac;
}
agac->sol=sil(agac->sol,x);
return agac;

};

int main()
{
node *agac=NULL;
agac=ekle(agac,12);
agac=ekle(agac,200);
agac=ekle(agac,190);
agac=ekle(agac,213);
agac=ekle(agac,56);
agac=ekle(agac,24);
agac=ekle(agac,18);
agac=ekle(agac,27);
agac=ekle(agac,28);
dolasinorder(agac);
printf(“\n”);
dolaspreorder(agac);
printf(“\n”);
dolaspostorder(agac);
printf(“\n”);
printf(“arama sonucu: %d”,bul(agac,100));
printf(“\n”);
printf(“max=%d min=%d”,max(agac),min(agac));
printf(“\n”);
dolasinorder(agac);
printf(“\n”);
agac=sil(agac,190);
dolasinorder(agac);
printf(“\n”);
return 0;
}

 

 

 

 

Reklamlar