Last active
November 19, 2018 03:47
-
-
Save djpeach/7ed95c01843c116ba0f95b8471b7644a to your computer and use it in GitHub Desktop.
STABLE Selection Sort that uses swapping
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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++; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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