Parallel implementation of bubble sort

Question

The main idea of this project is to parallel bubble sort. my approach to this project is,to create one big array and then divide it in to parts ( 4 or 5) based on the number of threads. for instance if the size of the array is 10, i divide it into 2 sub arrays, 0-4 and 5-9, then one thread has to scan the big arrays, and if the value is between 0-4 , assign the the the first sub arrays, if not assign to the next sub-array. then apple the bubble sort algorithm to all sub-arrays simultaneously. finally, all the sub arrays should be added to a thread safe queue. for now i have three class, the main class where i created the array, the U tiles class for shuffling the array, find the min and max of the array and the bubble sort class that has a bubble sorting algorithms. my challenge for now is, how divide the big array into small sub-arrays and fill the sub-array with values. i will appreciate all suggestions and helps. under is my classes.

package com.company;

import javax.xml.transform.sax.SAXSource;
import java.util.Random;

public class Main {

    public static void main(String[] args) {       

        // filling the array with integer values
        int[] anArray = Utils.fillArray((int) 10);          
        Utils.shuffleArray(anArray);

    // find the min and max of the array
        System.out.println("************************");


        BubbleSort sort = new BubbleSort(anArray);
        profiler.start();
        sort.sortMethod();
//        Utils.printArray(anArray);       
        Utils.findMinMax(anArray);

    }

}

package com.company;


import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

public class Utils {

    private static volatile int max;
    private static volatile int min;
    private static int[][] arrays;


      public Utils(int[][] arrays,int[] array) {
        max = array[0];
        min = array[0];
    }

    // taken from the kings class
    // source: http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array
    // Implementing Fisher�Yates shuffle
    public static void shuffleArray(int[] ar) {
        // If running on Java 6 or older, use `new Random()` on RHS here
        ThreadLocalRandom rnd = ThreadLocalRandom.current();
        for (int i = ar.length - 1; i > 0; i--) {
            int index = rnd.nextInt(i + 1);
            // Simple swap
            int a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
        }
    }

    public static void printArray(int[] anArray) {
        System.out.print("Array: ");
        for (int i=0; i< anArray.length; i++){
            System.out.print(anArray[i]+" ");
        }
        System.out.println();
    }


    public static int[] fillArray(int amount) {
        int[] result = new int[amount];
        for (int i=0; i<amount; i++){
            result[i] = i;
        }
        return result;
    }
    public static void findMinMax(int[] array) {
        int i = 0;
        for (; i < (array.length) / 2; i++) {
            int num1 = array[1 * 2];
            int num2 = array[i * 2 + 1];
            if (num1 >= num2) {
                if (num1 > max)
                    max = num1;
                if (num2 < min)
                    min = num2;
            } else {
                if (num2 > max) {
                    max = num2;
                    if (num1 < min)
                        min = num1;
                }
            }
        }
        if (i * 2 < array.length) {
            int num = array[i * 2];
            if (num > max)
                max = num;
            if (num < min)
                min = num;
        }

        System.out.println("min is: " + min);
        System.out.println("max is : " + max);

    }  
                }

public static int getMax() {
        return max;
        }

    public static int getMin() {
        return min;
    }
    public static void print(int[] anArray, int i) {
    }
}

Do you know what divide and conquer means? – Stefan Oct 10 '17 at 08:51 — Stefan, Oct 10 '17 at 08:51

Gleb Saharov · Answer 1 · 2017-10-10T09:38:36.720

I think you should try merge sort, using Fork/Join.

Like here:

import java.util.Random;
import java.util.concurrent.*;

/**
 * Example of Merge Sort using Fork/Join framework.
 *
 * @author L.Gobinath
 */
public class ForkJoinArraySort {
// From Java 7 '_' can be used to separate digits.
public static final int ARRAY_SIZE = 10_000_000;

public static void main(String[] args) {
    // Create a pool of threads
    ForkJoinPool pool = new ForkJoinPool();
    int[] array = createArray(ARRAY_SIZE);
    long startTime;
    long endTime;

    MergeSort mergeSort = new MergeSort(array, 0, array.length - 1);
    startTime = System.currentTimeMillis();

    pool.invoke(mergeSort); // Start execution and wait for result/return

    endTime = System.currentTimeMillis();
    System.out.println("Time taken: " + (endTime - startTime) + " millis");
}

/**
 * Create an array with random numbers.
 * @param  size Size of the array.
 * @return      An array with the given size.
 */
private static int[] createArray(final int size) {
    int[] array = new int[size];
    Random rand = new Random();
    for (int i = 0; i < size; i++) {
        array[i] = rand.nextInt(1000);
    }
    return array;
}
}

/**
 * Extends RecursiveAction.
 * Notice that the compute method does not return anything.
 */
class MergeSort extends RecursiveAction {
private int array[];
private int left;
private int right;

public MergeSort(int[] array, int left, int right) {
    this.array = array;
    this.left = left;
    this.right = right;
}

/**
 * Inherited from RecursiveAction.
 * Compare it with the run method of a Thread.
 */
@Override
protected void compute() {
    if (left < right) {
        int mid = (left + right) / 2;
        RecursiveAction leftSort = new MergeSort(array, left, mid);
        RecursiveAction rightSort = new MergeSort(array, mid + 1, right);
        invokeAll(leftSort, rightSort);
        merge(left, mid, right);
    }
}

/**
 * Merge two parts of an array in sorted manner.
 * @param left  Left side of left array.
 * @param mid   Middle of separation.
 * @param right Right side of right array.
 */
private void merge(int left, int mid, int right) {
    int temp [] = new int[right - left + 1];
    int x = left;
    int y = mid + 1;
    int z = 0;

//There some kind of sort at the leaf
//You can use your BubbleSort class
//***************************************************************
    while (x <= mid && y <= right) {
        if (array[x] <= array[y]) {
            temp[z] = array[x];
            z++;
            x++;
        } else {
            temp[z] = array[y];
            z++;
            y++;
        }
    }
//***************************************************************


    while (y <= right) {
        temp[z++] = array[y++];
    }
    while (x <= mid) {
        temp[z++] = array[x++];
    }

    for (z = 0; z < temp.length; z++) {
        array[left + z] = temp[z];
    }
}
}

(I had my own algorithm, where I used merge sorting, and in the leaf nodes sorting with a bubble sort when I studied algorithmization. But it was a long time ago, I lost it, sorry.)

P.S. I think it will be superfluous to recall that Array.sort will still be faster than the personal implementation of bubble sorting.

the OP asked specifically for bubble sort, not for merge sort. — cello, Oct 10 '17 at 09:26
@cello Actually he's asked for parallel sort - what in fact is merge sort. And at leafs he wants to use bubble sort. — Gleb Saharov, Oct 10 '17 at 09:31

Parallel implementation of bubble sort

1 Answers1