Sıralama Algoritmaları

Husamettin Elalmis

Sıralama Algoritmaları

Merhaba arkadaşlar, bu yazıda sizlere sıralama algoritmalarından bahsecedeğim.

Sıralama Algoritması Nedir?

Numerik veya AlfaNumeric verilerden oluşan bir diziyi küçükten büyüğe veya küçükten büyüğe doğru sıralama işlemi Sıralama Algoritması denir.

Yavaş Sıralama Algoritmaları Hangileridir?

En kötü senaryoda O(n^2) kompleksliğine sahip tüm sıralama algoritmaları yavaştır.

• BubleSort

• SelectionSort

• InsertionSort

Hızlı Sıralama Algoritmaları Hangileridir?

O(nk), (nLog(n)) kompleksliğine sahip tüm sıralama algoritmaları hızlıdır diyebiliriz

• ShellSort

• TimSort

• QuickSort

• RadixSort

En hızlı sıralama algoritmaları arasında QuickSort olarak bilinir, ancak RadixSort ve ShellSort algoritmaları serinin uzunluğuna ve sayıların dağılım frekansına bağlı olarak değişkenlik gösterebilmektedir.

QuickSort'un avantajı hızlı olmasıdır, dezavantajı Bellek ihtiyacı olmasıdır (Recursive fonksiyon kullandığı için)

RadixSort'un avantajı recursive fonksiyon kullanmamasıdır, dezavantajı ise sıralama işlemi sırasında ikinci bir diziye ihtiyaç duyar.

ShellSort'un avantajı recursive fonksiyon kullanmamasıdır, avantajı ise aynı dizi üzerinde işlem yapmasıdır.

Yaptığım denemelerde ShellSort, TimSort ve RadixSort'un baskın olarak öne çıktığını gördüm..

Ne Tür Sıralama Algoritmaları Vardır?

• BubbleSort

  • Bubble Sort, bitişik öğelerin yanlış sırada olması durumunda art arda değiştirerek çalışan en basit sıralama algoritmasıdır. Bu algoritma, ortalama ve en kötü durum zaman karmaşıklığı oldukça yüksek olduğundan büyük veri kümeleri için uygun değildir.

• InsertionSort

  • InsertionSort, oyun kartlarını elinizde sıralama şeklinize benzer şekilde çalışan basit bir sıralama algoritmasıdır. Dizi sanal olarak sıralanmış ve sıralanmamış bir bölüme ayrılmıştır. Sıralanmamış kısımdan değerler alınır ve sıralanan kısımda doğru konuma yerleştirilir.

• SelectionSort

  • SelectionSort, sıralanmamış kısımdan minimum öğeyi (artan sırayı dikkate alarak) tekrar tekrar bularak ve başına koyarak bir diziyi sıralar. Algoritma, belirli bir dizide iki alt dizi tutar.

• QuickSort

  • QuickSort, Böl ve Yönet algoritmasıdır. Bir öğeyi pivot olarak seçer ve verilen diziyi seçilen pivot etrafında bölümlere ayırır. Pivottan küçük olanlar sol tarafa, pivottan büyük olanlar sağ tarafa yerleştirilerek bu işlem her bölünen grup için tekrarlanır.

• HeapSort

  • HeapSort, İkili Yığın veri yapısına dayalı karşılaştırmaya dayalı bir sıralama tekniğidir. İlk önce minimum öğeyi bulduğumuz ve minimum öğeyi en başa yerleştirdiğimiz seçim sıralamasına benzer. Kalan elemanlar için aynı işlem tekrarlanır.

• MergeSort

  • MergeSort, Böl ve Yönet algoritmasıdır. Girdi dizisini iki yarıya böler, kendisini iki yarıya çağırır ve sonra sıralanmış iki yarıyı birleştirir. merge işlevi, iki yarıyı birleştirmek için kullanılır. Birleştirme(dizi, l, m, r), dizi[l..m] ve dizi[m+1..r]'nin sıralandığını varsayan ve sıralanmış iki alt diziyi tek bir dizide birleştiren süreçtir.

• TimSort

  • TimSort, diziyi bloklara böler. Bu blokları insertionsort kullanarak tek tek sıralar ve ardından bu blokları mergesort ile birleştirir. Blok boyutu 32 veya 64 arasında değişebilir. Blok boyutu 2'nin kuvveti şeklinde olmalıdır.

• RadixSort

  • RadixSort, (taban sıralama) birler basamağından başlayarak serideki büyük sayının basamak sayısına kadar bu sayıları kutulara yerleştirir. Ardından bu kutulardaki sayılar sırasıyla alttan yukarıya doğru olacak şekilde çekilerek yeni diziye atanır ve seri sıralanmış olur.

