A sorting algorithm is an algorithm that puts elements of a list in a certain order. Following sorting algorithms are used by most developer/student.
Merge sort is a comparison-based sorting algorithm. It is based on divide-and-conquer paradigm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.
For more information about Merge Sort Algorithm:
http://en.wikipedia.org/wiki/Merge_sort
Implementation and Usage:
int[] arr = new int[10]
{
1, 5, 4, 11, 20, 8, 2, 98, 90, 16
};
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine("Sorted Values:");
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(arr[i]);
//Output:
//Sorted Values:
//1
//2
//4
//5
//8
//11
//16
//20
//90
//98
private void Merge(int[] input, int left, int middle, int right)
{
int[] leftArray = new int[middle - left + 1];
int[] rightArray = new int[right - middle];
Array.Copy(input, left, leftArray, 0, middle - left + 1);
Array.Copy(input, middle + 1, rightArray, 0, right - middle);
int i = 0;
int j = 0;
for (int k = left; k < right + 1; k++)
{
if (i == leftArray.Length)
{
input[k] = rightArray[j];
j++;
}
else if (j == rightArray.Length)
{
input[k] = leftArray[i];
i++;
}
else if (leftArray[i] <= rightArray[j])
{
input[k] = leftArray[i];
i++;
}
else
{
input[k] = rightArray[j];
j++;
}
}
}
private void MergeSort(int[] input, int left, int right)
{
if (left < right)
{
int middle = (left + right) / 2;
MergeSort(input, left, middle);
MergeSort(input, middle + 1, right);
Merge(input, left, middle, right);
}
}
See Also:
Quicksort algorithm is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items.
For more information about Quick Sort Algorithm:
http://en.wikipedia.org/wiki/Quicksort
Implementation and Usage:
int[] arr = new int[10]
{
1, 5, 4, 11, 20, 8, 2, 98, 90, 16
};
QuickSort(arr, 0, arr.Length - 1);
Console.WriteLine("Sorted Values:");
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(arr[i]);
//Output:
//Sorted Values:
//1
//2
//4
//5
//8
//11
//16
//20
//90
//98
private void QuickSort(int[] arr, int start, int end)
{
int i;
if (start < end)
{
i = Partition(arr, start, end);
QuickSort(arr, start, i - 1);
QuickSort(arr, i + 1, end);
}
}
private int Partition(int[] arr, int start, int end)
{
int temp;
int p = arr[end];
int i = start - 1;
for (int j = start; j <= end - 1; j++)
{
if (arr[j] <= p)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = temp;
return i + 1;
}
See Also:
Counting sort is an sorting algorithm for sorting a collection of objects according to keys that are small integers;
For more information about Counting Sort Algorithm:
http://en.wikipedia.org/wiki/Counting_sort
Implementation and Usage:
int[] arr = new int[10]
{
1, 5, 4, 11, 20, 8, 2, 98, 90, 16
};
int[] sortedArray = CountingSort(arr);
Console.WriteLine("Sorted Values:");
for (int i = 0; i < sortedArray.Length; i++)
Console.WriteLine(sortedArray[i]);
//Output:
//Sorted Values:
//1
//2
//4
//5
//8
//11
//16
//20
//90
//98
public int[] CountingSort(int[] array)
{
int[] sortedArray = new int[array.Length];
// find smallest and largest value
int minVal = array[0];
int maxVal = array[0];
for (int i = 1; i < array.Length; i++)
{
if (array[i] < minVal) minVal = array[i];
else if (array[i] > maxVal) maxVal = array[i];
}
// init array of frequencies
int[] counts = new int[maxVal - minVal + 1];
// init the frequencies
for (int i = 0; i < array.Length; i++)
{
counts[array[i] - minVal]++;
}
// recalculate
counts[0]--;
for (int i = 1; i < counts.Length; i++)
{
counts[i] = counts[i] + counts[i - 1];
}
// Sort the array
for (int i = array.Length - 1; i >= 0; i--)
{
sortedArray[counts[array[i] - minVal]--] = array[i];
}
return sortedArray;
}
See Also:
The simplest sorting algorithm is bubble sort. It works by repeatedly stepping through the list to be sorted. It walks from the first element to the last and compares each pair of elements and switches their positions if necessary.
For more information about Bubble Sort Algorithm:
http://en.wikipedia.org/wiki/Bubble_sort
Implementation and Usage:
int[] arr = new int[10]
{
1, 5, 4, 11, 20, 8, 2, 98, 90, 16
};
BubbleSort(arr);
Console.WriteLine("Sorted Values:");
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(arr[i]);
//Output:
//Sorted Values:
//1
//2
//4
//5
//8
//11
//16
//20
//90
//98
private void BubbleSort(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
for (int j = arr.Length - 1; j > i; j--)
{
if (arr[j] < arr[j - 1])
{
Swap(ref arr[j], ref arr[j - 1]);
}
}
}
}
private void Swap(ref int x, ref int y)
{
int temp = x;
x = y;
y = temp;
}
See Also: