Compress Cryptography Recovery Sortings Ostatni
VE VYSTAVBE!

Principy serazovacich algoritmu (Sorting)


0. * sorting.htm (JavaScript sorting - moje demicko)
1. * www.cs.ubc.ca (Java sorting)
2. * en.wikipedia.org Velky zdroj sort algoritmu
3. digilander.libero.it (JavaApplet sorting)
Pozn.: "Speed" [0.] "Speed2" [2.]
2d=pole1_pole2 pocet1=n pocet=n+1 (n=1000 cpu=1,68GHz/AMD (2400+ intel))

Stabilita - pri serazeni 2 stejnych cisel "Stabilni" algoritmus zachova puvodni poradi, u "Nestabilniho" muze dojit k zamene.
1="B" 2="A" 3="B" (stabilni vzdy 213, nestabilni nekdy 231)

Bubble


Porovnaji se dve hodnoty v poli a pokud je prvni vetsi, pak se zameni. 
= 0 1
a 7 666666 55555 4444 333 22 1
b 6 755555 64444 5  3 4 2 31 2
c 5 574444 46333  5 2  41  3.3
d 4 447333 33622   51   4... 4
e 3 333722 22261    5....    5
f 2 222271 11116.....        6
g 1 111117......             7

1: z=a; if a>b then (a=b,b=z)

var i,j,a;
for (i=1;i<pocet;i++)
for (j=0;j<pocet-i;j++)
{ a=pole1[j];if (a>pole1[j+1]) {pole1[j]=pole1[j+1];pole1[j+1]=a} }
(Speed=1453 1d)

Bubble - double


Bubble zhora i z dola. 
= 0 1      2
a 7 666666 6   1.....        1
b 6 755555 5  16 5  5 5 2... 2
c 5 574444 4 1 5 6  4 425 44 3
d 4 447333 31  4 46 3 2 4 53 4
e 3 333722 1   3 3 62 3 3 35.5
f 2 222271 2   2 2  6....    6
g 1 111117......             7

1: z=a; if a>b then {a=b,b=z}
2: z=e; if e>f then {e=f,f=z}

var i,j,k,a,d;
d=Math.floor(pocet/2);
for (i=1;i<d;i++)
for (j=i-1;j<(pocet-i);j++)
{a=pole1[j];if (a>pole1[j+1]) {pole1[j]=pole1[j+1];pole1[j+1]=a;}
k=pocet1-j-1;
a=pole1[k];if (a>pole1[k+1]) {pole1[k]=pole1[k+1];pole1[k+1]=a;}
}
a=pole1[d];
if (pole1[d-1]>a) {pole1[d]=pole1[d-1];pole1[d-1]=a;a=pole1[d]};
if (pole1[d+1]<a) {pole1[d]=pole1[d+1];pole1[d+1]=a;a=pole1[d]};
if (pole1[d-1]>a) {pole1[d]=pole1[d-1];pole1[d-1]=a};
(Speed=1453 1d)

Select


Vybira se MIN hodnota (nejmensi) a jeji pozice. Az se projde cele pole hodnot, tak zapise MIN na 1. misto a na X. misto, kde byla, se zapise hodnota, ktera byla na 1. miste. 
= 0 123456 7 8 9ABCD E FGH I
a 7 777777 1 .........                   1
b 6 666666 6 6 66666 2 ......            2
c 5 555555 5 5 55555 5 5555 3....        3
d 4 444444 4 4 44444 4 4444 4 444 4...   4
e 3 333333 3 3 33333 3 3333 5 555 5 55 5.5
f 2 222222 2 2 22222 6 6666 6 666 6 66 6 6
g 1 111111 7 7 77777 7 7777 7 777 7 77 7 7

z 7 654321   6 54322  54333  4
x a bcdefg   b cdeff  cdeee  d
y          7         6      5

0: z=a x=(a)="1"
1: b<z then {z=(b)="6" x=b}
6: g<z then {z=(g)="1" x=g}
7: y=(a)="7"; a=z="1"; (x)=y="7";

var i,j,a,b;
b=0;a=pole1[b];
for (i=0;i<pocet;i++)
{
for (j=1;j<pocet;j++) {if (pole1[j]<a) {b=j;a=pole1[b]}}
pole2[i]=a;a=pocet;pole1[b]=a;
}
(Speed=1140 2d)

Shaker


Jako Select, vybira se MAX a MIN. 
=  0 123456 7
a  7 777777 1.........      1
b  6 666666 6 6 6666 2..... 2
c  5 555555 5 5 5555 5 55 3.3
d  4 444444 4 4 4444 4 44 4 4
e  3 333333 3 3 3333 3 33 5.5
f  2 222222 2 2 2222 6..... 6
g  1 111111 7.........      7

z1 7 654321   6 5432 543 4
x1 a bcdefg   b cdef cde d
z2 7 777777   6 6666 5   4
x2 a aaaaaa   b bbbb c   d
y           7       6   5 4
y           7       6   5 4

