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: 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. C dizisi, en soldaki birimden başlayarak n = n + (n-1) şeklinde artırılacak şekilde yeniden oluşturulur. 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); } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Ö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; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Kaynak: en.wikipedia.org net.pku.edu.cn Tags: , | Categories: C | C++ | Algoritma

Şubat 1021

Radix Sort

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'; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Kaynak: www.brpreiss.com www.cubic.org Tags: , | Categories: Algoritma | C++
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: Sıralanmak istenen veri kümesinden bir sayı pivot olarak seçilir. (Genelde dizinin en son elemanıdır) 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. 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); } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Tags: , | Categories: C++ | Algoritma
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: Sıralı olmayan listeyi ortadan eşit olarak iki alt listeye ayırır. Alt listeleri kendi içinde sıralar. 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]; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Tags: , | Categories: Algoritma | C++
Ç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; } } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Kaynak: İ.T.Ü. 2009 – 2010 Güz Dönemi, Advanced Data Structures dersi ders notları, Z.Çataltepe & S.Kabadayı Tags: , | Categories: Algoritma | C++
Ö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 .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Tags: , | Categories: Algoritma | C++