1. Introduction
Briefly explain the purpose the background of the multithreaded
sorting application. Highlight the importance of sorting algorithms and the
need for efficient sorting techniques in various domains.
Multithreaded sorting application
is a program that sorts a data set using multiple threads and single thread.
Each multi-thread is responsible for sorting a portion of the data set, and the
results are then merged together to form the sorted output.
Here
are some of the most common sorting algorithms that can be used in
multithreaded applications
-
Quicksort
-
Merge sort
-
Tree sort
-
Bubble sort
-
Insertion sort
The choice of
sorting algorithm will depend on the specific application and the
characteristics of the data set. For my opinion, I am going to choose two algorithms
are insertion sort is a good choice sort data sets that are randomly distributed, while merge
sort is a good choice for data sets that are already partially sorted
2. 2. Objective
The main objective of a multithreaded sorting application is improved
performance and reduced execution time compared to traditional single-threaded
sorting algorithms. By using multiple threads, it can distribute the task of
sorting data across available CPU cores or processing units, thereby making
better use of system resources and achieving faster results.
3. 3. Sorting algorithm
3.1
Insertion sort algorithm
Insertion sort is a simple sorting algorithm that works by repeatedly
inserting a new element into the correct position in a sorted list. The
algorithm starts with the first element in the list, which is considered to be
sorted. Then, each subsequent element is inserted into the sorted list in its
correct place.
How to
insertion sort work:
1. We start by making the second element of the given array, i.e. element at index
1, the key.
2. We compare
the key element with the element(s) before it, in this case,
element at index 0:
• If the key element is less than the first element, we insert the key
element
before the first
element.
• If the key
element is greater than the first element, then we insert it after
the first
element.
3. Then, we make the third element of the array as
key and will compare it with
elements to it's
left and insert it at the right position.
4.
And we go on repeating this, until the array is
sorted.
3.1 3.2 merge sort algorithm
Sure. Merge sort is a sorting algorithm that works by
dividing an array into smaller subarrays, sorting each subarray, and then
merging the sorted subarrays back together to form the final sorted array.
·
Merge Sort uses a
divide and conquer paradigm for sorting.
·
It divides the
problem into sub problems and solves them individually.
·
It then combines
the results of sub problems to get the solution of the original problem
Merge Sort
Algorithm works in the following steps-
• It divides
the given unsorted array into two halves- left and right sub arrays.
• The sub
arrays are divided recursively.
• This
division continues until the size of each sub array becomes 1.
• After each
sub array contains only a single element then merge procedure is
called.
• The merge
procedure combines these trivially sorted arrays to produce a final sorted array.
4.4. Result
The figure of graph that compares the execution time of a task
with a single thread and multiple threads. The x-axis represents the number of
threads, while the y-axis represents the execution time. The line labeled
"Single Thread" indicates that the execution time increases as the
number of array increases. This is because each thread must share the CPU, so
the less time each thread has to execute its code as the number of threads
grows. The line labeled "multi-threads" indicates that the execution
time decreases as the number of array increases. This is because multiple
threads can run concurrently, which
For example,
consider the array size of 100: the single-threaded approach takes 2 ms to
complete, while the multi-threaded approach takes only 1 ms. Similarly, for
larger array sizes, the multi-threaded approach consistently demonstrates
faster execution times compared to the single-threaded approach and when the
array size is 500, the improvement from using multi-threaded processing is
quite significant, but as the array size reaches 500,000, the improvement
becomes less pronounced. This is likely because as the array size gets larger,
the overhead of managing and synchronizing multiple threads becomes more
significant, which can offset some of the benefits of parallel.
5. Conclusion
based on the graph
comparing single and multi-thread, we can conclude that as the array size
increases, the processing time also increases. Additionally, using
multi-threaded processing can result in faster processing times compared to
single-threaded processing, particularly for larger array sizes. However, the
improvement in processing time diminishes as the array size gets larger.
In general, the
multi-threaded approach yields significant speed improvements over the
single-threaded approach, which is expected as it allows for parallel
processing and utilization of multiple CPU cores.
+ Source code in java
Main:
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Random;
public class Main {
public static void main(String[] args) throws InterruptedException {
int ArraySize, i, j, k; // Set matrix size by Rows = Column
long begintime, endtime; // Start and stop time sortime calculate
Scanner scan = new Scanner(System.in);
System.out.print("Input size of array element: ");
ArraySize = scan.nextInt();
Random rand = new Random();
// Input array element by random
int[] array = new int[ArraySize];
for(i=0; i<ArraySize; i++)
{
array[i] = rand.nextInt(100000000);
}
begintime = System.currentTimeMillis();
// Separate array to two part (array1 & array2)
int array1[];
int array2[];
if(ArraySize % 2 == 0)
{
array1 = new int[ArraySize/2];
array2 = new int[ArraySize/2];
for(i=0; i<array1.length; i++)
{
array1[i] = array[i];
array2[i] = array[(ArraySize/2)+i];
}
}
else
{
array1 = new int[(ArraySize+1)/2];
array2 = new int[(ArraySize-1)/2];
for(i=0; i<array1.length; i++)
{
array1[i] = array[i];
}
for(i=0; i<array2.length; i++)
{
array2[i] = array[array1.length + i];
}
}
endtime = System.currentTimeMillis();
// Print original array element
System.out.println("\nOriginal Array, generate by random");
System.out.println(Arrays.toString(array));
System.out.print("\nSeparate to two parts for calculate multi thread\n");
System.out.println(" Part 1: " + Arrays.toString(array1));
System.out.println(" Part 2: " + Arrays.toString(array2));
//Single Thread (1 Thread)
// Print sorted array element using single thread
begintime = System.currentTimeMillis();
Try_insertionSort ResultSthread = new Try_insertionSort(array, ArraySize, ArraySize);
Thread Sthread = new Thread(ResultSthread);
Sthread.start();
Sthread.join();
System.out.println("\nSingle thread, sorted array");
System.out.println(Arrays.toString(ResultSthread.result()));
endtime = System.currentTimeMillis();
long timesingle = endtime - begintime;
// Multi Thread (2 Threads) calculate
//Print sorted array element using multi thread
begintime = System.currentTimeMillis();
Try_insertionSort ResultThread1 = new Try_insertionSort(array1, array1.length, array1.length);
Thread Thread1 = new Thread(ResultThread1);
Thread1.start();
Thread1.join();
Try_insertionSort ResultThread2 = new Try_insertionSort(array2, array2.length, array2.length);
Thread Thread2 = new Thread(ResultThread2);
Thread2.start();
Thread2.join();
System.out.println("\n\nMultiple thread, sorted array");
System.out.println("thread 1: " + Arrays.toString(array1));
System.out.println("Thread 2: " + Arrays.toString(array2));
endtime = System.currentTimeMillis();
long timemulti = endtime - begintime;
i=0; j = 0; k=0;
int [] mergedArray = new int[array1.length + array2.length];
// sort array after divide to sublist already
while(i<array1.length && j< array2.length)
{
if(array1[i] <= array2[j])
{
mergedArray[k++] = array1[i++];
}
else
{
mergedArray[k++] = array2[j++];
}
}
while (i< array1.length)
{
mergedArray[k++] = array1[i++];
}
while (j< array2.length)
{
mergedArray[k++] = array2[j++];
}
System.out.println("Merged Thread: " + Arrays.toString(mergedArray));
System.out.println("---------------------------------");
System.out.println("Elapsed Time single thread: " +timesingle+ " mili seconds");
System.out.println("Elapsed Time Maged time : " + timemulti+ " mili seconds");
}
}
------------------------------------------------------------------------------------------------------------------------
create function for sort
public class Try_insertionSort implements Runnable {
private int array[];
private int i, j, n;
public Try_insertionSort(int[] array, int i, int j) {
n = array.length;
this.array = array;
this.i = i;
this.j = j;
}
public int[] result() {
return array;
}
@Override
public void run() {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
}
