FilesExpand file tree

 master

/

Sorting.cs

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

131 lines (92 loc) · 3.53 KB

 master

/

Sorting.cs

Copy path

Top

File metadata and controls

• Code
• Blame

131 lines (92 loc) · 3.53 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

118

119

120

121

122

123

124

125

126

127

128

129

130

131

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Sorting_Algorithm

{

public class Sorting

{

//THE SORTING ALGORITHMS THAT ARE N^2 OR BETTER AND HAVE TO BE GENERIC:

//QuickSort

//In Place Merge Sort

//Heap Sort

//Insertion Sort

//Intro Sort

public void BubbleSort<T>(T[] inputArray) where T : IComparable

{

T first;

T second;

if (inputArray.Count() <= 1)

return;

for (int i = inputArray.Count() - 1; i != 0; i--)

{

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

{

if (inputArray[j].CompareTo(inputArray[j + 1]) == 1)

{

first = inputArray[j];

second = inputArray[j + 1];

inputArray[j] = second;

inputArray[j + 1] = first;

}

}

}

}

private int Swap<T>(T[] array, int left, int right, int pivot)

{

if (pivot == left)

{

pivot = right;

}

else if (pivot == right)

{

pivot = left;

}

var temp = array[right];

array[right] = array[left];

array[left] = temp;

return pivot;

}

public void QuickSort<T>(ref T[] inputArray) where T : IComparable

{

int leftPosition = 0;

int rightPosition = inputArray.Count() - 1;

int pivotPosition = leftPosition + ((rightPosition - leftPosition) / 2);

T pivotValue = inputArray[pivotPosition];

if (inputArray.Count() < 2)

return;

while (leftPosition < rightPosition)

{

int leftToPivotComparison = inputArray[leftPosition].CompareTo(pivotValue);

int rightToPivotComparison = inputArray[rightPosition].CompareTo(pivotValue);

//The element is in the correct position:

if (leftToPivotComparison == -1)

leftPosition++;

if (rightToPivotComparison == 1)

rightPosition--;

//Both elements are in the wrong Position:

bool leftPosBad = (leftToPivotComparison == 1 || leftToPivotComparison == 0);

bool rightPosBad = (rightToPivotComparison == -1 || rightToPivotComparison == 0);

if (leftPosBad && rightPosBad)

pivotPosition = Swap(inputArray, leftPosition, rightPosition, pivotPosition);

}

//Recurse on left and right partitions:

if (0 < pivotPosition)

{

T[] arrayHead = inputArray.Take(pivotPosition + 1).ToArray();

this.QuickSort<T>(ref arrayHead);

T[] headRemoved = inputArray.Skip(pivotPosition + 1).ToArray();

inputArray = arrayHead.Concat(headRemoved).ToArray();

}

if (pivotPosition <= inputArray.Count() - 3)

{

T[] arrayTail = inputArray.Skip(pivotPosition + 1).ToArray();

this.QuickSort<T>(ref arrayTail);

T[] tailRemoved = inputArray.Take(pivotPosition + 1).ToArray();

inputArray = tailRemoved.Concat(arrayTail).ToArray();

}

}

}

}