CB Sorts
Sorts for Collegeboard
public class SelectionSort {
public int countCompare = 0;
public int countSwap = 0;
public void sort(int[] nums) {
for(int i=0; i<nums.length; i++) {
int min = nums[i];
int minIndex = i;
for (int j=i+1; j<nums.length; j++) {
countCompare = countCompare + 1;
if (nums[j] < min) {
min = nums[j];
minIndex = j;
}
}
countSwap = countSwap + 1;
int temp = nums[i];
nums[i] = min;
nums[minIndex] = temp;
}
}
public int getCountCompares() {
return this.countCompare;
}
public int getCountSwaps() {
return this.countSwap;
}
public void setCountCompare(int count) {
this.countCompare = count;
}
public void setCountSwap(int count) {
this.countSwap = count;
}
public static void main(String[] args) {
int[] test = new int[] { 5, 1, 4, 3, 7, 2};
System.out.println("**** Original Array ****");
for (int i=0; i<test.length; i++) {
System.out.print(test[i] + " ");
}
System.out.println();
System.out.println();
SelectionSort ss = new SelectionSort();
ss.sort(test);
System.out.println("**** Sorted Array ****");
for (int i=0; i<test.length; i++) {
System.out.print(test[i] + " ");
}
}
}
SelectionSort.main(null);
public class InsertionSort {
public int countCompare = 0;
public int countSwap = 0;
public void sort(int[] nums) {
for(int i=0; i<nums.length-1; i++) {
for (int j=i+1; j>0; j--) {
countCompare = countCompare + 1;
if (nums[j] < nums[j-1]) {
countSwap = countSwap + 1;
int temp = nums[j-1];
nums[j-1] = nums[j];
nums[j] = temp;
}
}
}
}
public int getCountCompares() {
return this.countCompare;
}
public int getCountSwaps() {
return this.countSwap;
}
public void setCountCompare(int count) {
this.countCompare = count;
}
public void setCountSwap(int count) {
this.countSwap = count;
}
public static void main(String[] args) {
int[] test = new int[] { 5, 1, 4, 3, 7, 2};
System.out.println("**** Original Array ****");
for (int i=0; i<test.length; i++) {
System.out.print(test[i] + " ");
}
System.out.println();
System.out.println();
InsertionSort is = new InsertionSort();
is.sort(test);
System.out.println("**** Sorted Array ****");
for (int i=0; i<test.length; i++) {
System.out.print(test[i] + " ");
}
}
}
InsertionSort.main(null);
public class BubbleSort{
public int countCompare = 0;
public int countSwap = 0;
public void bubbleSort(int arr[]){
for (int i = 0; i < arr.length - 1; i++){
for (int j = 0; j < arr.length - i - 1; j++){
countCompare += 1;
if (arr[j] > arr[j + 1]) {
countSwap += 1;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public int getCountCompares() {
return this.countCompare;
}
public int getCountSwaps() {
return this.countSwap;
}
public void setCountCompare(int count) {
this.countCompare = count;
}
public void setCountSwap(int count) {
this.countSwap = count;
}
public void toString(int arr[]){
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args){
int[] ll = { 5, 1, 4, 3, 9, 7};
BubbleSort b = new BubbleSort();
b.bubbleSort(ll);
b.toString(ll);
}
}
BubbleSort.main(null);
public class MergeSort {
public int countCompare = 0;
public int countSwap = 0;
public void sort(int[] arr) {
if (arr.length <= 1) {
return;
}
// Divide the array in half
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
// Recursively sort each half
mergeSort(left);
mergeSort(right);
// Merge the sorted halves
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
countCompare += 1;
if (left[i] <= right[j]) {
countSwap += 1;
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
// Copy remaining elements from left or right subarray
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
public int getCountCompares() {
return this.countCompare;
}
public int getCountSwaps() {
return this.countSwap;
}
public void setCountCompare(int count) {
this.countCompare = count;
}
public void setCountSwap(int count) {
this.countSwap = count;
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1, 9, 4};
MergeSort mg = new MergeSort();
mg.sort(arr);
System.out.println(Arrays.toString(arr)); // prints [1, 2, 3, 4, 5, 8, 9]
}
}
MergeSort.main(null);
public class Stats {
public int compares;
public int swaps;
public Stats(int compare, int swap) {
this.compares = compare;
this.swaps = swap;
}
public int getCompares() {
return this.compares;
}
public int getSwaps() {
return this.swaps;
}
}
import java.util.Random;
import java.util.HashMap;
public class TestSorts {
public void print(HashMap<Integer, Stats> map, int averageCompares, int averageSwaps) {
for (int index: map.keySet()) {
Stats stat = map.get(index);
System.out.println(index + " has " + stat.getCompares() + " compares and " + stat.getSwaps() + " swaps.");
}
System.out.println("Average Compares: " + averageCompares);
System.out.println("Average Swaps: " + averageSwaps);
}
public static void main(String[] args) {
HashMap<Integer, Stats> statsInsertion = new HashMap<>();
HashMap<Integer, Stats> statsSelection = new HashMap<>();
HashMap<Integer, Stats> statsBubble = new HashMap<>();
HashMap<Integer, Stats> statsMerge = new HashMap<>();
InsertionSort is = new InsertionSort();
SelectionSort ss = new SelectionSort();
BubbleSort bb = new BubbleSort();
MergeSort mg = new MergeSort();
TestSorts ts = new TestSorts();
Random rd = new Random();
int[] arr = new int[5000];
int averageComparesInsertion = 0;
int averageSwapsInsertion = 0;
long startTime = System.currentTimeMillis();
for (int j = 0; j < 12; j++) {
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt();
}
is.sort(arr);
Stats stats = new Stats(is.getCountCompares(), is.getCountSwaps());
averageComparesInsertion += is.getCountCompares();
averageSwapsInsertion += is.getCountSwaps();
is.setCountCompare(0);
is.setCountSwap(0);
statsInsertion.put(j, stats);
}
long endTime = System.currentTimeMillis();
long elapsedTime = endTime - startTime;
averageComparesInsertion = averageComparesInsertion / 12;
averageSwapsInsertion = averageSwapsInsertion / 12;
System.out.println("Insertion Sort");
System.out.println("Elapsed time: " + elapsedTime + " milliseconds");
ts.print(statsInsertion, averageComparesInsertion, averageSwapsInsertion);
System.out.println("***************************************");
int averageComparesSelection = 0;
int averageSwapsSelection = 0;
startTime = System.currentTimeMillis();
for (int j = 0; j < 12; j++) {
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt();
}
ss.sort(arr);
Stats stats = new Stats(ss.getCountCompares(), ss.getCountSwaps());
averageComparesSelection += ss.getCountCompares();
averageSwapsSelection += ss.getCountSwaps();
ss.setCountCompare(0);
ss.setCountSwap(0);
statsSelection.put(j, stats);
}
endTime = System.currentTimeMillis();
elapsedTime = endTime - startTime;
averageComparesSelection = averageComparesSelection / 12;
averageSwapsSelection = averageSwapsSelection / 12;
System.out.println("Selection Sort");
System.out.println("Elapsed time: " + elapsedTime + " milliseconds");
ts.print(statsSelection, averageComparesSelection, averageSwapsSelection);
System.out.println("***************************************");
int averageComparesBubble = 0;
int averageSwapsBubble = 0;
startTime = System.currentTimeMillis();
for (int j = 0; j < 12; j++) {
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt();
}
bb.bubbleSort(arr);
Stats stats = new Stats(bb.getCountCompares(), bb.getCountSwaps());
averageComparesBubble += bb.getCountCompares();
averageSwapsBubble += bb.getCountSwaps();
bb.setCountCompare(0);
bb.setCountSwap(0);
statsBubble.put(j, stats);
}
endTime = System.currentTimeMillis();
elapsedTime = endTime - startTime;
averageComparesBubble = averageComparesBubble / 12;
averageSwapsBubble = averageSwapsBubble / 12;
System.out.println("Bubble Sort");
System.out.println("Elapsed time: " + elapsedTime + " milliseconds");
ts.print(statsBubble, averageComparesBubble, averageSwapsBubble);
System.out.println("***************************************");
int averageComparesMerge = 0;
int averageSwapsMerge = 0;
startTime = System.currentTimeMillis();
for (int j = 0; j < 12; j++) {
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt();
}
mg.sort(arr);
Stats stats = new Stats(mg.getCountCompares(), mg.getCountSwaps());
averageComparesMerge += mg.getCountCompares();
averageSwapsMerge += mg.getCountSwaps();
mg.setCountCompare(0);
mg.setCountSwap(0);
statsMerge.put(j, stats);
}
endTime = System.currentTimeMillis();
elapsedTime = endTime - startTime;
averageComparesMerge = averageComparesMerge / 12;
averageSwapsMerge = averageSwapsMerge / 12;
System.out.println("Merge Sort");
System.out.println("Elapsed time: " + elapsedTime + " milliseconds");
ts.print(statsMerge, averageComparesMerge, averageSwapsMerge);
}
}
TestSorts.main(null);
For the two sorts above, we will analyze the worst case scenarios for Big O.
In Selection Sort, the worst case scenario is when the entire unsorted sub array has to be iterated through every time. This means that for n elements, we first iterate through n, then n-1, then n-2, and so on. Since each iteration has only constant time operations, we can simply add these up to get n^2/2 + n/2. In Big O terms, this is O(n^2).
For Insertion Sort, it is a very similar scenario, except the worst case involved iterating through the sorted subarray. In other words, we first iterate through 1, then 2, then 3 terms, up to n. This yields the same sum of n^2/2 + n/2, and again this is O(n^2).
O(nlog(n)); logarithmic makes sense as it repeatedly divides in 2.
O(n^2) as it has to do two iterations, and puts the largest value at the end every time. It is less efficient due to having to do more swaps.
Based on Big O notation and number of compares and swaps, both of these sorting methods are similar in performance. More swaps have to be done with Insertion sort however.