package heap;
public class Sorting{
public static boolean sorted(int[] xs){
boolean sorted = true;
int length = xs.length;
int i = 1;
while ((i < length) && (sorted == true)){
if (xs[i] >= xs[i-1]) i++;
else sorted = false;
}
return sorted;
}
public static void bubbleSort(int a[]){
for (int i = a.length; --i>=0; ) {
for (int j = 0; j<i; j++) {
if (a[j] > a[j+1]) {
int T = a[j];
a[j] = a[j+1];
a[j+1] = T;
}
}
}
}
public static void merge(int[] xs, int[] ys, int[] zs) {
int n = xs.length;
int m = ys.length;
//int[] zs = new int[n + m];
int i = 0, j = 0, k = 0;
// Main loop
while (i < n && j < m)
if (xs[i] <= ys[j]) zs[k++] = xs[i++];
else zs[k++] = ys[j++];
while(i < n) // Copy rest of xs
zs[k++] = xs[i++];
while(j < m) // Copy rest of ys
zs[k++] = ys[j++];
//return zs;
}
/**
* Mergesort algorithm.
* @param a an array of integers.
*/
public static void mergeSort(int[] a) {
int[] tmpArray = new int[a.length];
mergeSort(a, tmpArray, 0, a.length - 1);
}
/**
* Internal method that makes recursive calls.
* @param a an array of integers.
* @param tmpArray an array to place the merged result.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static void mergeSort(int[] a, int[] tmpArray,
int left, int right) {
if(left < right) {
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + 1, right);
merge(a, tmpArray, left, center + 1, right);
}
}
/**
* Internal method that merges two sorted halves of a subarray.
* @param a an array of integers.
* @param tmpArray an array to place the merged result.
* @param leftPos the left-most index of the subarray.
* @param rightPos the index of the start of the second half.
* @param rightEnd the right-most index of the subarray.
*/
public static void merge(int[] a, int[] tmpArray,
int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Check condition on the inputs, otherwise throw exception
/*if (!((rightPos-1 == (leftPos + rightEnd)/2) &&
(a.length > rightEnd) && (rightEnd >= rightPos) && (rightPos >= leftPos) &&
(a.length == tmpArray.length)))
throw new ArithmeticException();*/
// Main loop
while(leftPos <= leftEnd && rightPos <= rightEnd)
if(a[leftPos] <= a[rightPos])
tmpArray[tmpPos++] = a[leftPos++];
else
tmpArray[tmpPos++] = a[rightPos++];
while(leftPos <= leftEnd) // Copy rest of first half
tmpArray[tmpPos++] = a[leftPos++];
while(rightPos <= rightEnd) // Copy rest of right half
tmpArray[tmpPos++] = a[rightPos++];
// Copy tmpArray back
for(int i = 0; i < numElements; i++, rightEnd--)
a[rightEnd] = tmpArray[rightEnd];
}
public boolean equals(Object obj){
if (obj instanceof Sorting){
return true;
}
return false;
}
/*
public static void main(String[] args){
int[] xs = {5,2,0,1,3,15};
//int[] xs = {1,3,5}; int[] ys = {0,2,3,4};
int[] zs = new int[7];
//merge(xs,ys,zs);
mergeSort(xs);
for (int i = 0;i < xs.length;i++)
System.out.print(xs[i] + " ");
}
*/
}
/**
* Mergesort algorithm.
* @param a an array of Comparable items.
*/
/*
public static void mergeSort(Comparable[] a) {
Comparable[] tmpArray = new Comparable[a.length];
mergeSort(a, tmpArray, 0, a.length - 1);
}
*/
/**
* Internal method that makes recursive calls.
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
/*
private static void mergeSort(Comparable[] a, Comparable[] tmpArray,
int left, int right) {
if(left < right) {
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + 1, right);
merge(a, tmpArray, left, center + 1, right);
}
}
*/
/**
* Internal method that merges two sorted halves of a subarray.
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param leftPos the left-most index of the subarray.
* @param rightPos the index of the start of the second half.
* @param rightEnd the right-most index of the subarray.
*/
/*
private static void merge(Comparable[] a, Comparable[] tmpArray,
int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Main loop
while(leftPos <= leftEnd && rightPos <= rightEnd)
if(a[leftPos].compareTo(a[rightPos]) <= 0)
tmpArray[tmpPos++] = a[leftPos++];
else
tmpArray[tmpPos++] = a[rightPos++];
while(leftPos <= leftEnd) // Copy rest of first half
tmpArray[tmpPos++] = a[leftPos++];
while(rightPos <= rightEnd) // Copy rest of right half
tmpArray[tmpPos++] = a[rightPos++];
// Copy tmpArray back
for(int i = 0; i < numElements; i++, rightEnd--)
a[rightEnd] = tmpArray[rightEnd];
}
*/
|