Mergesort :- Only reason to choose this sort is its time complexity is o(nlogn) based on asymptotic analysis.
public class TestClass {
public static void main(String[] args) {
// Initialize the array
int a[] = { 1, 4, 9, 6 };
mergesort(a, 0, a.length - 1);
//Finally print the array
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
private static void mergesort(int[] a, int low, int high) {
// check if low is smaller then high, if not then the array is sorted
if (low < high) {
int middle = low + (high - low) / 2;
//Recursive call to left and right
mergesort(a, low, middle);
mergesort(a, middle + 1, high);
// Combine them both
merge(a, low, middle, high);
}
}
private static void merge(int[] a, int low, int middle, int high) {
//Create temporary error
int[] temp = new int[a.length];
for (int i = low; i <= high; i++) {
temp[i] = a[i];
}
//Initialize variables for looping condition
int i = low;
int j = middle + 1;
int k = low;
//Loop through first and second array and place smallest in main array
while (i <= middle && j <= high) {
if (temp[i] < temp[j]) {
a[k] = temp[i];
i = i + 1;
} else {
a[k] = temp[j];
j = j + 1;
}
k = k + 1;
}
//Loop through left over elements
// Loop through left over elements
while (i <= middle) {
a[k] = temp[i];
i = i + 1;
k = k + 1;
}
while (j <= high) {
a[k] = temp[j];
j = j + 1;
k = k + 1;
} }
}
public class TestClass {
public static void main(String[] args) {
// Initialize the array
int a[] = { 1, 4, 9, 6 };
mergesort(a, 0, a.length - 1);
//Finally print the array
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
private static void mergesort(int[] a, int low, int high) {
// check if low is smaller then high, if not then the array is sorted
if (low < high) {
int middle = low + (high - low) / 2;
//Recursive call to left and right
mergesort(a, low, middle);
mergesort(a, middle + 1, high);
// Combine them both
merge(a, low, middle, high);
}
}
private static void merge(int[] a, int low, int middle, int high) {
//Create temporary error
int[] temp = new int[a.length];
for (int i = low; i <= high; i++) {
temp[i] = a[i];
}
//Initialize variables for looping condition
int i = low;
int j = middle + 1;
int k = low;
//Loop through first and second array and place smallest in main array
while (i <= middle && j <= high) {
if (temp[i] < temp[j]) {
a[k] = temp[i];
i = i + 1;
} else {
a[k] = temp[j];
j = j + 1;
}
k = k + 1;
}
//Loop through left over elements
// Loop through left over elements
while (i <= middle) {
a[k] = temp[i];
i = i + 1;
k = k + 1;
}
while (j <= high) {
a[k] = temp[j];
j = j + 1;
k = k + 1;
} }
}
No comments:
Post a Comment