Введение в сортировку выбора в Java
Выборочная сортировка в Java - это метод сортировки, который постоянно находит наименьший элемент в несортированной части и сохраняет его в начале (для сортировки в порядке возрастания). Процесс будет повторяться до сортировки входного массива. Также, в Selection Sort, мы будем делить входной массив на два подмассива, где один массив используется для отсортированных элементов, а другой массив для несортированных элементов. В начале в отсортированном подмассиве не будет никаких элементов. Давайте рассмотрим работу сортировки выбора подробно в следующем разделе.
Как сортировка выбора работает в Java
Сортировка выбора работает простым способом, где она сохраняет два подмассива из входного массива. Они есть:
- Сортированный подмассив, чтобы сохранить отсортированные элементы
- Несортированный подмассив для хранения несортированных элементов.
Алгоритм:
Ниже приведен алгоритм, который используется для сортировки выбора.
- Установите минимальный (MIN) указатель на местоположение 0.
- Найти самый маленький элемент из списка элементов в массиве
- Поменяйте местами минимальный элемент с местоположением 0
- Переместить указатель MIN в следующую позицию
- Повторяйте процесс, пока входной массив не будет отсортирован.
Давайте разберемся в выборе сортировки на примере. Ниже приводится входной массив, который должен быть отсортирован. Элементы, выделенные полужирным синим цветом, будут являться частью отсортированного массива.
Шаг 1 : Установите указатель MIN на первое место. Таким образом, указатель MIN указывает на 15.
Наименьший: = 15
Шаг 2 : Найдите самый маленький элемент, сравнив его с остальными элементами. Сравнивая 15 и 21, 15 самый маленький. Таким образом, самое маленькое не изменится в этом случае.
Наименьший: = 15
Сравнивая 15 и 6, 6 самый маленький.
Наименьший: = 6
Сравнивая 6 и 3, 3 является наименьшим.
Наименьший: = 3
3 в этом случае также будет меньше, так как 19 больше 3.
Наименьший: = 3
Наименьший: = 3
Наконец, в этой итерации 3 оказывается наименьшим.
Шаг 3 : Поменяйте местами самый маленький элемент с элементом в местоположении 0.
Шаг 4: Увеличьте указатель MIN до следующей позиции.
Шаг 5: Найдите следующий наименьший элемент, сравнив его с остальными элементами.
Наименьший: = 21
Наименьший: = 6
Наименьший: = 6
Наименьший: = 6
Наименьший: = 6
Шаг 6: Поменяйте местами самый маленький элемент с элементом в местоположении 1.
Повторяйте процесс, пока не будет сформирован отсортированный массив, как показано ниже.
Примеры реализации сортировки выбора в Java
Как уже упоминалось выше, сортировка выбора основана на поиске минимума и обмене. Теперь давайте посмотрим, как реализовать сортировку выбора с использованием Java.
Java-программа для сортировки элементов в массиве с использованием Selection Sort
import java.util.*;
public class SelSortExample (
//Method that implements Selectionsort
public static void selsort(int() arr)
(
int n=arr.length; //length of the array
for(int i=0;i (
int MIN=i; //set the first position as minimum
System.out.println("Sorting based on Number "+(i+1));
//Find the smallest element by comparing with the element in MIN position
for(int j=i+1;j (
System.out.println("Comparing "+ arr(MIN) + " and " + arr(j));
if(arr(j) (
System.out.println(arr(MIN) + " is greater than " + arr(j) );
MIN=j;
)
)
//Swap the smallest element with element in MIN position
int temp=arr(i);
arr(i)=arr(MIN);
arr(MIN)=temp;
)
)
public static void main(String() args) (
int() arr= (15, 21, 6, 3, 19, 20); // input array
System.out.println("Elements in the array before Sorting: "+ Arrays. toString (arr));
selsort (arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays. toString (arr));
)
)import java.util.*;
public class SelSortExample (
//Method that implements Selectionsort
public static void selsort(int() arr)
(
int n=arr.length; //length of the array
for(int i=0;i (
int MIN=i; //set the first position as minimum
System.out.println("Sorting based on Number "+(i+1));
//Find the smallest element by comparing with the element in MIN position
for(int j=i+1;j (
System.out.println("Comparing "+ arr(MIN) + " and " + arr(j));
if(arr(j) (
System.out.println(arr(MIN) + " is greater than " + arr(j) );
MIN=j;
)
)
//Swap the smallest element with element in MIN position
int temp=arr(i);
arr(i)=arr(MIN);
arr(MIN)=temp;
)
)
public static void main(String() args) (
int() arr= (15, 21, 6, 3, 19, 20); // input array
System.out.println("Elements in the array before Sorting: "+ Arrays. toString (arr));
selsort (arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays. toString (arr));
)
)import java.util.*;
public class SelSortExample (
//Method that implements Selectionsort
public static void selsort(int() arr)
(
int n=arr.length; //length of the array
for(int i=0;i (
int MIN=i; //set the first position as minimum
System.out.println("Sorting based on Number "+(i+1));
//Find the smallest element by comparing with the element in MIN position
for(int j=i+1;j (
System.out.println("Comparing "+ arr(MIN) + " and " + arr(j));
if(arr(j) (
System.out.println(arr(MIN) + " is greater than " + arr(j) );
MIN=j;
)
)
//Swap the smallest element with element in MIN position
int temp=arr(i);
arr(i)=arr(MIN);
arr(MIN)=temp;
)
)
public static void main(String() args) (
int() arr= (15, 21, 6, 3, 19, 20); // input array
System.out.println("Elements in the array before Sorting: "+ Arrays. toString (arr));
selsort (arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays. toString (arr));
)
)import java.util.*;
public class SelSortExample (
//Method that implements Selectionsort
public static void selsort(int() arr)
(
int n=arr.length; //length of the array
for(int i=0;i (
int MIN=i; //set the first position as minimum
System.out.println("Sorting based on Number "+(i+1));
//Find the smallest element by comparing with the element in MIN position
for(int j=i+1;j (
System.out.println("Comparing "+ arr(MIN) + " and " + arr(j));
if(arr(j) (
System.out.println(arr(MIN) + " is greater than " + arr(j) );
MIN=j;
)
)
//Swap the smallest element with element in MIN position
int temp=arr(i);
arr(i)=arr(MIN);
arr(MIN)=temp;
)
)
public static void main(String() args) (
int() arr= (15, 21, 6, 3, 19, 20); // input array
System.out.println("Elements in the array before Sorting: "+ Arrays. toString (arr));
selsort (arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays. toString (arr));
)
)
Пример вывода:
В приведенной выше программе у нас есть два метода main и метод sort sort. Метод main вызывает метод sort sort, передавая входной массив в качестве аргумента. Минимальный элемент будет идентифицирован и заменен элементом, указанным MIN.
Сортировка выбора также может использоваться, когда входной массив не определен в коде. Давайте посмотрим, как это работает, используя программу ниже.
Java-программа для сортировки элементов с использованием Selection Sort
import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = new Scanner(System.in); //To take the input from user
System.out.print("Enter the size of array : \n");
n = sc.nextInt();
int array() = new int(n); //initialising the array
System.out.print("Enter the elements that need to be inserted in the array : \n");
//inserting the elements to the array
for(i=0; i (
array(i) = sc.nextInt();
)
System.out.print("array before Sorting: \n"+ Arrays.toString(array));
System.out.print("\nSorting begins here..\n");
for(i=0; i (
for(j=i+1; j (
if(array(i) > array(j))
(
tempvar = array(i);
array(i) = array(j);
array(j) = tempvar;
)
)
)
System.out.print("Array after Sorting is :\n");
for(i=0; i (
System.out.print(array(i)+ " ");
)
)
)import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = new Scanner(System.in); //To take the input from user
System.out.print("Enter the size of array : \n");
n = sc.nextInt();
int array() = new int(n); //initialising the array
System.out.print("Enter the elements that need to be inserted in the array : \n");
//inserting the elements to the array
for(i=0; i (
array(i) = sc.nextInt();
)
System.out.print("array before Sorting: \n"+ Arrays.toString(array));
System.out.print("\nSorting begins here..\n");
for(i=0; i (
for(j=i+1; j (
if(array(i) > array(j))
(
tempvar = array(i);
array(i) = array(j);
array(j) = tempvar;
)
)
)
System.out.print("Array after Sorting is :\n");
for(i=0; i (
System.out.print(array(i)+ " ");
)
)
)import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = new Scanner(System.in); //To take the input from user
System.out.print("Enter the size of array : \n");
n = sc.nextInt();
int array() = new int(n); //initialising the array
System.out.print("Enter the elements that need to be inserted in the array : \n");
//inserting the elements to the array
for(i=0; i (
array(i) = sc.nextInt();
)
System.out.print("array before Sorting: \n"+ Arrays.toString(array));
System.out.print("\nSorting begins here..\n");
for(i=0; i (
for(j=i+1; j (
if(array(i) > array(j))
(
tempvar = array(i);
array(i) = array(j);
array(j) = tempvar;
)
)
)
System.out.print("Array after Sorting is :\n");
for(i=0; i (
System.out.print(array(i)+ " ");
)
)
)import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = new Scanner(System.in); //To take the input from user
System.out.print("Enter the size of array : \n");
n = sc.nextInt();
int array() = new int(n); //initialising the array
System.out.print("Enter the elements that need to be inserted in the array : \n");
//inserting the elements to the array
for(i=0; i (
array(i) = sc.nextInt();
)
System.out.print("array before Sorting: \n"+ Arrays.toString(array));
System.out.print("\nSorting begins here..\n");
for(i=0; i (
for(j=i+1; j (
if(array(i) > array(j))
(
tempvar = array(i);
array(i) = array(j);
array(j) = tempvar;
)
)
)
System.out.print("Array after Sorting is :\n");
for(i=0; i (
System.out.print(array(i)+ " ");
)
)
)import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = new Scanner(System.in); //To take the input from user
System.out.print("Enter the size of array : \n");
n = sc.nextInt();
int array() = new int(n); //initialising the array
System.out.print("Enter the elements that need to be inserted in the array : \n");
//inserting the elements to the array
for(i=0; i (
array(i) = sc.nextInt();
)
System.out.print("array before Sorting: \n"+ Arrays.toString(array));
System.out.print("\nSorting begins here..\n");
for(i=0; i (
for(j=i+1; j (
if(array(i) > array(j))
(
tempvar = array(i);
array(i) = array(j);
array(j) = tempvar;
)
)
)
System.out.print("Array after Sorting is :\n");
for(i=0; i (
System.out.print(array(i)+ " ");
)
)
)
Пример вывода:
Здесь введенные пользователем элементы ввода будут сравниваться с временной переменной и заменяться местами. Процесс будет повторяться до тех пор, пока не будет сформирован отсортированный массив.
Производительность выбора сортировки
Этот метод сортировки используется из-за его простоты и некоторых других преимуществ производительности по сравнению с другими, более сортировочными методами.
Вывод
Сортировка выбора не работает эффективно в больших списках, так как она требует больше времени для сравнения. Сортировка выбора - это метод, в котором входной массив будет разделен на два подмассива, чтобы сохранить отсортированные и несортированные элементы. Минимальный элемент в массиве будет заменен на элемент в первой позиции, и процесс будет продолжаться, пока не будет сформирован отсортированный массив.
Рекомендуемые статьи
Это руководство по выбору сортировки в Java. Здесь мы обсуждаем введение, работу и эффективность сортировки выбора, а также некоторые примеры. Вы также можете посмотреть следующие статьи, чтобы узнать больше -
- Сортировка слиянием в Java
- Сортировка кучи в Java
- Копировать конструктор в Java
- Звездные узоры на Яве
- Сортировка кучи в Python