Heapsort Algorithm implementation in C#

Today I would like to introduce another sorting algorithm: heapsort. 

Heapsort’s running time is O(n lg n). Heapsort also introduces another algorithm design technique: using a data structure, in this case one we call a "heap", to manage information. The term "heap" was originally coined in the context of heapsort, but it has since come to refer to "garbage-collected storage", such as the programming languages C#, Java provide. My heap data structure is not garbage-collected storage, and whenever I refer to heaps,  I mean a data structure rather than an aspect of garbage collection.

The heapsort algorithm starts by using "Adjust" to build a max-heap on the input array A[1..n], where n=A.Length. Since the maximum element of the array is stored at the root A[1], we can put it into its correct final position by exchanging it with A[n]. If we now discard node n from the heap—and we can do so by simply decrementing A:heap-size—we observe that the children of the root remain max-heaps, but the new root element might violate the max-heap property. All we need to do to restore the max-heap property, however, is call  Adjust(A,1), which leaves a max-heap in A[1..n-1]. The heapsort algorithm then repeats this process for the max-heap of size n - 1 down to a heap of size 2.

Here is code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SortComparison { public class HeapSort<T> where T : IComparable<T> { public static void Sort(T[] A) { //build the initial heap for (int i = (A.Length - 1) / 2; i >= 0; i--) Adjust2(A, i, A.Length - 1); //swap root node and the last heap node for (int i = A.Length - 1; i >= 1; i--) { T Temp = A[0]; A[0] = A[i]; A[i] = Temp; Adjust(A, 0, i - 1); } } private static void Adjust(T[] list, int i, int len) { T Temp = list[i]; int j = i * 2 + 1; while (j <= len) { //more children if (j < len) if (list[j].CompareTo(list[j + 1]) < 0) j = j + 1; //compare roots and the older children if (Temp.CompareTo(list[j]) < 0) { list[i] = list[j]; i = j; j = 2 * i + 1; } else { j = len + 1; } } list[i] = Temp; } } }

Please, feel free post any comments!

Binary Search Algorithm

Generally, to find a value in unsorted array, we should  choose:
1 Take a look through elements of an array one by one, until searched value is found. If required value doesn't exists in  our array, then we will pass all array, all elements. In average, complexity of such an algorithm is  O(n) n- count of elements.
2. Sort array  using  any in place sort algorithms, QuickSort for instance, and then apply Binary Search algorithm.


Algorithm

Algorithm is very simple. It can be done either recursively or iteratively:

1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:

• searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
• searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

I decided  to implement it recursive way with a few enhancements.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class BinarySearch { public int Search(List A, T val) where T : IComparable { if (A == null || A.Count == 0) return -1; return InnerSearch(A, val, 0, A.Count() - 1); } private int InnerSearch(List A, T val, int min, int max) where T : IComparable { int middle = (min + max) / 2; if (max < min || min > max) return -1; if (A[middle].CompareTo(val) == 0) return middle; if (middle == A.Count() - 1) return -1; if (A[min].CompareTo(val) == 0) return min; if (A[max].CompareTo(val) == 0) return max; else if (A[middle].CompareTo(val) > 0) return InnerSearch(A, val, min+1, middle - 1); else return InnerSearch(A, val, middle + 1, max-1); } }

Quicksort Algorithm implementation in C#

Since begining of January 2012, I  tried  spend some spare time of studying  computer science base. Sure,  of course, I know  a lot  from that, but not  all. In addition, it is useful to repeat the basics knowledge.  I decided  create my own library of algorithm and data structures,  not  for  production   using but  for studying and understanding them.  I spent a lot of time  surfing internet  for good articles  regarding  algorithms and data structures. 

Today, I would like to  talk  about QuickSort algorithm. 

Quicksort, like lots of others sort algorithms, applies the divide-and-conquer paradigm. 

Here is the three-step divide-and-conquer process for sorting a

typical subarray Arr[q..w]

• Divide: Partition (rearrange) the array Arr[q..w] into two subarrays  Arr[q..e-1] and  Arr[e+1..w] such that each element of Arr[e..w-1] is less than or equal to Arr[e] which is, in turn, less than or equal to each element of Arr[e+1,w]. Compute the index e as part of this partitioning procedure. 
• Conquer: Sort the two subarrays Arr[q..e-1] and Arr[e+1..w] by recursive calls to quicksort.
• Combine: Because the subarrays are already sorted, no work is needed to combine them: the entire array Arr[q..w] is now sorted.

The quicksort algorithm has a worst-case running time of O(N^2) on an input array of n numbers. Despite this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is O(n lg n), and the constant factors hidden in the O(n lg n) notation are quite small.

Here is my C# implementation using recursion:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SortComparison { class QuickSort<T>; where T :IComparable; { private static T[] A; public static void Sort(T[] arr) { A = arr; InnerSort(0, A.Length - 1); } private static void InnerSort(int low, int high) { int i = low; int j = high; T pivot = A[(low + high) / 2]; do { while (A[i].CompareTo(pivot) < 0) i++; while (A[j].CompareTo(pivot) > 0) j--; if (i <= j) { T tmp = A[i]; A[i] = A[j]; A[j] = tmp; i++; j--; } } while (i <= j); if(i < high) InnerSort(i,high); if(low < j) InnerSort(low,j); } } }

As you  can see  it quit trivial  implementation,  but very efficient.