dh19 dh19 - 2 months ago 33
Java Question

Multithreaded bubblesort using a threshold

So I got this assignment where I had to split an array into two, split those split arrays in 2, etc... up to a certain threshold.

So if my threshold was lets say 1000 it would be like:
10k>2x 5k>4x 2500>8x 1250>16x 625 (numbers in array).

Then I'd have to sort those arrays and merge them:
16x 625 (merged)>8x 1250 (merged)>4x 2500 (merged)>2x 5000 (merged)>1x 10k.
All of them must remain sorted.

So I think I got pretty far but it seems like it does not work the way I want it to. I tried multiple things to figure what is going wrong but I haven#t figured it out which is why I am here.

Can someone help me understand what I am doing wrong and give me a solution?

Bubblesort.java:

package PartThree;

import java.util.ArrayList;
import java.util.List;

public class Bubblesort implements Runnable {
public List<Integer> arrayList;
private int threshold;
private int middle;

public Bubblesort(List<Integer> arrayList, int threshold) {
this.arrayList = arrayList;
this.threshold = threshold;
this.middle = arrayList.size() / 2;
System.out.println(arrayList.size() + " ha");
}

@Override
public void run() {
if (arrayList.size() <= treshold) {
sort();
}else if(threshold<arrayList.size()){
Bubblesort rLeft = new Bubblesort(arrayList.subList(0, middle), threshold);
Bubblesort rRight = new Bubblesort(arrayList.subList(middle, arrayList.size()), threshold);


Thread tLeft = new Thread(rLeft);
Thread tRight = new Thread((rRight));
tRight.start();
tLeft.start();
try {
tLeft.join();
tRight.join();
} catch (InterruptedException e) {
e.printStackTrace();
}

merge(rLeft.arrayList, rRight.arrayList);
System.out.println(arrayList.size() + ":size");
}
}

private void merge(List<Integer> left, List<Integer> right) {
int i = 0, j = 0, k = 0;
List<Integer> temp = new ArrayList<>();
while (i < left.size() && j < right.size()) {
if (left.get(i) < right.get(j)) {
temp.add(k, left.get(i));
i++;
} else {
temp.add(k, right.get(j));
j++;
}
k++;
}
while (i < left.size()) {
temp.add(k, left.get(i));
i++;
k++;
}
while (j < right.size()) {
temp.add(k, right.get(j));
j++;
k++;
}
arrayList = temp;
temp.clear();
}

private void sort() {
int i, j, tijdelijk;
for (j = 0; j < arrayList.size(); j++) {
for (i = 1; i < arrayList.size() - j; i++) {
if (arrayList.get(i - 1) > arrayList.get(i)) {
tijdelijk = arrayList.get(i);
arrayList.set(i, arrayList.get(i - 1));
arrayList.set(i - 1, tijdelijk);
}
}
}
}
}


Implementation:

package PartThree;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class API {
private Random random = new Random();
private List<Integer> array_unsorted_main = new ArrayList<>();
private int maxSize;

private Thread t1;

private void run(){
this.maxSize = 10000;

for (int i = 0; i < maxSize; i++) {
array_unsorted_main.add(random.nextInt(10000));
}
t1 = new Thread(new Bubblesort(array_unsorted_main,1000));
t1.start();
try {
t1.join();
} catch (InterruptedException e) {
e.printStackTrace();
}

}

public static void main(String args[]){
new PartThree.API().run();
}
}


Please help me out, thank you for your time.

Answer

One of your problems is in your merge method you do arrayList = temp; and then do temp.clear() thereby clearing arrayList since it now points to temp.

Remove the temp.clear() statement so arrayList will retain the sorted values.