Below has java program to compare time taken between Insertion Sort, Selection Sort, Quick Sort, Merge Sort.
import
java.util.Random;
public class Sorting {
private static final int SIZE = 16000;
private static int[] z = new int[SIZE];
private static int[] a = new int[SIZE];
private static int[] b = new int[SIZE];
public static void main(String[]
args) {
// Create and
populate array with random values
Random rand = new Random();
int[] x = new int[SIZE];
for (int i = 0; i <
x.length; i++) {
x[i]
= rand.nextInt(SIZE);
}
showArray(x);
int[] y = new int[SIZE];
y
= x;
z = x;
a = x;
// Insertion
Sort
long start = System.currentTimeMillis();
insertionSort(x);
long end = System.currentTimeMillis();
System.out.println("It took
" + (end - start) / 1000.0
+
"
seconds to sort " + SIZE + " elements.");
// Selection
sort
start
= System.currentTimeMillis();
selectionSort(y);
end
= System.currentTimeMillis();
System.out.println("It took
" + (end - start) / 1000.0
+
"
seconds to sort " + SIZE + " elements.");
// Quicksort
start
= System.currentTimeMillis();
quickSort(0,
z.length - 1);
end
= System.currentTimeMillis();
System.out.println("It took
" + (end - start) / 1000.0
+
"
seconds to sort " + SIZE + " elements.");
// Mergesort
start
= System.currentTimeMillis();
mergeSort(0,
a.length - 1);
end
= System.currentTimeMillis();
System.out.println("It took
" + (end - start) / 1000.0
+
"
seconds to sort " + SIZE + " elements.");
}
private static void showArray(int[] x) {
System.out.print("[");
for (int i = 0; i <
x.length - 1; i++) {
System.out.print(x[i] + ", ");
}
System.out.println(x[x.length - 1] + "]");
}
// Add sorting
algorithms here // Insertion, Selection, Quicksort, Mergesort
public static void insertionSort(int[] arr) {
int i, j, newValue;
for (i = 1; i <
arr.length; i++) {
newValue
= arr[i];
j
= i;
while (j > 0
&& arr[j - 1] > newValue) {
arr[j]
= arr[j - 1];
j--;
}
arr[j]
= newValue;
}
}
//selection sort
public static void selectionSort(int[] x) {
for (int i = 0; i <
x.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j
< x.length; j++) {
if (x[minIndex]
> x[j]) {
minIndex
= j;
}
}
if (minIndex != i)
{
int temp = x[i];
x[i]
= x[minIndex];
x[minIndex]
= temp;
}
}
}
// Quick sort
public static void quickSort(int low, int high) {
int i = low, j =
high;
// the pivot
element from the middle of the list
int pivot = z[low + (high -
low) / 2];
// divide into
two lists
while (i <= j) {
while (z[i] < pivot)
{
i++;
}
while (z[j] > pivot)
{
j--;
}
if (i <= j) {
swap(i,
j);
i++;
j--;
}
}
if (low < j)
quickSort(low,
j);
if (i < high)
quickSort(i,
high);
}
public static void swap(int i, int j) {
int temp = z[i];
z[i] = z[j];
z[j] = temp;
}
// Merge Sort
public static void mergeSort(int low, int high) {
System.out.print("");
// Check if
low is smaller then high, if not then the array is sorted
if (low < high)
{
// Get the
index of the element which is in the middle
int middle = low +
(high - low) / 2;
// Sort the
left side of the array
mergeSort(low,
middle);
// Sort the
right side of the array
mergeSort(middle
+ 1, high);
// Combine
them both
merge(low,
middle, high);
}
}
public static void merge(int low, int middle, int high) {
// Copy both
parts into the temp array
for (int i = low; i
<= high; i++) {
b[i] = a[i];
}
int i = low;
int j = middle + 1;
int k = low;
// copy the
smallest values from either the left or the right side back
// to the
original array
while (i <= middle
&& j <= high) {
if (b[i] <= b[j]) {
a[k] = b[i];
i++;
}
else {
a[k] = b[j];
j++;
}
k++;
}
// copy the
rest of the left side of the array into the target array
while (i <=
middle) {
a[k] = b[i];
k++;
i++;
}
}
}
Output:
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.