1+ package com .cdac .threads .sorting ;
2+ /*
3+ * Author: Suraj Subramanian
4+ *
5+ * Quick Sort implemented using Generics and Multithreading
6+ *
7+ * */
8+ 9+ public class QuickSortMultiThreaded <T extends Comparable <T >> implements Runnable {
10+ 11+ private T arr [];
12+ private int start ;
13+ private int end ;
14+ 15+ // Driver
16+ public static void main (String [] args ) {
17+ Integer [] data = { 5 , 10 , 4 , 1 , 2 , 88 , 11 , 23 , 13 };
18+ new QuickSortMultiThreaded <Integer >().quickSort (data );
19+ 20+ for (Integer integer : data ) {
21+ System .out .println (integer );
22+ }
23+ }
24+ 25+ private int partition (T arr [], int start , int end ) {
26+ // set pivot as last element
27+ T pivot = arr [end ];
28+ int index = start - 1 ;
29+ 30+ for (int i = start ; i <= end - 1 ; i ++) {
31+ if (arr [i ].compareTo (pivot ) < 0 ) {
32+ index ++;
33+ T temp = arr [index ];
34+ arr [index ] = arr [i ];
35+ arr [i ] = temp ;
36+ }
37+ }
38+ 39+ T temp = arr [index + 1 ];
40+ arr [index + 1 ] = arr [end ];
41+ arr [end ] = temp ;
42+ 43+ return index + 1 ;
44+ }
45+ 46+ private void quickSort (T arr []) {
47+ Thread t = new Thread (new QuickSortMultiThreaded <T >(arr , 0 , arr .length - 1 ));
48+ t .start ();
49+ try {
50+ t .join ();
51+ } catch (InterruptedException e ) {
52+ e .printStackTrace ();
53+ }
54+ }
55+ 56+ public QuickSortMultiThreaded (T arr [], int start , int end ) {
57+ super ();
58+ this .arr = arr ;
59+ this .start = start ;
60+ this .end = end ;
61+ }
62+ 63+ public QuickSortMultiThreaded () {
64+ super ();
65+ }
66+ 67+ @ Override
68+ public void run () {
69+ if (start < end ) {
70+ // partition the array
71+ int partition = partition (arr , start , end );
72+ 73+ Thread t1 = new Thread (new QuickSortMultiThreaded <T >(arr , start , partition - 1 ));
74+ Thread t2 = new Thread (new QuickSortMultiThreaded <T >(arr , partition + 1 , end ));
75+ 76+ t1 .start ();
77+ t2 .start ();
78+ 79+ try {
80+ t1 .join ();
81+ } catch (InterruptedException e ) {
82+ e .printStackTrace ();
83+ }
84+ }
85+ }
86+ 87+ }
0 commit comments