Skip to content

Instantly share code, notes, and snippets.

@djpeach
Last active November 19, 2018 03:47
Show Gist options
  • Save djpeach/7ed95c01843c116ba0f95b8471b7644a to your computer and use it in GitHub Desktop.
Save djpeach/7ed95c01843c116ba0f95b8471b7644a to your computer and use it in GitHub Desktop.
STABLE Selection Sort that uses swapping
package com.danielpeach.S02_sorting.L02_selection;
public class Int {
private static int cP;
public int v;
public int p;
public Int(int v) {
this.v = v;
this.p = Int.cP++;
}
}
package com.danielpeach.S02_sorting.L02_selection;
import java.util.Arrays;
/**
* Selection sort is very similar to bubble sort. It has the same time
* complexity, that is quadratic, and it moves the largest elements
* to the end.
* It differs in that swapping is only performed once, when the iteration
* reaches the end of the unsorted partition.
*/
public class SelectionSorter {
public static boolean activated = true;
public void main() {
// Int[] intArray = { new Int(20), new Int(35), new Int(20), new Int(-15), new Int(7), new Int(55), new Int(1), new Int(-22) };
// Int[] intArray = { new Int(5), new Int(2), new Int(5), new Int(5) };
Int[] intArray = { new Int(10), new Int(5), new Int(2), new Int(5), new Int(5), new Int(1) };
Arrays.stream(intArray).forEach(el -> System.out.println(el.v + " --- " + el.p));
System.out.println();
sort(intArray, intArray.length);
Arrays.stream(intArray).forEach(el -> System.out.println(el.v + " --- " + el.p));
}
private void sort(Int[] arr, int firstSortedIndex) {
if(firstSortedIndex == 0) {
System.out.println("firstSortedIndex has reached 0, array is sorted\n");
return;
} else {
System.out.println("firstSortedIndex (" + firstSortedIndex + ") is greater than 0, need to find and swap the largest element\n");
int largestIndex = findLargestIndex(arr, firstSortedIndex - 1, firstSortedIndex - 1);
swap(arr, largestIndex, firstSortedIndex - 1);
sort(arr, firstSortedIndex - 1);
}
}
private int findLargestIndex(Int[] arr, int currentIndex, int currentLargestIndex) {
if(currentIndex < 0) {
System.out.println("\tcurrentIndex has reached the beginning of the array, the largest element is: " + arr[currentLargestIndex].v + "\n");
return currentLargestIndex;
} else if(arr[currentIndex].v > arr[currentLargestIndex].v) {
System.out.println("\tcurrentIndex (" + arr[currentIndex].v + ") is larger than currentLargestIndex (" + arr[currentLargestIndex].v + "), updating currentLargestIndex");
currentLargestIndex = currentIndex;
} else {
System.out.println("\tcurrentIndex (" + arr[currentIndex].v + ") is not larger than currentLargestIndex (" + arr[currentLargestIndex].v + ")");
}
System.out.println("Calling findLargestIndex again to see if there is a number larger than " + arr[currentLargestIndex].v);
return findLargestIndex(arr, currentIndex - 1, currentLargestIndex);
}
private void swap(Int[] arr, int i, int j) {
System.out.println("Swapping the element at " + i + " (" + arr[i].v + ") and the element at " + j + " (" + arr[j].v + ")");
if(i == j) {
return;
}
arr[i].v += arr[j].v;
arr[i].p += arr[j].p;
arr[j].v = arr[i].v - arr[j].v;
arr[j].p = arr[i].p - arr[j].p;
arr[i].v -= arr[j].v;
arr[i].p -= arr[j].p;
Arrays.stream(arr).forEach(el -> System.out.print(el + " "));
System.out.println();
System.out.println();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment