Skip to content

Instantly share code, notes, and snippets.

@katychuang
Created November 13, 2019 12:14
Show Gist options
  • Save katychuang/598134bef08ab1ecf8681412bb5c26d6 to your computer and use it in GitHub Desktop.
Save katychuang/598134bef08ab1ecf8681412bb5c26d6 to your computer and use it in GitHub Desktop.
Some Sorting Algorithm examples
class Sort {
private int[] a; // ref to array a
private int nElems; // number of data items
public Sort(int max) // constructor
{
a = new int[max]; // create the array
nElems = 0; // no items yet
}
public void insert(int value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
public void display() // displays array contents
{
for (int j = 0; j < nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
public void insertionSort() {
for (int i = 0; i < nElems; i++) { // i is dividing line
for (int j = 0; j < i; j++) {
if (a[i] < a[j]) {
swap(i, j);
System.out.print(i + ": (" + i + ", " + j + ") \t");
display();
}
}
} // end for
} // end insertionSort()
private void swap(int one, int two) {
int temp = a[one];
a[one] = a[two];
a[two] = temp;
}
public void selectionSort() {
for (int i = 0; i < nElems-1; i++) {
int min = i;
for (int j = i + 1; j < nElems; j++) {
if (a[min] > a[j]) {
min = j;
}
}
// if (min != i) {
swap(i, min);
System.out.print(i + ": (" + i + ", " + min + ") \t");
display();
// }
} // end for
} // end insertionSort()
public void selectionSortBook() {
int out, in, min;
for(out=0; out<nElems-1; out++) // outer loop
{
min = out; // minimum
for(in=out+1; in<nElems; in++) // inner loop
if(a[in] < a[min] ) // if min greater,
min = in; // we have a new min
swap(out, min); // swap them
} // end for(out)
} // end selectionSort()
}
class SortTest {
public static void main(String[] args) {
int maxSize = 100; // array size
Sort arr = new Sort(maxSize); // create the array
System.out.print("Insertion Sort: ");
arr.insert(90);
arr.insert(51);
arr.insert(3);
arr.insert(9);
arr.insert(10);
arr.insert(12);
arr.insert(8);
arr.insert(11);
Sort two = new Sort(maxSize);;
arr.display();
arr.insertionSort();
arr.display(); // display them again
System.out.print("Selection Sort: ");
two.insert(90);
two.insert(51);
two.insert(3);
two.insert(9);
two.insert(10);
two.insert(12);
two.insert(8);
two.insert(11);
two.display();
two.selectionSort();
two.display(); // display them again
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment