Skip to Main Content

Java Programming

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

How to limit threads in a Java QuickSort algorithm.

864501May 25 2011 — edited Jun 2 2011
With the following piece of code, I quickly run into OutOfMemory exceptions, since the code starts creating Threads exponentially. However, after waiting for a long time (for all the exception texts to print out, obviously making it slower than running it with one thread only), the program eventually ends with the correct result. Is there a way to run the code as is, but making sure that no more that x threads are running at a time?

things I have tried:
- sleeping the current thread - makes it slower than one-thread.
- looping blank while Thread.activeCount() > x - doesnt work at all
- suspending resuming threads based on the activeCount - doesnt work too

Code:
import java.util.*;
import java.io.*;

public class ThreadedSort extends Thread{

private ArrayList<Integer> _list;

public ThreadedSort()
{
_list = new ArrayList<Integer>();
}

public ThreadedSort(ArrayList<Integer> List)
{
_list = List;
}

public void run()
{
threadQuickSort();
}

public void threadQuickSort()
{
try{
if (_list.size() < 2)
return;

Integer pivot = new Integer(_list.get(_list.size()-1));

ArrayList<Integer> left = new ArrayList<Integer>();
ArrayList<Integer> right = new ArrayList<Integer>();

//ListIterator iter = arr.listIterator();
// *** optimize here
for (int i = 0; i < _list.size()-1; i++) {
Integer next = (Integer)_list.get(i);
if (next <= pivot)
left.add(next);
else
right.add(next);
}
ThreadedSort LeftThread = new ThreadedSort(left);
ThreadedSort RightThread = new ThreadedSort(right);

// System.out.println(Thread.currentThread().getName()+" --> "+Thread.activeCount());
// Thread.sleep(4000);

LeftThread.start();
RightThread.start();
// System.out.println(Thread.currentThread().getName()+" --> "+Thread.activeCount());
LeftThread.join();
RightThread.join();

_list.clear();
list.addAll(LeftThread.list);
_list.add(pivot);
list.addAll(RightThread.list);
}catch (InterruptedException ie) { ie.printStackTrace(); }
return;
}

public static void main(String[] args) { ///////////////////////////////////////////

Random rand = new Random();
ArrayList arr1 = new ArrayList();

long before_threadedQuickSort, after_threadedQuickSort;

try{
FileWriter fout = new FileWriter("out.txt");
BufferedWriter bw = new BufferedWriter(fout);

before_populate = System.currentTimeMillis();
for (int i = 0; i< 2000; i++){//***
arr1.add(rand.nextInt(2000000));
}
after_populate = System.currentTimeMillis();

ThreadedSort sorter3 = new ThreadedSort(new ArrayList(arr1));

before_threadedQuickSort = System.currentTimeMillis();
sorter3.start();
sorter3.join();
after_threadedQuickSort = System.currentTimeMillis();

bw.write("time for threadedQuickSort: " + (after_threadedQuickSort - before_threadedQuickSort)); bw.newLine();
bw.newLine();

arr1.clear();

}
bw.close();

}catch (Exception IOException){};
System.out.printf("\n\n");
} //end of main

} //end of class
Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on Jun 30 2011
Added on May 25 2011
25 comments
666 views