JetBrains Academy: Selection sort in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki
JetBrains Academy: Selection sort in Java
Max-min sorting:
Let's say that an array is max-min sorted if the first element of the array is the maximum element, the second is the minimum, the third is the second maximum and so on. Modify Selection sort such that it can be used for max-min sorting.
Input: the first line contains a number n — the length of an input array. The next line contains n numbers — the elements of the array.
Output: a max-min sorted input array.
import java.util.*;
import java.util.stream.Collectors;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
scanner.nextLine();
int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
.mapToInt(Integer::parseInt)
.toArray();
String outputArray = Arrays.stream(maxMinSort(array))
.mapToObj(Integer::toString)
.collect(Collectors.joining(" "));
System.out.println(outputArray);
}
public static int[] maxMinSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int index = i; // the index of the found min / max
if (i % 2 == 0) {
/* Iterating over the unsorted subarray to find the max */
for (int j = i + 1; j < array.length; j++) {
if (array[j] > array[index]) {
index = j;
}
}
/* Exchanging the found max and the current element */
int currentMax = array[index];
array[index] = array[i];
array[i] = currentMax;
} else {
/* Iterating over the unsorted subarray to find the min */
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[index]) {
index = j;
}
}
/* Exchanging the found min and the current element */
int currentMinimum = array[index];
array[index] = array[i];
array[i] = currentMinimum;
}
}
return array;
}
}
The number of operations:
For different arrays, Selection sort performs a different number of operations. Write a program that for a collection of arrays finds the one for which Selection sort makes the maximum number of operations.
Input: the first line contains two numbers n and m. Each of the following n lines contains an array: m numbers separates by spaces.
Output: the number of an array for which Selection sort performs the maximum number of operations among all other arrays. Assume that each array needs to be sorted in ascending order. Here, an operation is either a changing of the current minimum or exchanging the current minimum with the current index. If there are several arrays requiring the maximum number of operations, print the number of the first one.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int rows = Arrays.stream(scanner.nextLine().split("\\s+"))
.mapToInt(Integer::parseInt)
.toArray()[0];
int[] arrayOfOperationsCount = new int[rows];
for (int i = 0; i < rows; i++) {
int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
.mapToInt(Integer::parseInt)
.toArray();
arrayOfOperationsCount[i] = countOperations(array);
}
System.out.println(findMax(arrayOfOperationsCount));
}
public static int countOperations(int[] array) {
int operations = 0;
/* Selection sorting algorithm */
for (int i = 0; i < array.length - 1; i++) {
int indexOfMinimum = i; // the index of the found min
/* Iterating over the unsorted subarray to find the min */
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[indexOfMinimum]) {
operations++;
indexOfMinimum = j;
}
}
/* Exchanging the found min and the current element */
int currentMinimum = array[indexOfMinimum];
array[indexOfMinimum] = array[i];
array[i] = currentMinimum;
}
return operations;
}
public static int findMax(int[] array) {
int maxIndex = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
maxIndex = i + 1;
}
}
return maxIndex;
}
}
Partial sorting:
At each step, Selection sort finds the smallest (largest) element in an unsorted part of an array and places the found element to the end of a sorted part. So, after k iterations are completed, the first k elements are the smallest (largest) elements of the array in ascending (descending) order. This property allows us to implement a partial sorting algorithm which runs in O(k⋅n) for an array of size n. Your task here is to implement such an algorithm by modifying Selection sort.
Input: the first line contains a number n — the length of an input array. The next line contains n numbers — the elements of the array. The 3rd line contains an integer k.
Output: k largest elements of the input array in descending order.
import java.util.*;
import java.util.stream.Collectors;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
scanner.nextLine();
int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
.mapToInt(Integer::parseInt)
.toArray();
int k = Integer.parseInt(scanner.nextLine());
String result = Arrays.stream(partialSorting(array, k))
.mapToObj(Integer::toString)
.collect(Collectors.joining(" "));
System.out.println(result);
}
public static int[] partialSorting(int[] array, int k) {
int count = 0;
int[] newArray = new int[k];
if (array.length == 0) {
return array;
}
for (int i = 0; i < array.length; i++) {
if (k > count) {
int indexOfMaximum = i; // the index of the found max
/* Iterating over the unsorted subarray to find the max */
for (int j = i + 1; j < array.length; j++) {
if (array[j] > array[indexOfMaximum]) {
indexOfMaximum = j;
}
}
/* Exchanging the found min and the current element */
int currentMax = array[indexOfMaximum];
array[indexOfMaximum] = array[i];
array[i] = currentMax;
newArray[i] = array[i];
}
/* Counting each iteration */
count++;
}
return newArray;
}
}