BubbleSort, Kabarcık sıralama örneği

[command]

daha önceden forumda paylaştığım örnek bir koda sıralama fonkiyonu ekledim fonksiyon tamamen bana ait değil internette gezinirken bulduğum bir kodu kendi koduma uyarladım örnek için kullanılabilir

Kod Seç Genişlet


uses crt;

var sifir,say,numara,i : byte;
sira : array [0..5] of byte;
cevap : char;
label tekrar,basla;

procedure uretec;
begin
randomize;
numara:=random(48)+1;
end;

procedure rset;
begin
for sifir:=0 to 5 do
begin
sira[sifir]:=0; // aynı sayının tekranını engellemek için dizideki değerler sıfırlanıyor
end;
end;

procedure sort;
var x,y,temp:integer;
begin
 for x:=0 to 5 do
   for y:=x to 6 do
     if sira[y]<sira[x] then
       begin
         temp:=sira[x];
         sira[x]:=sira[y];
         sira[y]:=temp;          
       end;
       for i:=1 to 6 do
       write(sira[i]:02,'. ');
end;


BEGIN
basla:
highvideo;
clrscr;
textcolor(green);
writeln('Hesaplanıyor, lütfen bekleyin...');
for say:=1 to 6 do
begin
tekrar:
uretec;
sira[say]:=numara;
if (numara=sira[say-1]) or   // dizideki 0
  (numara=sira[say-2]) or   // dizideki 1
  (numara=sira[say-3]) or   // dizideki 2
  (numara=sira[say-4]) or   // dizideki 3
  (numara=sira[say-5]) or   // dizideki 4
  (numara=sira[say-6]) then // dizideki 5
begin
goto tekrar;
end
else
write(sira[say]:02,'. ');
end;
writeln;
textcolor(red);
writeln('Sıralandı.');
sort;
writeln;
normvideo;
write('Tekrar E/H ? : ');
cevap:=readkey;
if upcase(cevap)='E' then
begin
rset;
goto basla;
end
else
begin
write('BYE.');
end;
halt(0);
END.



örnek

Kod Seç Genişlet


Hesaplanıyor, lütfen bekleyin...
7. 17. 48. 21. 25. 23.
Sıralandı.
7. 17. 21. 23. 25. 48.
Tekrar E/H ? :


[heartsmagic]

Öncelikle eline sağlık. Benim merakım bu sıralama yönteminin bir ismi var mı? Örneğin zamanında C ile haşir neşir olduğumuzda Bubble Sort gibi yöntemleri görmüştüm. Sonuçta bu bir algoritmadır ve hemen her dile uygulanabilir. Buradaki yöntem bunlardan birine giriyor mu?

[command]

Belirli bir örneğini bulamadım ama c örnelerinden baktığımda "Quick Sort" adında bir yöntemle benzerliği var

Quick sort değilmiş

örneğin aslı bu sayfada
http://pascalprogramming.byethost15.com/articles/sorting.php

[heartsmagic]

Hangi sortmuş peki bu?
Amacım başlığa bir tane anahtar kelime ekletebilemek aslında, çok fazla önemi olmasa da ihtiyaç duyacak olanlar yararlanabilir diye düşünmüştüm.

[command]

BubbleSort, Kabarcık sıralama

[heartsmagic]

Demek ki iyi atmış... pardon tahmin etmişim
Başlığı düzenlediğin için teşekkürler.

[empax]

C uzerinde bubble sort siralamasini kavramaya calsiyorum, kafam allak bullak oldu. 

[egcodes]

Vakti zamanında bu algoritmaları toplayım yarıştırmıştım

Aşağıda kodları ve isimleri var.

Kod Seç Genişlet


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

#define SIZE        100000
#define SORTSIZE    8

typedef struct _sort {
char name[25];
double time;
}sort;

double calctime(double start);

int *setRandomArray(int *a, int size);
void displayArray(const int *a, int size);
void displaySort(sort *p, int size);
void sortSort(sort *p, int size);


int fcmp(const void *vp1, const void *vp2); //for qsort
void sift(int *p, int left, int right);     //for heap sort

//Sort Algorithms
void bubble_sort(int *p, int size);
void selection_sort(int *p, int size);
void shell_sort (int *p, int size);
void merge_sort (int *p, int size);
void insertion_sort(int *p, int size);
void heap_sort (int *p, int size);


