|
import java.time.Duration; |
|
import java.time.Instant; |
|
import java.util.Arrays; |
|
import java.util.Random; |
|
import java.util.Scanner; |
|
|
|
public class Sort { |
|
|
|
private static final Scanner SC = new Scanner(System.in); |
|
|
|
public static void main(String[] args) { |
|
int[] unsorted = testArray(); |
|
int[] bubble = unsorted.clone(); |
|
int[] selection = unsorted.clone(); |
|
int[] insertion = unsorted.clone(); |
|
Instant start, end; |
|
start = Instant.now(); |
|
bubbleSort(bubble); |
|
end = Instant.now(); |
|
System.out.println("Bubble sort took " + Duration.between(start, end)); |
|
start = Instant.now(); |
|
selectionSort(selection); |
|
end = Instant.now(); |
|
System.out.println("Selection sort took " + Duration.between(start, end)); |
|
start = Instant.now(); |
|
insertionSort(insertion); |
|
end = Instant.now(); |
|
System.out.println("Insertion sort took " + Duration.between(start, end)); |
|
System.out.println("Unsorted: " + Arrays.toString(unsorted)); |
|
System.out.println("Bubble sort: " + Arrays.toString(bubble)); |
|
System.out.println("Selection sort: " + Arrays.toString(selection)); |
|
System.out.println("Insertion sort: " + Arrays.toString(insertion)); |
|
} |
|
|
|
private static int[] testArray() { |
|
System.out.print("Min: "); |
|
int min = SC.nextInt(); |
|
System.out.print("Max: "); |
|
int max = SC.nextInt(); |
|
System.out.print("Size: "); |
|
int size = SC.nextInt(); |
|
Random random = new Random(); |
|
int[] numbers = new int[size]; |
|
for (int i = 0; i < numbers.length; i++) { |
|
numbers[i] = random.nextInt(max - min + 1) + min; |
|
} |
|
return numbers; |
|
} |
|
|
|
/** |
|
* Sorts the given array using <b>bubble sort</b> algorithm. |
|
* <p> |
|
* Sorted area on the right is increased in size. |
|
* The first element of unsorted area is compared to the next one and swapped if it is bigger. |
|
* Then the bigger one is compared with the nex one and again swapped. |
|
* Once this has iterated once through the unsorted area it starts again on the left side and repeats |
|
* till all elements are sorted. That way bubbles of similar elements travel slowly from left to right. |
|
* <p> |
|
* Avg. n²/2 (always) comparisons and n²/4 (average, depends on entropy) swaps. |
|
* <p> |
|
* Abort for presorted arrays can be implemented. |
|
*/ |
|
public static void bubbleSort(int[] data) { |
|
for (int leftBoundary = data.length; leftBoundary > 0; leftBoundary--) { |
|
boolean abort = true; |
|
for (int i = 1; i < leftBoundary; i++) { |
|
if (data[i - 1] > data[i]) { |
|
int temp = data[i]; |
|
data[i] = data[i - 1]; |
|
data[i - 1] = temp; |
|
abort = false; |
|
} |
|
} |
|
if (abort) return; |
|
} |
|
} |
|
|
|
/** |
|
* Sorts the given array using <b>selection sort</b> algorithm. |
|
* <p> |
|
* Sorted area on the left is increased in size. |
|
* The unsorted area on the right is searched through, looking for the smallest element. |
|
* When all elements are checked the smallest element is selected and swapped with the first of the unsorted area. |
|
* That way the sorted area increases its size till it covers the entire array. |
|
* <p> |
|
* Avg. n²/2 comparisons and n swaps. |
|
* <p> |
|
* Presorted arrays take the same time as unsorted ones. |
|
*/ |
|
public static void selectionSort(int[] data) { |
|
for (int sorted = 0; sorted < data.length; sorted++) { |
|
int smallestPos = sorted; |
|
for (int i = sorted; i < data.length; i++) { |
|
if (data[i] < data[smallestPos]) { |
|
smallestPos = i; |
|
} |
|
} |
|
int tmp = data[sorted]; |
|
data[sorted] = data[smallestPos]; |
|
data[smallestPos] = tmp; |
|
} |
|
} |
|
|
|
/** |
|
* Sorts the given array using <b>insertion sort</b> algorithm. |
|
* <p> |
|
* Sorted area on the left is increased in size. The first element of unsorted area is picked |
|
* and compared with the elements in the sorted area from right to left. |
|
* All elements that are bigger than the picked are shifted one to the right. |
|
* <p> |
|
* Avg. n²/4 comparisons and n²/8 swaps, max. doubled amount. |
|
* <p> |
|
* Detects and aborts for presorted arrays. |
|
*/ |
|
public static void insertionSort(int[] data) { |
|
for (int i = 1; i < data.length; i++) { |
|
int value = data[i]; |
|
int newPos = i; |
|
for (newPos = i; newPos > 0; newPos--) { |
|
if (data[newPos - 1] > value) { |
|
data[newPos] = data[newPos - 1]; |
|
} else { |
|
break; |
|
} |
|
} |
|
data[newPos] = value; |
|
} |
|
} |
|
} |
