Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
package sorting;
public class ArrayUtils {
public static boolean isSorted(int[] in){
for(int i = 0; i<in.length-1; i++){
if(in[i+1] < in[i]){
return false;
}
}
return true;
}
public static void printArray(int[] in){
for(int i = 0; i<in.length; i++){
System.out.print(in[i] + ",");
}
System.out.println();
}
//swaps elements at index a and b
public static void swap(int[] in, int indA, int indB){
int temp = in[indA];
in[indA] = in[indB];
in[indB] = temp;
}
}
package sorting;
import javax.management.timer.Timer;
public class BubbleSort {
public static void sort(int[] in){
for(int i = 0; i<in.length-1; i++){
if(in[i+1] < in[i]){
int temp = in[i];
in[i] = in[i+1];
in[i+1] = temp;
}
}
if(!ArrayUtils.isSorted(in)){
sort(in);
}
}
//returns total time in ms that it takes the sort to occur
public static long timedSort(int[] in){
long a = System.currentTimeMillis();
System.out.println(a);
sort(in);
long b = System.currentTimeMillis();
System.out.println(b);
return b-a;
}
public static void printSortInfo(int[] in){
System.out.println("it took " + timedSort(in) + " ms to fully sort a list of " + in.length + " elements");
}
public static void main(String args[]){
int[] inData = RandomGenerator.getData(3000, 1000);
ArrayUtils.printArray(inData);
printSortInfo(inData);
ArrayUtils.printArray(inData);
}
/**
* for each element i
* compare to element i + 1
* if i + 1 < i
* swap i with i + 1
* if(unsorted)
* sort()
*
*/
}
package sorting;
public class Quicksort {
/**
* use final element as pivot
*
*
* @param args
*/
public static void partition(int[] in, int start, int size){
int wall = start;
size = size - 1;
int pivot = start + size;
for(int i = 0; i<size; i++){
if(in[i] < in[pivot]){
ArrayUtils.swap(in, wall, i);
wall++;
}
}
partition(in,start,start+wall);
partition(in,start+wall,in.length);
}
public static void sort(int[] in){
partition(in,0,in.length);
}
public static void main(String args[]){
int[] inData = RandomGenerator.getData(3000, 1000);
ArrayUtils.printArray(inData);
sort(inData);
ArrayUtils.printArray(inData);
}
}
package sorting;
import java.util.Random;
public class RandomGenerator {
public static int[] getData(int elements,int range){
int[] random = new int[elements];
Random r = new Random();
for(int i = 0; i<random.length; i++){
random[i] = r.nextInt(range);
}
return random;
}
public static boolean checkSort(int[] input){
for(int i = 0; i<input.length-1; i++){
if(input[i] > input[i+1]){
return false;
}
}
return true;
}
}
package sorting;
public class SelectionSort {
/**
* for each element
* find lowest element
* add to the end of the sorted portion
*
*/
public static void sort(int[] in){
int minIndex = 0;
for(int i = 0; i<in.length-1; i++){
//for each element
for(int k = i+1; k<in.length; k++){
if(in[minIndex] > in[k]){
minIndex = k;
}
}
ArrayUtils.swap(in, i, minIndex);
minIndex = i+1;
}
}
public static void main(String args[]){
int[] inData = RandomGenerator.getData(3000, 1000);
ArrayUtils.printArray(inData);
sort(inData);
ArrayUtils.printArray(inData);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment