Swap the minimum and maximum in the array

Radically different search algorithms min. and max. elements with adequate computing power, I did not find. You can, of course, pre-sort the array in order to take the first and last elements, but this is not even O(n) .

The first algorithm consists in passing through the array and comparing each element with the minimum and maximum, which were selected at the beginning of the first option. This is the algorithm that you implemented.

The second algorithm operates according to a similar scheme, but the elements are pre-divided into pairs and sorted within a pair in ascending order. After that, passing through the modified array in the search for the minimum and maximum occurs, however, a pair of elements is considered at once, and only the first element of the pair is compared with the minimum, and the second is compared with the maximum.

 public static void main(String[] args) { System.out.println("Введите кол-во элементов"); Scanner in = new Scanner(System.in); int elementsCount = in.nextInt(); int[] elements = new int[elementsCount]; for (int i = 0; i < elementsCount; i++) { System.out.println("Введите элемент массива под номером " + i); elements[i] = in.nextInt(); } for (int i = 0; i < elementsCount; i++) { int firstElement = elements[i]; for (int j = i + 1; j < elementsCount; j++) { int secondElement = elements[j]; if (firstElement == secondElement) { System.out.println("Все элементы должны быть разными"); return; } } } printArray(elements); firstAlgorithm(elements); secondAlgorithm(elements); } private static void firstAlgorithm(int[] data) { int[] elements = new int[data.length]; System.arraycopy(data, 0, elements, 0, data.length); int minIndex = 0; int min = elements[minIndex]; int maxIndex = 0; int max = elements[maxIndex]; for (int i = 1; i < elements.length; i++) { if (elements[i] < min) { min = elements[i]; minIndex = i; } else if (elements[i] > max) { max = elements[i]; maxIndex = i; } } System.out.println("Первый способ:"); System.out.println("Максимальный элемент массива = " + max); System.out.println("Минимальный элемент массива = " + min); swapElements(elements, minIndex, maxIndex); printArray(elements); } private static void secondAlgorithm(int[] data) { int[] elements = new int[data.length]; System.arraycopy(data, 0, elements, 0, data.length); int[] elementsPairs = new int[data.length]; System.arraycopy(data, 0, elementsPairs, 0, data.length); if (data.length == 1) { System.out.println("Второй способ: в массиве всего один элемент"); return; } HashMap<Integer, Integer> swappedPlaceToRealPlace = new HashMap<>(); for (int i = 0; i < elementsPairs.length; i += 2) { if (i + 1 < elementsPairs.length && elementsPairs[i] > elementsPairs[i + 1]) { swapElements(elementsPairs, i, i + 1); swappedPlaceToRealPlace.put(i, i + 1); swappedPlaceToRealPlace.put(i + 1, i); } } int minIndex = 0; int min = elementsPairs[minIndex]; int maxIndex = 1; int max = elementsPairs[maxIndex]; for (int i = 2; i < elementsPairs.length; i += 2) { int firstIndex = i; int secondIndex = i + 1; if (secondIndex == elementsPairs.length) { secondIndex = i; } if (elementsPairs[firstIndex] < min) { min = elementsPairs[firstIndex]; minIndex = i; } else if (elementsPairs[secondIndex] > max) { max = elementsPairs[secondIndex]; maxIndex = secondIndex; } } if (swappedPlaceToRealPlace.containsKey(minIndex)) { minIndex = swappedPlaceToRealPlace.get(minIndex); } if (swappedPlaceToRealPlace.containsKey(maxIndex)) { maxIndex = swappedPlaceToRealPlace.get(maxIndex); } System.out.println("Второй способ:"); System.out.println("Максимальный элемент массива = " + max); System.out.println("Минимальный элемент массива = " + min); swapElements(elements, minIndex, maxIndex); printArray(elements); } private static void swapElements(int[] array, int i, int j) { int swap = array[i]; array[i] = array[j]; array[j] = swap; } private static void printArray(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } 

It turned out a lot of code. If the elements did not need to be rearranged in places, then it would be significantly less.

In the first algorithm (the firstAlgorithm method), I think everything is clear. In the second (the secondAlgorithm method) elementPairs contains a modified array, in which the sorting is performed within pairs. swappedPlaceToRealPlace used to restore min indexes. and max. elements in the source ( elements ) array after they are in the modified ( elementsPairs ) array. This is necessary, again, only for rearranging elements in places.

From the point of view of theory, both algorithms work in linear time O(n) , however, it is assumed that in practice the second should work somewhat faster due to the smaller number of operations. It is possible that due to the add. costs associated with the creation of additional. copies of the array and saving the indices in the original array, it will not work faster.

The second algorithm is taken from here .