0: z1=(a) x1=a z2=(a) x2=a
1: b<z1 then {z1=(b)="6"; x1=b}
   b>z2 then {z2=(b)="6"; x2=b} NEPLATI (z2=a)
7: y=(a)="7"; a=z1="1"; (x1)=y="1"
   y=(g)="7"; g=z2="7"; (x2)=y="7"
8: z1=(b) x1=b z2=(b) x2=b

var i,j,a,b,e,f,h,m,n;
h=Math.floor((pocet+1)/2);
b=0;a=pole1[b];
f=0;e=pole1[f];
for (i=0;i<h;i++)
{
for (j=0;j<pocet;j++)
{
m=pole1[j];
if (m!=pocet)
{
 if (m<a) {b=j;a=m}
 if ((m>e)||(e==pocet)) {f=j;e=m}
}
}
pole2[i]=a;pole2[pocet1-i]=e;
a=pocet;e=a;pole1[b]=a;pole1[f]=a;
}
(Speed=984 2d)

Swap


Speed2: 7000 Pamet2: Ne
Swap=Select in 1d 
var i,j,a,b,c,x,y;
x=0;y=pocet1;
for (i=x;i<y;i++)
{
a=pole1[i];b=i;c=pole1[b]
for (j=(i+1);j<=y;j++) {if (pole1[j]<c) {b=j;c=pole1[b]}}
pole1[i]=c;pole1[b]=a;
}
(Speed=422 1d)

Swap + slevani


Pole rozdelim na 4 casti a kazdou zvlast seSwapuji. Pak je slevam do sebe. 
var i,j,a,b,c,x,y;
var h=Math.floor(pocet/4);

x=0;y=h-1;swap(x,y)
x=h;y=2*h-1;swap(x,y)
x=2*h;y=3*h-1;swap(x,y)
x=3*h;y=pocet1;swap(x,y)

a=0;b=h;c=2*h;slevani12(a,b,c)
a=2*h;b=3*h;c=pocet;slevani12(a,b,c)
a=0;b=2*h;c=pocet;slevani2_1(a,b,c) (zmen pole1/2)

(slevani begin)
function slevani12(x1,x2,x3)
{	var i,a,b,c,x,y;
	c=0;
	a=x1;b=x2;
	for (i=x1;i<x3;i++)
	{
	x=pole1[a];
	y=pole1[b];
	if (x<y) {pole2[i]=x;a++;if (a>=x2) {c=i;i=x3;x=b;y=x3}}
	else	 {pole2[i]=y;b++;if (b>=x3) {c=i;i=x3;x=a;y=x2}}
	}
	if (c!=0) {for (i=x;i<y;i++) {c++;pole2[c]=pole1[i]}}
(slevani end)
(Speed=110 2d)

Insertion


Vybrana hodnota se vklada ve spravnem poradi do druhe tabulky. Speed2: 227562 Pamet2: Ne 
Priklad (Pamet: Ano)
  0 1 23 456 789A BCDEF G..
a 7 7 7  7   7    7     7
b 6 6 6  6   6    6     6
c 5 5 5  5   5    5     5
d 4 4 4  4   4    4     4
e 3 3 3  3   3    3     3
f 2 2 2  2   2    2     2
g 1 1 1  1   1    1     1

z   6 55 444 3333 22222 111111

i 7 6 65 554 4443 33332 222221
j   7 76 665 5554 44443 333332
k      7 776 6665 55554 444443
l          7 7776 66665 555554
m               7 77776 666665
n                     7 777776
o                            7

0: i=a
1: z=b; if z>i then {n=i; i=z}
2: z=c; if z>j then {n=j; j=z} NEPLATI
	if z>i then {n=i; i=z}

var i,j,b,c;
pole2[0]=pole1[0];
for (i=1;i<pocet;i++)
{
c=pole1[i];b=i;
for (j=0;j<i;j++) {if (pole2[j]>c) {b=j;j=i}}
if (b!=i) { for (j=(i-1);j>=b;j--) {pole2[j+1]=pole2[j]} }
pole2[b]=c
}
(Speed=563 2d)

In-Place Merge


Speed2: Pamet2: NESTABILNI 1. Tabulka hodnot se rozdeli na "n" bloku 2. V kazdem bloku se najde "m" rostoucich posloupnosti hodnot. Cili nejmene 2. 3. prave 2 posledni v bloku se slevaji do sebe, cimz vznika nestabilita

Double Storage Merge


Speed2: 87793 Pamet2: Ne

Comb


Speed2: 69515 Pamet2: Ne

Shell


Heap


Speed2: 49594 Pamet2: Ne

Quick


Pole rozdeli na hodnoty vetsi/mensi nez max/2. Toto opakuje pro kazdou pulku. Narocne na zpracovani pri velkem poli. Speed2: Pamet2:

Quick with Bubblesort


Speed2: 12937 Pamet2: Ne

Enhanced Quick


Speed2: 11875 Pamet2: Ne

Fast Quick


Speed2: 10500 Pamet2: Ne

Radix


Speed2: Pamet2: