package edu.columbia.cs.cs1007.sort;
public class Sorter {
public static int[] countingSortBuggy(int [] K) {
int [] C = new int[K.length];
int [] S = new int[K.length];
for (int i=0; i < K.length; i++) {
for (int j=0; j < K.length; j++) {
// count the number of elements lower than the given element
if (K[i] > K[j]) {
C[i]++;
}
}
}
for (int i=0; i<K.length; i++) {
int newIdx = C[i];
S[newIdx] = K[i];
}
return S;
}
public static int[] countingSort(int [] K) {
int [] C = new int[K.length];
int [] S = new int[K.length];
for (int i=0; i<K.length; i++) {
for (int j=i+1; j<K.length; j++) {
// count the number of elements lower than the given element
// to the right of the element
if (K[i] < K[j]) {
C[j]++;
} else {
C[i]++;
}
}
}
for (int i=0; i<K.length; i++) {
int newIdx = C[i];
S[newIdx] = K[i];
}
return S;
}
public static int[] selectionSort(int[] K) {
int[] S = new int[K.length];
// copy elements from the input array into the output array
for (int i=0; i<K.length; i++) {
S[i] = K[i];
}
for (int i=0; i<S.length-1; i++) {
int currMin = S[i];
int minIdx = -1;
// find the lowest element to the right of element i
for (int j = i+1; j < S.length; j++) {
if (currMin > S[j]) {
currMin = S[j];
minIdx = j;
}
}
// swap the value at minIdx with the value at i
if (minIdx != -1) {
int tmp = S[i];
S[i] = S[minIdx];
S[minIdx] = tmp;
}
}
return S;
}
public static int[] bubbleSort(int[] K) {
int[] S = new int[K.length];
// copy elements from the input array into the output array
for (int i=0; i<K.length; i++) {
S[i] = K[i];
}
boolean swapped = false;
do {
swapped = false;
for (int i=0; i<S.length-1; i++) {
int j=i+1;
if (S[i] > S[j]) {
int tmp = S[i];
S[i] = S[j];
S[j] = tmp;
swapped = true;
}
}
} while (swapped);
return S;
}
public static int[] sort(int [] inArr) {
if (inArr.length <= 1) {
return inArr;
} else {
// split the array
int medIdx = inArr.length / 2;
int[] leftArr = new int[medIdx];
int[] rightArr = new int[inArr.length - medIdx];
System.arraycopy(inArr, 0, leftArr, 0, leftArr.length);
System.arraycopy(inArr, medIdx, rightArr, 0, rightArr.length);
// sort each part
leftArr = sort(leftArr);
rightArr = sort(rightArr);
// merge the two parts together
return merge(leftArr, rightArr);
}
}
public static int[] merge(int[] left, int[] right) {
int[] mergedArr = new int[left.length + right.length];
int leftIdx =0;
int rightIdx = 0;
int mergedIdx = 0;
// merge for as long as there are elements in both arrays
while ((leftIdx < left.length) && (rightIdx < right.length)) {
if (left[leftIdx] < right[rightIdx]) {
mergedArr[mergedIdx++] = left[leftIdx++];
} else {
mergedArr[mergedIdx++] = right[rightIdx++];
}
}
// copy the remaining elements to the result
if (leftIdx < left.length) {
System.arraycopy(left, leftIdx, mergedArr, mergedIdx, left.length - leftIdx);
} else if (rightIdx < right.length) {
System.arraycopy(right, rightIdx, mergedArr, mergedIdx, right.length - rightIdx);
}
return mergedArr;
}
public static String arrayToString(int[] K) {
StringBuffer res = new StringBuffer();
for (int i=0; i<K.length; i++) {
res.append(K[i] + " ");
}
return res.toString();
}
public static void main(String args[]) {
int[] K = {503, 87, 512, 61, 908, 170, 897, 275, 653, 426};
System.out.println(arrayToString(K));
System.out.println("countingSort");
int[] S = countingSort(K);
System.out.println(arrayToString(S));
System.out.println("selectionSort");
S = selectionSort(K);
System.out.println(arrayToString(S));
System.out.println("bubbleSort");
S = bubbleSort(K);
System.out.println(arrayToString(S));
System.out.println("mergeSort");
S = sort(K);
System.out.println(arrayToString(S));
}
}
|