public class Main {
public static void main(String[] args) {
int[] array = new int[30];
for (int i = 0; i < array.length; i++) {
array[i] = (int) (Math.random() * 20 - 10);
System.out.print(array[i] + " ");
}
System.out.println();

int[] gnome = gnomeSort(array);
for (int value : gnome)
System.out.print(value + " ");
System.out.println();

for (int i = 0; i < array.length; i++) {
array[i] = (int) (Math.random() * 20 - 10);
System.out.print(array[i] + " ");
}
System.out.println();

int[] heap = heapSort(array);
for (int value : heap)
System.out.print(value + " ");
System.out.println();
}

private static int[] gnomeSort(int[] array) {//гномья
int i = 1;
int j = 2;
while (i < array.length) {
if (i <= 0 || array[i - 1] <= array[i]) {
i = j;
j++;
} else {
int tmp = array[i];
array[i] = array[i - 1];
array[i - 1] = tmp;
i--;
}
}
return array;
}

private static void siftDown(int[] array, int root, int bottom) {
int maxChild;
boolean found = false;
while (root * 2 <= bottom && !found) {

if (root * 2 == bottom) maxChild = root * 2;
else if (array[root * 2] > array[root * 2 + 1]) maxChild = root * 2;
else maxChild = root * 2 + 1;

if (array[root] < array[maxChild]) {
int temp = array[root];
array[root] = array[maxChild];
array[maxChild] = temp;
root = maxChild;
} else found = true;
}
}

private static int[] heapSort(int[] array) {//пирамидальная
for (int i = (array.length / 2) - 1; i >= 0; i--)
siftDown(array, i, array.length - 1);

for (int i = array.length - 1; i >= 1; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
siftDown(array, 0, i - 1);
}
return array;
}
}