FilesExpand file tree

 master

/

QuickSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

93 lines (78 loc) · 2.39 KB

 master

/

QuickSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

93 lines (78 loc) · 2.39 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

/**

*

* @author Varun Upadhyay (https://github.com/varunu28)

*

*/

class QuickSort {

/**

* This method implements the Generic Quick Sort

*

* @param array The array to be sorted

* @param start The first index of an array

* @param end The last index of an array

* Sorts the array in increasing order

**/

public static <T extends Comparable<T>> void QS(T array[], int start, int end) {

if (start < end) {

int PIndex = partition(array, start, end);

QS(array, start, PIndex - 1);

QS(array, PIndex + 1, end);

}

}

/**

* This method finds the partition index for an array

*

* @param array The array to be sorted

* @param start The first index of an array

* @param end The last index of an array

* Finds the partition index of an array

**/

public static <T extends Comparable<T>> int partition(T array[], int start, int end) {

T pivot = array[end];

int PIndex = start;

for (int i=start;i<end;i++) {

if (array[i].compareTo(pivot) <= 0) {

swap(array, i, PIndex);

PIndex++;

}

}

swap(array, PIndex, end);

return PIndex;

}

/**

* This method swaps two elements of an array

*

* @param array The array to be sorted

* @param initial The first element

* @param fin The second element

* Swaps initial and fin element

**/

public static <T extends Comparable<T>> void swap(T[] array, int initial, int fin) {

T temp = array[initial];

array[initial] = array[fin];

array[fin] = temp;

}

// Driver Program

public static void main(String[] args) {

// For integer input

int[] arr = {3,4,1,32,0,2,44,111,5};

Integer[] array = new Integer[arr.length];

for (int i=0;i<arr.length;i++) {

array[i] = arr[i];

}

QS(array, 0, arr.length-1);

//Output => 0 1 2 3 4 5 32 44 111

for (int i=0;i<array.length;i++) {

System.out.print(array[i] + " ");

}

System.out.println();

// String Input

String[] array1 = {"c", "a", "e", "b","d"};

QS(array1, 0,array1.length-1);

//Output => a b c d e

for(int i=0; i<array1.length; i++)

{

System.out.print(array1[i]+"\t");

}

}

}