Created
May 19, 2021 22:40
-
-
Save ogerardin/2c27bdfb04507cf6b160c48cb61b3a3d to your computer and use it in GitHub Desktop.
some sort algorithms in Java
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.ogerardin.xpman.util; | |
import lombok.experimental.UtilityClass; | |
import java.util.Comparator; | |
import java.util.List; | |
@UtilityClass | |
public class Sort { | |
public <X> void insertionSort(List<X> list, Comparator<X> comparator) { | |
for (int i = 1; i < list.size(); i++) { | |
X current = list.get(i); | |
int j = i - 1; | |
while (j >= 0 && (comparator.compare(list.get(j), current) > 0)) { | |
list.set(j + 1, list.get(j)); | |
j--; | |
} | |
list.set(j + 1, current); | |
} | |
} | |
public <X> void selectionSort(List<X> arr, Comparator<X> comparator) { | |
for (int i = 0; i < arr.size() - 1; i++) { | |
int minElementIndex = i; | |
for (int j = i + 1; j < arr.size(); j++) { | |
if (comparator.compare(arr.get(minElementIndex), arr.get(j)) > 0) { | |
minElementIndex = j; | |
} | |
} | |
if (minElementIndex != i) { | |
X temp = arr.get(i); | |
arr.set(i, arr.get(minElementIndex)); | |
arr.set(minElementIndex, temp); | |
} | |
} | |
} | |
public <X> void cycleSort(List<X> arr, Comparator<X> comparator) { | |
cycleSort(arr, comparator, arr.size()); | |
} | |
public <X> void cycleSort(List<X> arr, Comparator<X> comparator, int n) | |
{ | |
// count number of memory writes | |
int writes = 0; | |
// traverse array elements and put it to on | |
// the right place | |
for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++) { | |
// initialize item as starting point | |
X item = arr.get(cycle_start); | |
// Find position where we put the item. We basically | |
// count all smaller elements on right side of item. | |
int pos = cycle_start; | |
for (int i = cycle_start + 1; i < n; i++) | |
if (comparator.compare(arr.get(i), item) <0) | |
pos++; | |
// If item is already in correct position | |
if (pos == cycle_start) | |
continue; | |
// ignore all duplicate elements | |
while (comparator.compare(item, arr.get(pos)) == 0) { | |
pos += 1; | |
} | |
// put the item to it's right position | |
if (pos != cycle_start) { | |
X temp = item; | |
item = arr.get(pos); | |
arr.set(pos,temp); | |
writes++; | |
} | |
// Rotate rest of the cycle | |
while (pos != cycle_start) { | |
pos = cycle_start; | |
// Find position where we put the element | |
for (int i = cycle_start + 1; i < n; i++) | |
if (comparator.compare(arr.get(i), item) <0) { | |
pos += 1; | |
} | |
// ignore all duplicate elements | |
while (comparator.compare(item, arr.get(pos)) == 0) { | |
pos += 1; | |
} | |
// put the item to it's right position | |
if (comparator.compare(item, arr.get(pos)) != 0) { | |
X temp = item; | |
item = arr.get(pos); | |
arr.set(pos, temp); | |
writes++; | |
} | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment