FilesExpand file tree

master

/

QuickSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

89 lines (80 loc) · 2.2 KB

master

/

QuickSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

89 lines (80 loc) · 2.2 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

package com.dsj.sorting;

public class QuickSort extends SortingUtils {

public QuickSort() {

super();

}

@Override

void sortArrayOfNumbers() {

sortNumber(0, sizeOfArr - 1);

}

/**

* @param lowerIndex

* Starting index of sub-array

* @param higherIndex

* Ending index of sub-array

*/

private void sortNumber(int lowerIndex, int higherIndex) {

if (lowerIndex < higherIndex) {

int indexOfMovedPivot = partitionOfNumbers(lowerIndex, higherIndex);

sortNumber(lowerIndex, indexOfMovedPivot - 1);

sortNumber(indexOfMovedPivot + 1, higherIndex);

}

}

/**

* @param lowerIndex

* Starting index of sub-array

* @param higherIndex

* Ending index of sub-array

* @return the index which exceeds the altered position of current pivot by

* 1.

*/

private int partitionOfNumbers(int lowerIndex, int higherIndex) {

int i = lowerIndex - 1;

Object pivotElement = unsortedArr[higherIndex];

int itr = lowerIndex;

for (; itr < higherIndex; itr++) {

if ((Double) unsortedArr[itr] <= (Double) pivotElement) {

i++;

if (i != itr) {

swap(i, itr);

}

}

}

swap(++i, higherIndex);

return i;

}

@Override

void sortArrayOfStrings() {

sortStrings(0, sizeOfArr - 1);

}

private void sortStrings(int lowerIndex, int higherIndex) {

if (lowerIndex < higherIndex) {

int indexOfMovedPivot = partitionOfStrings(lowerIndex, higherIndex);

sortStrings(lowerIndex, indexOfMovedPivot - 1);

sortStrings(indexOfMovedPivot + 1, higherIndex);

}

}

private int partitionOfStrings(int lowerIndex, int higherIndex) {

int i = lowerIndex - 1;

Object pivotElement = unsortedArr[higherIndex];

int itr = lowerIndex;

for (; itr < higherIndex; itr++) {

if (((String) unsortedArr[itr]).length() <= ((String) pivotElement).length()) {

i++;

if (i != itr) {

swap(i, itr);

}

}

}

swap(++i, higherIndex);

return i;

}

/**

* Swap the values at index i and itr for the array.

*/

private void swap(int i, int itr) {

Object tempHolder = unsortedArr[i];

unsortedArr[i] = unsortedArr[itr];

unsortedArr[itr] = tempHolder;

}

}