forked from VAR-solutions/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathheapsort.cs
More file actions
117 lines (89 loc) · 2.34 KB
/
heapsort.cs
File metadata and controls
117 lines (89 loc) · 2.34 KB
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
using System;
namespace Heap_sort
{
public class MainClass
{
public static void Main (string[] args)
{
int[] mykeys = new int[] {2, 5, -4, 11, 0, 18, 22, 67, 51, 6};
//double[] mykeys = new double[] {2.22, 0.5, 2.7, -1.0, 11.2};
//string[] mykeys = new string[] {"Red", "White", "Black", "Green", "Orange"};
Console.WriteLine("\nOriginal Array Elements :");
printArray (mykeys);
heapSort (mykeys);
Console.WriteLine("\n\nSorted Array Elements :");
printArray (mykeys);
Console.WriteLine("\n");
}
private static void heapSort<T> (T[] array) where T : IComparable<T>
{
int heapSize = array.Length;
buildMaxHeap (array);
for (int i = heapSize-1; i >= 1; i--)
{
swap (array, i, 0);
heapSize--;
sink (array, heapSize, 0);
}
}
private static void buildMaxHeap<T> (T[] array) where T : IComparable<T>
{
int heapSize = array.Length;
for (int i = (heapSize/2) - 1; i >= 0; i--)
{
sink (array, heapSize, i);
}
}
private static void sink<T> (T[] array, int heapSize, int toSinkPos) where T : IComparable<T>
{
if (getLeftKidPos (toSinkPos) >= heapSize)
{
// No left kid => no kid at all
return;
}
int largestKidPos;
bool leftIsLargest;
if (getRightKidPos (toSinkPos) >= heapSize || array [getRightKidPos (toSinkPos)].CompareTo (array [getLeftKidPos (toSinkPos)]) < 0)
{
largestKidPos = getLeftKidPos (toSinkPos);
leftIsLargest = true;
} else
{
largestKidPos = getRightKidPos (toSinkPos);
leftIsLargest = false;
}
if (array [largestKidPos].CompareTo (array [toSinkPos]) > 0)
{
swap (array, toSinkPos, largestKidPos);
if (leftIsLargest)
{
sink (array, heapSize, getLeftKidPos (toSinkPos));
} else
{
sink (array, heapSize, getRightKidPos (toSinkPos));
}
}
}
private static void swap<T> (T[] array, int pos0, int pos1)
{
T tmpVal = array [pos0];
array [pos0] = array [pos1];
array [pos1] = tmpVal;
}
private static int getLeftKidPos (int parentPos)
{
return (2 * (parentPos + 1)) - 1;
}
private static int getRightKidPos (int parentPos)
{
return 2 * (parentPos + 1);
}
private static void printArray<T> (T[] array)
{
foreach (T t in array)
{
Console.Write(' '+t.ToString()+' ');
}
}
}
}