int main(void)
{
int array[SIZE];
clock_t start;
sort sortarray[SORTSIZE];

srand((unsigned int)time(0));

printf("S o r t   A l g o r i t h m s\n");
printf("=============================\n\n");

printf("%d element array\n", SIZE);
printf("----------------------\n\n");



//Selection sort
printf("Selection sort is working\n");
setRandomArray(array, SIZE);
start = clock();
selection_sort(array, SIZE);
sprintf(sortarray[1].name, "Selection sort");
sortarray[1].time = calctime(start);

//Bubble sort
printf("Bubble sort is working\n");
setRandomArray(array, SIZE);
start = clock();
bubble_sort(array, SIZE);
sprintf(sortarray[2].name, "Bubble sort");
sortarray[2].time = calctime(start);

//Qsort
printf("Qsort is working\n");
setRandomArray(array, SIZE);
start = clock();
qsort(array, SIZE, sizeof(int), &fcmp);
sprintf(sortarray[3].name, "Qsort");
sortarray[3].time = calctime(start);

//Merge sort
printf("Merge sort is working\n");
setRandomArray(array, SIZE);
start = clock();
merge_sort(array, SIZE);
sprintf(sortarray[4].name, "Merge sort");
sortarray[4].time = calctime(start);

//Insertion sort
printf("Insertion sort is working\n");
setRandomArray(array, SIZE);
start = clock();
insertion_sort(array, SIZE);
sprintf(sortarray[5].name, "Insertion sort");
sortarray[5].time = calctime(start);

//Heap sort
printf("Heap sort is working\n");
setRandomArray(array, SIZE);
start = clock();
heap_sort(array, SIZE);
sprintf(sortarray[6].name, "Heap sort");
sortarray[6].time = calctime(start);

//Shell sort
printf("Shell sort is working\n");
setRandomArray(array, SIZE);
start = clock();
shell_sort(array, SIZE);
sprintf(sortarray[7].name, "Shell sort");
sortarray[7].time = calctime(start);


//Results
system("clear");
printf("S o r t   A l g o r i t h m s\n");
printf("=============================\n\n");
sortSort(sortarray, SORTSIZE);
displaySort(sortarray, SORTSIZE);

getchar();
return 0;
}

void sortSort(sort *p, int size)
{
   int  i, j;
   sort temp;

   for (i = 0; i < size - 1; i++)
      for (j = 0; j < size - i - 1; j++)
         if (p[j].time > p[j + 1].time) {
            temp = p[j];
            p[j] = p[j + 1];
            p[j + 1] = temp;
         }

}

void displaySort(sort *p, int size)
{
    int k;

    for (k = 1; k < size; k++)
      printf("%d) %s -> %.3f\n", k, p[k].name, p[k].time);


}


int *setRandomArray(int *a, int size)
{
    int i;

    for (i = 0; i < size; i++)
        a[i] = rand() % 1000 + 100;

    return a;
}

void displayArray(const int *a, int size)
{
    int i;

    for (i = 0; i < size; i++)
        printf("%d ", a[i]);
}

double calctime(double start)
{
    clock_t end = clock();


    return (double)(end - start) / CLOCKS_PER_SEC;
}

//for Qsort
int fcmp(const void *vp1, const void *vp2)
{
return *(const int *)vp1 -  *(const int *)vp2;
}

//for Heap sort
void sift(int *p, int left, int right)
{
   int temp, i;

   i = left +left +1;
    temp = p[left];

   do {
      if (i < right && p[i] < p[i+1])
         i++;
      if (temp >= p[i])
         break;
      p[left] = p[i];
      left = i;
      i = 2 * i + 1;
   } while (i <= right);
   p[left] = temp;
}




void bubble_sort(int *p, int size)
{
   int   i, j, temp;

   for (i = 0; i < size - 1; i++)
      for (j = 0; j < size - i - 1; j++)
         if (p[j] > p[j + 1]) {
            temp = p[j];
            p[j] = p[j + 1];
            p[j + 1] = temp;
         }
}

void selection_sort(int *p, int size)
{
   int   i, j, temp, min;

   for (i = 0; i < size - 1; i++) {
      min = i;
      for (j = i + 1; j < size; j++)
         if (p[min] > p[j])
            min = j;
      temp = p[min];
      p[min] = p[i];
      p[i] = temp;
   }
}

