Untitled
import java.util.*;
public class Sorts {
//swap method to be used in all sorting algorithms
private static void swap(int[] arr, int num1, int num2) {
int temp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = temp;
}
//Adapted from Professor Langsam’s notes.
//Plan: Pass through the array, and swap any pair of elements that is out of
order.
public static void bubbleSort(int[] arr) {
boolean isSorted = false; //we will keep track of whether or not the array is
sorted as we go through. At first, we assume that the array is unsorted.
for(int pass = 0; pass < arr.length-1 && !isSorted; pass++) // we only have
to make n-1 passes since if the first n-1 numbers are sorted, the array is sorted.
{
isSorted = true; //we make the hopeful assumption that the array will
be sorted.
for(int i = 0 ; i
isSorted = false; //if a swap is performed, we know that
the array is still unsorted.
swap(arr, i, i+1);
}
}
}
}
//Adapted from McConnell (2008)
//Plan: On any arbitrary pass i through the for loop, all of the elements
arr[0..i-1] is in sorted order.
// Repeatedly copy elements over one by one until you find where the new
element, arr[i] should go.
public static void insertionSort(int[] arr) {
for(int i=1; i
is still in bounds, and newElement is still out of order
arr[location+1] = arr[location]; // copy the elements over
one by one to make space for “newElement”
location–;
}
arr[location+1] = newElement;
}
}
//findMinimumIndex() is a subroutine to selectionSort. It finds the index of
minimum element in the array from arr[start..end-1].
private static int findMinimumIndex (int[] arr, int start, int end) {
int minIndex = start;
int minValue = arr[start];
for(int i=start+1; i
//This function returns the index of the pivot.
//This version of partition() is adapted from CLRS(2009), but there are other
ways of doing this.
private static int partition(int[] arr, int start, int end) {
int pivot = arr[start];
int boundaryIndex = start; //on an arbitrary iteration of this loop, all
elements in arr[start..boundaryIndex] are <=pivot
// and all elements in
arr[boundaryIndex+1..newElement-1] are >=pivot.
for(int newElementIndex = start+1; newElementIndex
the boundary of >= by one element and do no extra work.
//Now, if arr[newElementIndex] <=pivot, we must swap the new element
we encounter with the element on the boundary, thus maintaining the invariant.
if(arr[newElementIndex] <= pivot) {
boundaryIndex++;
swap(arr, boundaryIndex, newElementIndex);
}
}
swap(arr, boundaryIndex, start);
return boundaryIndex;
}
//Quicksort works by partitioning the array into 2 subarrays around a pivot.
//if the pivot is at index x, then all numbers in arr[0..x-1] <=x
// and all elements in arr[x+1..n-1] >=x.
//Because of this property, if we recursively sort each subarray, we will get an
overall
//sorted array.
private static void quicksort(int[] arr, int start, int end) {
if((end-start)<=1)
return;
int pivotIndex = partition(arr, start, end);
quicksort(arr, start, pivotIndex);
quicksort(arr, pivotIndex+1, end);
}
public static void quicksort(int[] arr) {
quicksort(arr, 0, arr.length);
}
public static void shuffle(int[] arr) {
Random r = new Random();
for(int i=0; i