Paylaşım Noktası

Daha önceki yazımda ofstream kullanarak dosyadan okuma işlemini göstermiştim. Bu yazımda ise fprintf kullarak dosyadan veri okumaya yarayan C++ kodlarına yer vereceğim.

FILE *File;
File = fopen ("./output.txt", "w");    
    
if(!File){
    perror("error");
    exit ( EXIT_FAILURE );
}

int i = 0;

for(int k = 0 ; k<25 ; k++) {
    fprintf(File, "%d", i);
    i++;
}

fclose(File);

C++ fprintf, FILE

Daha önceki yazımda ifstream kullanarak dosyadan okuma işlemini göstermiştim. Bu yazımda ise fscanf kullarak dosyadan veri okumaya yarayan C++ kodlarına yer vereceğim.

FILE *File;
File = fopen("./input.txt", "r");

if(!File) {
    perror("error");
    exit ( EXIT_FAILURE );
}

int num;
fscanf(File, "%d", &num);

fclose(File);

C++ fscanf, FILE

BFS, kök düğümden başlayarak tüm elemanları tarayan ve komşulukları ortaya çıkaran bir graf arama algoritmasıdır.

Çalışması sırasında son düğüme oluşana dek, keşfedilmiş tüm düğümlere komşu henüz keşfedilmemiş düğümleri keşfetme mantığını yürütür. Diklemesine değil, yataylamasına büyümeyi hedefler.

Düğümlerin keşfediliş sıralarına göre farklı ağaçlar oluşturulabilir.

Pseudocode:

unmark all vertices
choose some starting vertex x
mark x
list L = x
tree T = x

while L nonempty
choose some vertex v from front of list
visit v
for each unmarked neighbor w
    mark w
    add it to end of list
    add edge (v,w) to T

Liste olarak kuyruk tutmalıyız. FIFO kuralı uygulanacak.

Kuyruk kullanmadan da yapılabilir. Aşağıda yer alan C++ kodunda kuyruk kullanılmamıştır.

bool Discovered[num];
for (int k = 0; k < num; k++)
    Discovered[k] = false;

Node BFStree[num];

int i = 0;
BFStree[i].data = 0;
Node *temp;

Discovered[i] = true;

while ( i < num ) {
    temp = &BFStree[i];
    for( int k = 0 ; k < num ; k++ ) {
        if ( matris[i][k] == 1 && !Discovered[k] ) {
            Discovered[k] = true;
            Node *newNode = new Node(k);
            temp->next = newNode;
            temp = newNode;
        }
    }

    i++;
    BFStree[i].data = i;
}

Not: Yukarıdaki kodu çalıştırmak için Adjacency matris kullanılmıştır. “num” adındaki değişken ise grafta yer alan eleman sayısını göstermektedir.

Sonuç olarak Adjencency matrisi sol aşağıdaki gibi olan bir grafın bfs algoritması sonucu oluşan spanning ağacı sağ aşağıdaki gibidir.

Algoritma, C++ bfs, graf, arama, search, spanning tree

Counting sort veri kümesinde (sayılardan oluşuyor) yer alan elemanların aralığını kullanarak sıralama yapan vir sıralama algoritmasıdır. 1954 yılında Harold H. Seward tarafından yarılmıştır.

Counting sort çalışması sırasında giren dizi haricinde 2 tane boş dizi yaratır.

• A: Sıralanacak elemanların bulunduğu dizi
• B: Sıralanmış dizi
• C: A dizisindeki tekrarlanan eleman sayısını tutan dizi

Algoritmanın uygulanışı şu şekildedir:

1. A dizisindeki elemanlar tek tek dolaşılarak B dizisi doldurulur.
   
   Mesela; A dizinde 1 elemanında 2 tane bulunmaktadır, 2 elamanından hiç yoktur.
   
2. C dizisi, en soldaki birimden başlayarak n = n + (n-1) şeklinde artırılacak şekilde yeniden oluşturulur.
   
3. Bu adımda A dizisinin elemanları sondan başlayarak taranmaya başlanır. Her elemanın içeriği kontrol edilerek C dizisindeki karşılığı bulunur. Bu karşılık A dizinden aldığımız elemanı B dizisinin hangi gözüne yazmamız gerektiğini gösteriyor.
   
   
   
   
   
    
   
   İşlem sonucunda B dizimiz şu şekilde oluşmuştur:
    

Örnek C kodu:

