dh19 - 1 month ago 11
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);

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)) {
i++;
} else {
j++;
}
k++;
}
while (i < left.size()) {
i++;
k++;
}
while (j < right.size()) {
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 void run(){
this.maxSize = 10000;

for (int i = 0; i < maxSize; i++) {
}
t1.start();
try {
t1.join();
} catch (InterruptedException e) {
e.printStackTrace();
}

}

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

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.