Selection Sort – это простой алгоритм сортировки. В этой статье мы собираемся реализовать это с помощью java для сортировки массива от наименьшего к наибольшему элементу. Мы тоже поговорим об этом временной сложности . Давайте погрузимся в это!
Давайте начнем с создания вашего первого java-файла SelectionSort.java
В этом файле мы собираемся создать метод с именем sort , который возвращает массив целых чисел.
int[] sort(int[] arr) {
int index;
//looping the unsorted list
for (int first = 0; first < arr.length; first++) {
}
}
Здесь мы начнем с создания целочисленной переменной с именем index (который мы собираемся использовать позже) и цикл, который выполняет итерацию по всему массиву. Затем мы собираемся сделать так, чтобы index имел то же значение, что и first , сделать еще один цикл и реализовать наше условие… Да, это много! Позвольте мне объяснить.
int[] sort(int[] arr) {
int index;
//looping the unsorted list
for (int first = 0; first < arr.length; first++) {
//index starts at first but changes in every loop
index = first;
//then every loop the index is compared with all numbers
//except the one we are comparing to (the index)
for (int i = first + 1; i < arr.length; i++) {
//check if value is lower
if (arr[i] < arr[index]) {
//if it is, change index to it
index = i;
}
}
}
}
Давайте начнем объяснять этот второй цикл, который мы сделали. Этот цикл находится внутри первого цикла, поэтому каждый раз, когда мы повторяем первый цикл один раз, мы получаем значение списка и проходим через все элементы в массиве, используя второй цикл, чтобы мы могли сравнить значение, полученное в первом цикле, со всеми элементами в массиве с помощью второго цикла. вторая петля.
важный: Во втором цикле мы делаем it + 1 , потому что мы зацикливаем каждый элемент в списке, ИСКЛЮЧАЯ только тот, который мы на самом деле сравниваем, потому что значение, которое у нас есть, никогда не будет меньше самого себя.
После того, как были выполнены два цикла, мы создаем условие внутри второго цикла, где мы проверяем, являются ли элементы в цикле for ( arr[i] ) меньше, чем значение, которое мы получили с помощью первого цикла ( arr[index] ) . Если условие верно, мы делаем индекс, который пока содержит наше меньшее число, индексом найденного меньшего числа. Условие if проверяет каждое число во втором цикле до конца, получая меньшее число в массиве и сохраняя его индекс с помощью index .
Теперь, когда наш второй цикл подошел к концу, и у нас есть индекс нашего наименьшего числа, нам нужно поменять местами позицию, в которой он находится
int[] sort(int[] arr) {
int index;
//looping the unsorted list
for (int first = 0; first < arr.length; first++) {
//index starts at first but changes in every loop
index = first;
//then every loop the index is compared with all numbers
//except the one we are comparing to (the index)
for (int i = first + 1; i < arr.length; i++) {
//check if value is lower
if (arr[i] < arr[index]) {
//if it is, change index to it
index = i;
}
}
//holds the value of the minimum we found
int temp = arr[index];
//places the value that was in the start at the place we found our index
arr[index] = arr[first];
//puts the value from the index in the start
arr[first] = temp;
}
//terminate the loop and return array sorted
return arr;
}
Здесь у нас есть готовый метод сортировки, я поместил все это здесь, чтобы вы не запутались в том, где находятся фрагменты кода в общей картине, но мы будем говорить о конце, части обмена и возврата:
//holds the value of the minimum we found
int temp = arr[index];
//places the value that was in the start at the place we found our index
arr[index] = arr[first];
//puts the value from the index in the start
arr[first] = temp;
}
//terminate the loop and return array sorted
return arr;
}
Я собираюсь поговорить об этом, приведя пример, который был сделан в части алгоритмов CS50 (настоятельно рекомендую), у вас есть две чашки, одна с синей жидкостью, а другая с красной жидкостью. Вы хотите поменять местами синюю жидкость из 1 чашки, чтобы она была в 2 чашках, и красную жидкость из 2 чашек, чтобы она была в 1 чашке, не смешивая. Что ты делаешь? Хороший способ сделать это – иметь “Временную чашку” , 3 чашки, которые будут содержать вашу синюю жидкость, чтобы вы могли налить красную жидкость в 1 чашку, а затем налить синюю жидкость в 2 чашки.
В коде мы делаем то же самое! Мы создаем временную переменную int temp и присваиваем ему значение наименьшего числа, которое мы нашли. Затем мы делаем значение arr[index] , то есть текущее наименьшее число, значением первого цикла, и мы делаем значение первого цикла временной переменной, наименьшим числом.
С этим мы сделали наш обмен! Итак, после этого первая итерация первого цикла, наконец, заканчивается и повторяется снова, пока мы не посмотрим на каждое число и не сравним, затем выберем и поменяем местами. Теперь нам просто нужно вернуть отсортированный массив с помощью return arr .
Временная сложность
Прежде чем мы напечатаем наш метод печати, а затем выполним ваш код, чтобы увидеть, что все работает, давайте объясним временную сложность этого алгоритма. Мы запускаем алгоритм, создавая цикл, который проходит через каждое число в массиве. это означает, что у нас есть O(n) потому что n – это количество шагов и количество элементов, которые у нас есть в массиве. После этого у нас есть второй цикл, внутри первого цикла, который также перебирает каждое число в массиве, так что это еще один O(n ). Итак, у нас есть O (n) что для каждого n внутри него есть еще один O (n) , что делает O(n X n) или O(n ^ 2) . Таким образом, временная сложность этого алгоритма составляет O(n ^ 2) !
Подожди секунду…
Может быть, вы сомневаетесь в себе” Но каждый раз, когда мы делаем наш второй цикл, мы делаем так, чтобы это была позиция первого цикла + 1, поэтому мы не проверяем n полностью во втором цикле, так что это будет n-1, n-2 …” и да, вы на самом деле правы! в конце второго цикла мы будем проверять только один элемент, поэтому временная сложность должна быть примерно такой O(n X 1/2 X n) . Это правильно, но в обозначении Big O мы игнорируем константы типа 1/2, так что в итоге у нас просто есть O(n X n) и вот почему все так и остается!
Ладно, это был полный рот, но мы почти в конце! теперь мы просто собираемся создать последний метод, printArray :
void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " | ");
}
}
Здесь нам не нужно ничего возвращать, мы просто создаем цикл for, который проходит через весь массив и выводит значения с разделяющим их каналом | .
Теперь мы собираемся создать java-файл для выполнения и тестирования этого алгоритма! Давайте создадим файл с именем SelectionSortMain.java
package selectionSort;
public class SelectionSortMain {
public static void main(String args[]) {
SelectionSort selection = new SelectionSort();
//create the array
int[] arr = {10, 6, 4, 8, 2};
//This is gonna print the original array
System.out.println("Unsorted array: ");
selection.printArray(arr);
//sort the array
selection.sort(arr);
//used println here just to make a space since we used print in the printArray
System.out.println();
//print sorted array
System.out.println("Sorted array: ");
selection.printArray(arr);
}
}
Здесь мы просто создаем массив, печатаем его несортированным (с помощью нашего метода printArray), а затем используем наш метод сортировки и печатаем его снова, поэтому наш результат должен быть таким:
Unsorted array: 10 | 6 | 4 | 8 | 2 | Sorted array: 2 | 4 | 6 | 8 | 10 |
И это в значительной степени все! Надеюсь, что эта статья помогла вам в чем-то. Вы можете проверить репозиторий, который я сделал в Github, со всем кодом и с другими реализациями DS & A. Я новичок в создании статей и писательстве в целом но я пытаюсь совершенствоваться! Любые вопросы или предложения очень ценятся. Удачи вам в вашем учебном путешествии!
Удачи вам в вашем учебном путешествии!
Оригинал: “https://dev.to/gmkonan/implementing-selection-sort-in-java-26c2”