void counting_sort(int *array, int size)
{
  int i, min, max;
 
  min = max = array[0];
  for(i = 1; i < size; i++) 
  {
    if (array[i] < min)
      min = array[i];
    else if (array[i] > max)
      max = array[i];
  }
 
  int range = max - min + 1;
  int *count = (int *) malloc(range * sizeof(int));
 
  for(i = 0; i < range; i++)
    count[i] = 0;
 
  for(i = 0; i < size; i++)
    count[ array[i] - min ]++;
  int j, z = 0;
  for(i = min; i <= max; i++)
    for(j = 0; j < count[ i - min ]; j++)
      array[z++] = i;
 
  free(count);
}

Örnek C++ kodu:

#include <iostream>
#include <vector>
using namespace std;
 
void countingSort(vector<int>& Array)
{
    int Min, Max;
    Min = Max  = Array[0];
    for(int i = 1; i < Array.size(); i ++)
    {
        if(Array[i] < Min)
            Min = Array[i];
 
        if(Array[i] > Max)
            Max = Array[i];
    }
    int Range = Max - Min + 1; 
 
    vector<int> Count; 
    Count.resize(Range);
 
    for(int i = 0; i < Range; i ++)
        Count[i] = 0;
 
    for(int i = 0; i < Array.size(); i ++)
        Count[Array[i] - Min] ++;
 
    int Index = 0;
    for(int i = Min; i <= Max; i ++)
        for(int j = 0; j < Count[i - Min]; j ++)
            Array[Index ++] = i;
}

Kaynak:
en.wikipedia.org
net.pku.edu.cn

C, C++, Algoritma sıralama algoritmalaları, counting

Radix Sort algoritması, sayıları sıralamaya yarayan bir sıralama algoritmasıdır. Tarihte ilk kullanımı 1887 yılında Herman Hollerith’un 1887 yılındaki kataloglama makinesi çalışmalarına dayanmaktadır.

Karakter katarları ve tarihler de sayma sayısı olarak temsil edilebildiklerinden (ASCII), radix sort sayılar yanından karakter katarlarını da sıralayabilir.

Sıralama işlemi O(kN) zamanda gerçeklenir.
N: Veri kümesinde yer alan eleman sayısı,
k: Veri kümesinde yer alan elemanların en büyük basamak sayısı

Basamakları kullanarak sıralama işlemi yapılır. İlk olarak en küçük basamağa (en sağ) göre sıralanır. En büyük basamağa doğru ilerlenir. Her basamakta sıralama işlemi tekrarlanır. Böylece elimizde küçükten büyüğe (ya da büyükten küçüğe – isteğe bağlı) sıralanmış veri kümesi kalmış olur.

Örnek C++ kodu:

#include <iostream.h>
#include <stdlib.h>
#include <string.h>

