Thursday, May 7, 2015

Multithreaded Quick Sort

Quick sort is a classic example where we can use multiple threads, since execution proceeds on separate paths on separate segments. You can read about classic Quick Sort here.

Quick Sort Steps
1. Select an element as pivot (preferable the last element).
2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)
3. Sort the two segments (Before Pivot and After Pivot) separately

Now check the last step, The two segments can be sorted and processes by 2 separate Threads easily as they don't depend on each other. In turn they can spawn more segments and more threads. For this we can use ThreadPool.

Multi-threaded Quick Sort Steps
1. Select an element as pivot (preferable the last element).
2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)
3. Sort the two segments (Before Pivot and After Pivot) separately via Two Threads

INPUT
2
6
7
5
3
1
8
4

PROCESSING
2
6
7
5
3
1
8
4

2
8
7
5
3
1
4
6

2
1
7
5
3
4
8
6

2
1
3
5
4
7
8
6

2
1
3
4
5
7
8
6

THREAD 1
2
1
3
THREAD 2
5
7
8
6

1
2
3

5
7
6
8

5
6
7
8

FINAL RESULT
1
2
3
4
5
6
7
8