Write a program to implement bubble sort , insertion sort, selection sort, merge
ID: 3804278 • Letter: W
Question
Write a program to implement bubble sort, insertion sort, selection sort, merge sort and quick sort (pivot = first index) algorithms.
Compute the CPU processing time for all the algorithms for varying input sizes as follows: N = 102, 103, 104, 105, and 106
Use a random number generator to generate the inputs. Obtain the inputs from the following input ranges: 1- 103, 1 - 106, 1 – 109, 1 - 1012
Write down your results as a table (with varying input size and algorithm type) and plot the graph. Present your inferences and/or explanations for your result (in a separate document).
Explanation / Answer
Bubble Sort:
public class BubbleSortExample {
static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
Insertion Sort
public class InsertionSortExample {
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}
}
Selection Sort:
public static void selectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
index = j;//searching for lowest index
}
}
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
Merge Sort:
Quick Sort:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.