The last week I was fighting with algorithms again. 🙂
Thus, I had to implement the mighty heap sort in C# and here is what I came up with. The idea of the code below is the following:
- In line 68 generate a list of unsorted numbers.
- The in line 70 create an object myHeap of type heap, taking the list as argument of the class.
- Thus, the class has two properties – myList and myLen (line 6 and 7), which are used in the constructor.
- The sorting is done with the function “heapsort” of the object heap (line 15).
- This function uses another one, adjust, to sort the list in the correct order. To get a better idea, it is advisable to use breakpoints.
- At the end, we simply print the list with a built-in function of the class heap.
- That’s all folks!
Here comes the 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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
using System; using System.Collections.Generic; public class heap { public List myList = new List(); public int myLen; public heap(List myList, int myLen) { this.myLen = myLen; this.myList = myList; } public void heapsort() { int iValue; for (int i = myLen/2; i >= 0; i--) { adjust(i, myLen-1); } for (int i = myLen-2; i >= 0; i--) { iValue = myList[i + 1]; myList[i + 1] = myList[0]; myList[0] = iValue; adjust(0, i); } } private void adjust(int i, int n) { int iPosition; int iChange; iPosition = myList[i]; iChange = 2 * i; while (iChange <= n) { if (iChange < n && myList[iChange] < myList[iChange + 1]) { iChange++; } if (iPosition >=myList[iChange]) { break; } myList[iChange / 2] = myList[iChange]; iChange *= 2; } myList[iChange / 2] = iPosition; } public string printList() { string myValue = ""; for (int i = 0; i < myLen; i++) { myValue += myList[i] + " "; } return myValue; } public static void Main() { List myList = new List(new int[] {2,5,1,1990,0,6,9,3,7,7,4,8,500,678}); int myLen = myList.Count; heap myHeap = new heap(myList, myLen); Console.WriteLine("Original: {0}",myHeap.printList()); myHeap.heapsort(); Console.WriteLine("Sorted: {0}",myHeap.printList()); } } |
Enjoy it!