• ShellSort

  • ShellSort, esas olarak InsertionSort'un bir çeşididir. InsertionSort'da, öğeleri yalnızca bir konum ileri taşırız. Bir elemanın çok ileriye taşınması gerektiğinde, birçok hareket söz konusudur. ShellSort'un fikri, uzaktaki öğelerin değiş tokuşuna izin vermektir. ShellSort, büyük bir h değeri için diziyi h-sıralı yaparız. 1 olana kadar h değerini düşürmeye devam ederiz. Her h'inci elemanın tüm alt listeleri sıralanmışsa tüm seri sıralanmış olur.

• …

Program Kodu

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using System.Threading;

using System.Threading.Tasks;

namespace SortArge

{

class Program

{

static void Main(string[] args)

{

// rastgele sayılar

int numberCount = 100000;

int minNumber = 1;

int maxNumber = 100000;

List<int> testCollection = GetRandomNumbers(numberCount, minNumber, maxNumber);

Console.WriteLine($"== Sıralama Algoritmaları ==");

Console.WriteLine($"{numberCount.ToString("N0")} adet rastgele sayı oluşturuldu");

Console.WriteLine($"Bu sayılar içerisinde en küçük sayı {testCollection.Min().ToString("N0")}");

Console.WriteLine($"Bu sayılar içerisinde en büyük sayı {testCollection.Max().ToString("N0")}");

Console.WriteLine($"Sıralama işlemleri aynı anda başlatılacak ve süreler her biri için ayrı ayrı tutulup raporlanacak");

Console.WriteLine($"{new string('=', 40)}");

// süre değerleri

List<Tuple<string, long>> results = new List<Tuple<string, long>>();

// 9 adet thread barındıracağız, aynı anda çalıştıracağız

Barrier barrier = new Barrier(9);

// bubbleSort

Task bubbleSortingTask = new Task(

() =>

{

Stopwatch sw = new Stopwatch();

sw.Start();

List<int> arr = new List<int>();

arr.AddRange(testCollection);

barrier.SignalAndWait();

Console.WriteLine("BubbleSort başladı");

BubbleSorting(arr);

sw.Stop();

results.Add(Tuple.Create("BubbleSort", sw.ElapsedMilliseconds));

});

bubbleSortingTask.Start();

// quickSort

Task quickSortingTask = new Task(

() =>

{

Stopwatch sw = new Stopwatch();

sw.Start();

List<int> arr = new List<int>();

arr.AddRange(testCollection);

barrier.SignalAndWait();

Console.WriteLine("QuickSort başladı");

QuickSorting(arr, 0, arr.Count - 1);

sw.Stop();

results.Add(Tuple.Create("QuickSort", sw.ElapsedMilliseconds));

});

quickSortingTask.Start();

// insertionSort

Task insertionSortingTask = new Task(

() =>

{

Stopwatch sw = new Stopwatch();

sw.Start();

List<int> arr = new List<int>();

arr.AddRange(testCollection);

barrier.SignalAndWait();

Console.WriteLine("InsertionSort başladı");

InsertionSorting(arr);

sw.Stop();

results.Add(Tuple.Create("InsertionSort", sw.ElapsedMilliseconds));

});

insertionSortingTask.Start();

// radixSort

Task radixSortTask = new Task(

() =>

{

Stopwatch sw = new Stopwatch();

sw.Start();

List<int> arr = new List<int>();

arr.AddRange(testCollection);

barrier.SignalAndWait();

Console.WriteLine("RadixSort başladı");

var res = RadixSort(arr.ToArray());

sw.Stop();

results.Add(Tuple.Create("RadixSort", sw.ElapsedMilliseconds));

});

radixSortTask.Start();

// mergeSort

Task mergeSortTask = new Task(

() =>

{

Stopwatch sw = new Stopwatch();

sw.Start();

List<int> arr = new List<int>();

arr.AddRange(testCollection);

barrier.SignalAndWait();

Console.WriteLine("MergeSort başladı");

MergeSort(arr.ToArray(), 0, arr.Count - 1);

sw.Stop();

results.Add(Tuple.Create("MergeSort", sw.ElapsedMilliseconds));

});

mergeSortTask.Start();

// selectionSort

Task selectionSortTask = new Task(

() =>

{

Stopwatch sw = new Stopwatch();

sw.Start();

List<int> arr = new List<int>();

arr.AddRange(testCollection);

barrier.SignalAndWait();

Console.WriteLine("SelectionSort başladı");

SelectionSort(arr.ToArray());

sw.Stop();

results.Add(Tuple.Create("SelectionSort", sw.ElapsedMilliseconds));

});

selectionSortTask.Start();

// heapSort

Task heapSortTask = new Task(

() =>

{

Stopwatch sw = new Stopwatch();

sw.Start();

List<int> arr = new List<int>();

arr.AddRange(testCollection);

barrier.SignalAndWait();

Console.WriteLine("HeapSort başladı");

var res = HeapSort(arr.ToArray());

sw.Stop();

results.Add(Tuple.Create("HeapSort", sw.ElapsedMilliseconds));

});

heapSortTask.Start();

// timSort

Task timSortTask = new Task(

() =>

{

Stopwatch sw = new Stopwatch();

sw.Start();

List<int> arr = new List<int>();

arr.AddRange(testCollection);

barrier.SignalAndWait();

Console.WriteLine("TimSort başladı");

var res = timSort(arr.ToArray(), arr.Count);

sw.Stop();

results.Add(Tuple.Create("TimSort", sw.ElapsedMilliseconds));

});

timSortTask.Start();

// ShellSort

Task shellSortTask = new Task(

() =>

{

Stopwatch sw = new Stopwatch();

sw.Start();

List<int> arr = new List<int>();

arr.AddRange(testCollection);

barrier.SignalAndWait();

Console.WriteLine("ShellSort başladı");

var res = ShellSort(arr.ToArray());

sw.Stop();

results.Add(Tuple.Create("ShellSort", sw.ElapsedMilliseconds));

});

shellSortTask.Start();

// task Havuzu

Task[] tasks = { bubbleSortingTask, quickSortingTask, insertionSortingTask, radixSortTask, mergeSortTask, selectionSortTask, heapSortTask, timSortTask, shellSortTask };

// tüm taskları bekle

Task.WaitAll(tasks);

// sonuçlar

Console.WriteLine("== Sonuçlar ==");

var ordered = results.OrderBy(x => x.Item2);

foreach (var item in ordered)

{

Console.WriteLine($"{item.Item1} {item.Item2} miliseconds");

}

Console.WriteLine("ok");

Console.ReadLine();

}

// GetRandomNumbers - Rastgele Sayı Üretir

static List<int> GetRandomNumbers(int numberCount, int minValue, int maxValue)

{

List<int> list = new List<int>();

Random rnd = new Random();

for (int i = 0; i < numberCount; i++)

{

list.Add(rnd.Next(minValue, maxValue + 1));

}

return list;

}

// BubbleSort

static List<int> BubbleSorting(List<int> arr)

{

for (int i = 0; i < arr.Count - 1; i++)

{

for (int j = 1; j < arr.Count - i; j++)

{

if (arr[j] < arr[j - 1])

{

int temp = arr[j - 1];

arr[j - 1] = arr[j];

arr[j] = temp;

}

}

}

return arr;

}

// QuickSorting

static List<int> QuickSorting(List<int> nums, int leftVal, int rightVal)

{

int i = leftVal;

int j = rightVal;

double pivotValue = ((leftVal + rightVal) / 2);

int x = nums[Convert.ToInt32(pivotValue)];

int w = 0;

while (i <= j)

{

while (nums[i] < x)

{

i++;

}

while (x < nums[j])

{

j--;

}

if (i <= j)

{

w = nums[i];

nums[i++] = nums[j];

nums[j--] = w;

}

}

if (leftVal < j)

{

QuickSorting(nums, leftVal, j);

}

if (i < rightVal)

{

QuickSorting(nums, i, rightVal);

}

return nums;

}

// InsertionSorting

static List<int> InsertionSorting(List<int> nums)

{

for (int j = 1; j < nums.Count; j++)

{

int keyValue = nums[j];

int i = j - 1;

while (i >= 0 && nums[i] > keyValue)

{

nums[i + 1] = nums[i];

i = i - 1;

}

nums[i + 1] = keyValue;

}

return nums;

}

// RadixSort

static List<int> RadixSort(int[] arr)

{

int max = arr.Max();

int min = arr.Min();

int range = max - min + 1;

int[] count = new int[range];

int[] output = new int[arr.Length];

for (int i = 0; i < arr.Length; i++)

{

count[arr[i] - min]++;

}

for (int i = 1; i < count.Length; i++)

{

count[i] += count[i - 1];

}

for (int i = arr.Length - 1; i >= 0; i--)

{

output[count[arr[i] - min] - 1] = arr[i];

count[arr[i] - min]--;

}

for (int i = 0; i < arr.Length; i++)

{

arr[i] = output[i];

}

return arr.ToList();

}

// MergeSort

static void MergeArray(int[] nums, int left, int middle, int right)

{

var leftArrayLength = middle - left + 1;

var rightArrayLength = right - middle;

var leftTempArray = new int[leftArrayLength];

var rightTempArray = new int[rightArrayLength];

int i, j;

for (i = 0; i < leftArrayLength; ++i)

leftTempArray[i] = nums[left + i];

for (j = 0; j < rightArrayLength; ++j)

rightTempArray[j] = nums[middle + 1 + j];

i = 0;

j = 0;

int k = left;

while (i < leftArrayLength && j < rightArrayLength)

{

if (leftTempArray[i] <= rightTempArray[j])

{

nums[k++] = leftTempArray[i++];

}

else

{

nums[k++] = rightTempArray[j++];

}

}

while (i < leftArrayLength)

{

nums[k++] = leftTempArray[i++];

}

while (j < rightArrayLength)

{

nums[k++] = rightTempArray[j++];

}

}

static int[] MergeSort(int[] nums, int left, int right)

{

if (left < right)

{

int middle = left + (right - left) / 2;

MergeSort(nums, left, middle);

MergeSort(nums, middle + 1, right);

MergeArray(nums, left, middle, right);

}

return nums;

}

// SelectionSort

static int[] SelectionSort(int[] nums)

{

var arrayLength = nums.Length;

for (int i = 0; i < arrayLength - 1; i++)

{

var smallestVal = i;

for (int j = i + 1; j < arrayLength; j++)

{

if (nums[j] < nums[smallestVal])

{

smallestVal = j;

}

}

var tempVar = nums[smallestVal];

nums[smallestVal] = nums[i];

nums[i] = tempVar;

}

return nums;

}

// HeapSort

static void heapify(int[] arr, int n, int i)

{

int largest = i;

int l = 2 * i + 1;

int r = 2 * i + 2;

if (l < n && arr[l] > arr[largest])

largest = l;

if (r < n && arr[r] > arr[largest])

largest = r;

if (largest != i)

{

int swap = arr[i];

arr[i] = arr[largest];

arr[largest] = swap;

heapify(arr, n, largest);

}

}

static int[] HeapSort(int[] nums)

{

int n = nums.Length;

for (int i = n / 2 - 1; i >= 0; i--)

heapify(nums, n, i);

for (int i = n - 1; i > 0; i--)

{

int temp = nums[0];

nums[0] = nums[i];

nums[i] = temp;

heapify(nums, i, 0);

}

return nums;

}

// TimSort

const int RUN = 32;

static void insertionSort(int[] nums, int left, int right)

{

for (int i = left + 1; i <= right; i++)

{

int temp = nums[i];

int j = i - 1;

while (j >= left && nums[j] > temp)

{

nums[j + 1] = nums[j];

j--;

}

nums[j + 1] = temp;

}

}

static void merge(int[] nums, int left, int middle, int right)

{

int len1 = middle - left + 1, len2 = right - middle;

int[] leftArr = new int[len1];

int[] rightArr = new int[len2];

for (int x = 0; x < len1; x++)

leftArr[x] = nums[left + x];

for (int x = 0; x < len2; x++)

rightArr[x] = nums[middle + 1 + x];

int i = 0;

int j = 0;

int k = left;

while (i < len1 && j < len2)

{

if (leftArr[i] <= rightArr[j])

{

nums[k] = leftArr[i];

i++;

}

else

{

nums[k] = rightArr[j];

j++;

}

k++;

}

while (i < len1)

{

nums[k] = leftArr[i];

k++;

i++;

}

while (j < len2)

{

nums[k] = rightArr[j];

k++;

j++;

}

}

static int[] timSort(int[] nums, int n)

{

for (int i = 0; i < n; i += RUN)

{

insertionSort(nums, i, Math.Min((i + RUN - 1), (n - 1)));

}

for (int size = RUN; size < n; size = 2 * size)

{

for (int left = 0; left < n; left += 2 * size)

{

int mid = left + size - 1;

int right = Math.Min((left + 2 * size - 1), (n - 1));

if (mid < right)

{

merge(nums, left, mid, right);

}

}

}

return nums;

}

// ShellSort

static int[] ShellSort(int[] nums)

{

int n = nums.Length;

for (int gap = n / 2; gap > 0; gap /= 2)

{

for (int i = gap; i < n; i += 1)

{

int temp = nums[i];

int j;

for (j = i; j >= gap && nums[j - gap] > temp; j -= gap)

nums[j] = nums[j - gap];

nums[j] = temp;

}

}

return nums;

}

}

}

Sonuç

• Bu dokumanda sıralama algoritmalarını görmüş olduk

• ShellSort, RadixSort ve TimSort'un daha hızlı çalıştığını gördük.

Saygılarımla,

Hüsamettin ELALMIŞ – 28.05.2022

[e-mail]