Skip to content

Instantly share code, notes, and snippets.

@itarato
Created December 15, 2016 17:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save itarato/7b3597ab378ffebd4b6a13245e3f4a6e to your computer and use it in GitHub Desktop.
Save itarato/7b3597ab378ffebd4b6a13245e3f4a6e to your computer and use it in GitHub Desktop.
Multithreaded quick sort - attempt
package com.company;
class QuickSortThreaded {
private int[] l;
QuickSortThreaded(int[] l) {
this.l = l;
long start = System.nanoTime();
new Sorter(l, 0, l.length - 1).sort(0, l.length - 1);
System.out.printf("Threaded QS: %d\n", System.nanoTime() - start);
}
}
class Sorter extends Thread {
private static final int THREAD_LIMIT = 100;
private final int[] l;
private final int f;
private final int t;
private static int threadCount = 0;
private synchronized static void incThreadCount(int n) { threadCount += n; }
private synchronized static void decThreadCount(int n) { threadCount -= n; }
private synchronized boolean isThreadAllowed() {
return threadCount <= THREAD_LIMIT;
}
Sorter(int[] l, int f, int t) {
this.l = l;
this.f = f;
this.t = t;
}
void sort(int f, int t) {
if (f < t) {
int mid = partition(f, t);
if (isThreadAllowed()) {
incThreadCount(2);
new Sorter(l, f, mid - 1).start();
new Sorter(l, mid + 1, t).start();
decThreadCount(2);
} else {
sort(f, mid - 1);
sort(mid + 1, t);
}
}
}
private int partition(int f, int t) {
int ref = l[t];
int j = f - 1;
for (int i = f; i < t; i++) {
if (ref >= l[i]) {
j++;
int temp = l[i];
l[i] = l[j];
l[j] = temp;
}
}
int temp = l[j + 1];
l[j + 1] = l[t];
l[t] = temp;
return j + 1;
}
@Override
public void run() {
sort(f, t);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment