Checkpoint 3
Sorts
import java.util.Random;
public class Tortoise {
protected int comparisons = 0;
protected int swaps = 0;
protected int[] arr;
public Tortoise(int[] arr) {
this.arr = arr;
}
public int getComparisons() {
return this.comparisons;
}
public int getSwaps() {
return this.swaps;
}
public void sort() {
comparisons = 0;
swaps = 0;
// empty implementation for base class
}
// public void toString() {
// for (int i = 0; i < arr.length; i++) {
// System.out.print(arr[i] + " ");
// }
// System.out.println();
// }
public int[] generateArray(int size, int range) {
int[] arr = new int[size];
Random rand = new Random();
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(range) + 1;
}
return arr;
}
}
public class BubbleTort extends Tortoise {
public BubbleTort(int[] arr) {
super(arr);
}
@Override
public void sort() {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
comparisons++;
if (arr[j] > arr[j + 1]) {
swaps++;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
// public class MergeTort extends Tortoise {
// public BubbleTort(int[] arr) {
// super(arr);
// }
// @Override
// public void sort() {
// for (int i = 0; i < arr.length - 1; i++) {
// for (int j = 0; j < arr.length - i - 1; j++) {
// comparisons++;
// if (arr[j] > arr[j + 1]) {
// swaps++;
// int temp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = temp;
// }
// }
// }
// }
// }
public class BubbleTortTester {
public static void main(String[] args) {
int size = 5001;
int range = 500;
for (int j = 0; j < 12; j++) {
int[] arr = new Tortoise().generateArray(size, range);
BubbleTort tortoiseColony = new BubbleTort(arr);
long startTime = System.currentTimeMillis();
tortoiseColony.sort();
// tortoiseColony.toString();
System.out.print("Number of Comparisons: " + tortoiseColony.getComparisons());
System.out.print(" | Number of Swaps: " + tortoiseColony.getSwaps());
long endTime = System.currentTimeMillis();
long elapsedTime = endTime - startTime;
System.out.println(" | Milliseconds Taken: " + elapsedTime);
}
}
}
BubbleTortTester.main(null);
import java.util.Random;
// BUBBLE SORT
public class BubbleTort extends BigTort{
public int comparisons = 0;
public int swaps = 0;
public int getComparisons(){
return this.comparisons;
}
public int getSwaps(){
return this.swaps;
}
public void bubbleTort(int arr[]){
comparisons = 0;
swaps = 0;
for (int i = 0; i < arr.length - 1; i++){
for (int j = 0; j < arr.length - i - 1; j++){
comparisons++;
if (arr[j] > arr[j + 1]) {
swaps++;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public void toString(int arr[]){
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
}
public int[] fiveThousand(){
int[] tortArr = new int[5001];
Random rand = new Random();
for(int i = 0; i < 5001; i++){
tortArr[i] = rand.nextInt(500) + 1;
}
return(tortArr);
}
public static void main(String[] args){
BubbleTort tortoiseColony = new BubbleTort();
for(int j = 0; j < 12; j++){
Long startTime = System.currentTimeMillis();
tortoiseColony.bubbleTort(tortoiseColony.fiveThousand());
// tortoiseColony.toString(tortoiseColony.fiveThousand());
System.out.print("Number of Comparisons: " + tortoiseColony.getComparisons());
System.out.print(" | Number of Swaps: " + tortoiseColony.getSwaps());
Long endTime = System.currentTimeMillis();
Long elapsedTime = endTime - startTime;
System.out.println(" | Milliseconds Taken: " + elapsedTime);
}
}
}
// MERGE SORT
public class MergeTort{
public int comparisons = 0;
public int swaps = 0;
public int getComparisons(){
return this.comparisons;
}
public void setComparisons(int newComparisons) {
this.comparisons = newComparisons;
}
public int getSwaps(){
return this.swaps;
}
public void setSwaps(int newSwaps){
this.swaps = newSwaps;
}
public void mergeTort(int[] arr) {
if (arr == null) {
return;
}
int n = arr.length;
if (n <= 1) {
return;
}
int mid = n / 2;
int[] left = new int[mid];
int[] right = new int[n - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < n; i++) {
right[i - mid] = arr[i];
}
mergeTort(left);
mergeTort(right);
merge(left, right, arr);
}
public void merge(int[] left, int[] right, int[] arr) {
int nLeft = left.length;
int nRight = right.length;
int i = 0, j = 0, k = 0;
while (i < nLeft && j < nRight) {
comparisons++;
if (left[i] <= right[j]) {
swaps++;
arr[k] = left[i];
i++;
}
else {
swaps++;
arr[k] = right[j];
j++;
}
k++;
}
while (i < nLeft) {
comparisons++;
arr[k] = left[i];
i++;
k++;
}
while (j < nRight) {
comparisons++;
arr[k] = right[j];
j++;
k++;
}
}
public int[] fiveThousand(){
int[] tortArr = new int[5001];
Random rand = new Random();
for(int i = 0; i < 5001; i++){
tortArr[i] = rand.nextInt(500) + 1;
}
return(tortArr);
}
public static void main(String[] args){
MergeTort tortoiseColony = new MergeTort();
for(int j = 0; j < 12; j++){
tortoiseColony.setComparisons(0);
tortoiseColony.setSwaps(0);
Long startTime = System.currentTimeMillis();
tortoiseColony.mergeTort(tortoiseColony.fiveThousand());
// tortoiseColony.toString(tortoiseColony.fiveThousand());
System.out.print("Number of Comparisons: " + tortoiseColony.getComparisons());
System.out.print(" | Number of Swaps: " + tortoiseColony.getSwaps());
Long endTime = System.currentTimeMillis();
Long elapsedTime = endTime - startTime;
System.out.println(" | Milliseconds Taken: " + elapsedTime);
}
}
}
System.out.println("Bubble sort has a time complexity of O(n^2)");
BubbleTort.main(null);
System.out.println("---------------------------------------------------------------------------");
System.out.println("Merge sort has a time complexity of O(n log n)");
MergeTort.main(null);