void shell_sort (int *p, int size)
{
   int   i, j, k, temp;

   for (k = size; k > 1; ) {
      k = (k < 5) ? 1 : ((k * 5 - 1) / 11);
      for (i = k - 1; ++i < size; ) {
         temp = p[i];
         for (j = i; p[j - k] > temp; ) {
            p[j] = p[j - k];
            if ((j -= k) < k)
               break;
         }
         p[j] = temp;
      }
   }
}

void merge_sort (int *p, int size)
{
   int *t, *q, *buf;
   int   left, len, count1, count2, source1, source2, dest;

   if (size <= 1)
      return;
   buf = q = (int *) malloc(size * sizeof(int));
   if (buf == NULL) {
      printf("not enough memory!");
      exit(EXIT_FAILURE);
   }
   len = 1;

   do {
      left = size;
      source1 = dest = 0; source2 = len;
      do {
         left -= count1 = (left >= len) ? len : left;
         left -= count2 = (left >= len) ? len : left;
         while (count1 > 0 && count2 > 0) {
            if (p[source1] < p[source2]) {
               q[dest++] = p[source1++];
               count1--;
            }
            else {
               q[dest++] = p[source2++];
               count2--;
            }
         }
         while (--count1 >= 0)
            q[dest++] = p[source1++];
         while (--count2 >= 0)
            q[dest++] = p[source2++];
         source1 += len; source2 += len;
      } while (left > 0);
      t = p;
      p = q;
      q = t;
      len *= 2;
   } while (len < size);
   if (p == buf)
      while (--size >= 0)
         q[size] = p[size];
   free(buf);
}

void insertion_sort(int *p, int size)
{
   int   i, j, t;

   for (i = 0; ++i < size; ) {
      t = p[i];
      for (j = i; p[j - 1] > t; ) {
         p[j] = p[j - 1];
            if (--j <= 0) break;
      }
      p[j] = t;
   }
}

void heap_sort (int *p, int size)
{
   int  left, right, temp;

   if (size <= 1)
      return;
   left = size / 2;
   right = size - 1;

   while (--left >= 0)
      sift(p, left, right);

   for (;;) {
      temp = p[0];
      p[0] = p[right];
      p[right] = temp;
      if (--right <= 0)
         break;
      sift(p, 0, right);
   }
}
 

[canosayan]

http://www.facebook.com/AlgoRythmics adresinde bir çok algoritmayı farklı şekillerde izleyebiliyorsunuz.

[empax]

http://www.facebook.com/AlgoRythmics adresinde bir çok algoritmayı farklı şekillerde izleyebiliyorsunuz.

Bizde turkce kaynak sıkıntısı var adamlarda kaynak bollugu.
http://www.youtube.com/watch?v=lyZQPjUT5B4&feature=related

[sem]

@egcodes, acaba rastgele dizi yaratma bir kere yapılsa yani bütün algoritmalar aynı dizi üzerinde çalışsa daha adaletli olma ihtimali var mı sıralamanın... Kafama takıldı da tüm algoritmaların içeriğini bilmediğim için...  Bir bilene danışayım dedim =)

[egcodes]

Kısmen doğru söylüyorsun.

Yüzde 50'sinin sırası doğru diğeri yanlış olan bir dizide qsort mesela iki kat daha hızlı çalışır ama bu herhalde mikrosaniye cinsinden bir fark yaratır.

Genel anlamda sıralama hep aynı çıkar ama

Bu qsort mergesort onların nasıl çalışıtığını bende bilmiyorum karmaşık bayağı. Ben sadece yerine koyup hızlarına baktım

[sem]

Eline sağlık güzel kaynak olmuş gerçekten.

Gerçi şöyle bir durum da var, eğer benim dediğim kadar dikkat edilecek olursa eğer, her algoritma için ayrı bir diziyi el ile yazmak da gerekebilir. Çünkü rastgele oluşturulan bir dizi de bir algoritma için çok avantajlı olurken yani her adım başarı ile sonuçlanırken bir başka algoritma için  o kadar avantajlı olmayabilir.

Yani sonuç olarak senin izlediğin yol en uygunu gibi.

[sem]

Gözden kaçırmışız sanırım.. İlk iletideki kod C ya da C++ kodu değil... BEGIN ve END var... Basic, Pascal temelli bir dil olabilir... Onlarda vardı sanırım bloklar yerine begin & end kısımları...