void radix (int byte, long N, long *source, long *dest)
{
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
  for ( i=0; i<N; i++ ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

void radixsort (long *source, long *temp, long N)
{
  radix (0, N, source, temp);
  radix (1, N, temp, source);
  radix (2, N, source, temp);
  radix (3, N, temp, source);
}

void make_random (long *data, long N)
{
  for ( int i=0; i<N; i++ ) data[i]=rand()|(rand()<<16);
}

long data[100];
long temp[100];

void main (void)
{
  make_random(data, 100);
  radixsort (data, temp, 100);
  for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
}

Kaynak:
www.brpreiss.com
www.cubic.org

Algoritma, C++ sıralama algoritmalaları, radix

Quicksort algoritması, yapısındaki basitlik ve çalışmasındaki hızlılığa bağlı olarak günümüz bilgisayar sistemlerinde önemli yer etmiş bir sıralama algoritmasıdır.

1960 yılında küçük bir İngiliz şirketi olan Elliot Brothers'ta çalışan C. A. R. Hoare tarafından geliştirilmiştir.

Θ(nlogn) çalışma zamanında çalışan algoritmanın çalışma şekli çok basittir:

1. Sıralanmak istenen veri kümesinden bir sayı pivot olarak seçilir. (Genelde dizinin en son elemanıdır)
2. Veri kümesindeki her eleman tek tek kontrol edilir. Pivotun değerinden küçük elemanlar pivotun sol tarafına, büyük elemanlar pivotun sağ tarafına taşınır.
3. Pivotun sağ ve sol tarafı şeklinde 2 veri kümesine ayrılır ve algoritma tarafından tekrar işlenir.

Yukarıdaki basamaklar, fonksiyona giren veri kümesinde 1 eleman kalıncaya kadar devam eder. Sonunda tüm veri kümeleri bir araya getirilir.

Pseudocode:

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Örnek C++ kodu:

void quickSort(int arr[], int left, int right) {

      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

C++, Algoritma sıralama algoritmalaları, quicksort

Bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Merge Sort algoritması, 1945 yılında John von Neumann tarafından bulunmuştur.

Merge Sort, sıralanması istenen veri kümesini 2’ye bölme ve karşılaştırma işlemleri yaparak sıralamayı gerçekler.

zamanda gerçeklenen algoritmanın algoritması aslında günlük hayatta çok sık başvurduğumuz bir yöndemdir:

1. Sıralı olmayan listeyi ortadan eşit olarak iki alt listeye ayırır.
2. Alt listeleri kendi içinde sıralar.
3. Sıralı iki alt listeyi tek bir sıralı liste olacak şekilde birleştirir.

Örnek C++ kodu:

void mergesort (int *a, int l, int r)
{
    int m;
    if (l<r)
    {
        m = (l+r)/2;
        mergesort(a,l,m);    
        mergesort(a,m+1,r);
        merge (a,l,m,r);
    }
}

void merge (int *a, int l, int m, int r)
{
    int b[SIZE];
    int h,i,j,k;    
    
    i = l;
    j = m+1;
    k = l;

    while (i<=m && j<=r) 
    {
        if (a[i] <= a[j]) 
        {
            b[k] = a[i];
            i = i+1;
        }
        else if (a[i] > a[j]) 
        {
            b[k] = a[j];
            j = j+1;
        }
        k = k+1;
    }

    if (i>m) 
    {
        for (h=j; h<=r; h++)
            b[k+h-j] = a[h];
    }
    else if (j>r) 
    {
        for (h=i; h<=m; h++)
            b[k+h-i] = a[h];
    }

    for (h=l; h<=r; h++)
        a[h] = b[h];
}

Algoritma, C++ sıralama algoritmalaları, merge sort

Çok sık kullanılan, karşılaştırmaya dayalı bir sıralama algoritmasıdır.

zamanda gerçekleşir. Uzun zaman aldığından, büyük veri paketlerinde kullanılmamasına dikkat edilmelidir.

Çalışma sistemine gelince: Arka kısımda 2li sıralama ağacı kullanır. Tüm sıralama işlemlerini bu ağaç üzerinde gerçekleştirir.

Algoritma, verilen veri kümesini 2li ağaca çevirir. Bu işlemi yaparken herhangi bir koşul gözetilmez, elemanlar ağaca sırayla eklenir. Fakat ağaç oluşturduktan sonra ağacın en son elemanından başlayarak köke kadar tüm elemanları tarayarak, ağacın bir MAX ya da MIN HEAP ağacı olması sağlarız. (Bu kadarı, sıralamamızı azalan ya da artan olması durumuna göre karar veririz.). Bu işlemden sonra en sondaki eleman ile kök elemanının yerlerini değiştirilir ve en son yaprak ağaçtan koparılır.

Sıralama, yer değiştirme ve koparma işlemleri, ağaçta sadece kök elemanı kalana kadar tekrarlanır. Koparılan elemanlar konduğu sırada listeye geri alınır. Böylece sıralama yapılmış olur.

Pseudocode:

Build Max Heap:

BUILD-MAX-HEAP(A)
    heap-size[A] ← length[A]
    for i ← floor(length[A]/2) downto1
        do
             MAX-HEAPIFY(A, i)

Max Heapify:

MAX-HEAPIFY(A, i)
    l ← LEFT(i)
    r ← RIGHT(i)
    if l ≤ heap-size[A] and A[l] > A[i]
        then largest ← l
        else largest ← i
    if r ≤ heap-size[A] and A[r] > A[largest]
        then largest ← r
    if largest ≠ i
        then exchange A[i] ↔ A[largest]
            MAX HEAPIFY(A, largest)

Sıralama örneği:

Bize verilen dizi: 4 1 3 2 16 9 10 14 8 7

2li ağacımızı oluşturalım:

Ağacı düzenleyelim (sıralama):

Ağacın son elemanı ile kökü yer değiştirelim, ve son düğümü ağaçtan kopartalım.

Ağacın en son hali:

Örnek C++ kodu:

void heapsort(int *a, int size) 
{
    int i, temp;
 
    for (i = (size / 2)-1; i >= 0; i--)
        heapify(a, i, size - 1);
 
    for (i = size-1; i >= 1; i--)
    {
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        heapify(a, 0, i-1);
    }
}

void heapify(int *a, int root, int bottom)
{
    int done, maxChild, temp;
 
    done = 0;
    while ((root*2 <= bottom) && (!done))
    {
        if (root*2 == bottom)
            maxChild = root * 2;
        else if (a[root * 2] > a[root * 2 + 1])
            maxChild = root * 2;
        else
            maxChild = root * 2 + 1;
 
        if (a[root] < a[maxChild])
        {
            temp = a[root];
            a[root] = a[maxChild];
            a[maxChild] = temp;
            root = maxChild;
        }
        else
            done = 1;
    }
}

Kaynak:
İ.T.Ü. 2009 – 2010 Güz Dönemi, Advanced Data Structures dersi ders notları, Z.Çataltepe & S.Kabadayı

Algoritma, C++ sıralama algoritmalaları, heap sort

Özellikler:

• Uygulaması kolaydır.
• Küçük Veri kümeleri üzerinde kullanıldığında verimlidir.
• Çoğunluğu zaten sıralanmış olan diziler üzerinde kullanıldığında verimlidir.
• Karmaşıklığı seçmeli sıralama ve kabarcık sıralaması gibi çoğu yalın sıralama algoritmalarından daha verimlidir.
• Kararlı bir sıralama algoritmasıdır (değeri eşit olan öğelerin asıl listedeki göreceli konumlarını değiştirmez)
• Sıralanacak diziyi yerinde sıralar, ek bir bellek alanı gerektirmez. Sıralanacak dizinin hepsinin algoritmanın girdisi olmasına gerek yoktur.
• Dizi parça parça da alınabilir ve sıralama işlemi sırasında diziye yeni veriler eklenebilir.

Çalışma mantığı çok basittir:

Sıralanmak istenen dizinin en başındaki elemandan en sonundakine kadar tüm verileri tek tek kontrol eder ve gerekli yerlere yerleştirir.

Kontrol edeceğimiz değerimizi geçici olarak kaydederiz. Daha sonra kontrol ettiğimiz eleman indisinden itibaren geriye doğru gideriz.

Eğer, geçici olarak tuttuğumuz değer, o anda üzerinde bulunduğumuz değerden küçükse, bir basamak önce üzerinde olduğumuz yere yazarız. Bu sayede sayıyı bir sağa kaydırmış oluruz. Fakat daha sonrasında geçici olarak tuttuğumuz (kontrol edilen) değeri şu anda üzerinde bulunduğumuz yere yazmamız gerekmektedir.

Kısaca dizinin başından sonuna doğru giderken

Bir şekilde anlatmak gerekirse:

Pseudocode:

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        while A[j] > value do
        begin
            A[j + 1] := A[j];
            j := j - 1;
            if j < 0 then exit while;
        end;
        A[j + 1] := value;
    end;
end;

Örnek C++ Kodu:

void insertionsort(int *a, int n)
{
      int i, j, t;
      for (i=1; i<n; i++)
      {
          j=i;
          t=*(a+j);
          while (j>0 && *(a+j-1)>t)
          {
              *(a+j)=*(a+j-1);
              j--;
          }
          *(a+j)=t;
      }
} 

Kaynaklar:
www.wikipedia.org
www.javacoffeebreak.com

Algoritma, C++ sıralama algoritmalaları, insertion sort

Okuma probleminden sonra ikinci bir problemim de dosyaya yazmaktı.

Bu işlem için de ofstream komutunu kullanıyorum. Örnek kodlara aşağıdan ulaşbilirsiniz…

void writeData( string fileName, int *a, int size ) 
{ 
    cout << "file to write: " << fileName << "\n"; 
    char* ch = (char *)malloc(sizeof(char)*(fileName.length()+5)); 
    strcpy(ch, fileName.c_str()); 
    
    ofstream File(ch); 
    if ( File.fail() ) 
    { 
        perror ( "error" ); 
        exit ( EXIT_FAILURE );

    } 
    
    int i = 0; 
    while( i < size ) 
    { 
        File << a[i] << "\n"; 
        i++; 
    }  
     
    File.close(); 
}

C++ ofstream