Java - Алгоритм сортировки выбора

Question

У меня есть несколько вопросов по поводу сортировки выбора. Я немного запутался.

 int [] arr = {5,4,3,2,1}; // This is my array
    int min = 0;

    for(int i = 0;i<arr.length;i++)
    {
        //Assume first element is min
        min = i;//Selection sort algorithm says that find the minimum in the
                // array, but first element is not minimum.What's point here?
        for(int j = i + 1;j<arr.length;j++)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            System.out.println(arr[i]);//I print the in ascending order 
        }
    }

Вывод:

4
3
2
1
4
3
2
4
3
4

Что не так?

Answer 1

Сортировка выбора

- это поиск минимального значения на каждом шаге цикла.Вы не нашли минимальное значение (возможно, с помощью оператора if), просто обменяли значение во внутреннем цикле.так что вы на самом деле не делали сортировку.

исправление на основе вашей реализации:

final int[] arr = { 5, 4, 3, 2, 1 }; // This is my array
    int min;
    for (int i = 0; i < arr.length; i++) {
        // Assume first element is min
        min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;

            }
        }
        if (min != i) {
            final int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        System.out.println(arr[i]);// I print the in ascending order
    }

это должно дать вам вывод:

1
2
3
4
5

Answer 2

Правильно:

public class Test {

public static void main(String args[]){
    int[] arr = {5,4,3,2,1}; // This is my array
    int min = 0;

    for(int i = 0;i<arr.length;i++)
    {
        //Assume first element is min
        min = i;
        for(int j = i + 1;j<arr.length;j++)
        {
            if(arr[j] < arr[min]) { min = j;}
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
        System.out.println(arr[i]);//I print the in ascending order 
    }
}

}

О минимальной части: это просто относится к индексу текущего минимума.Вы двигаетесь вниз по массиву до тех пор, пока не достигнете нового минимума, и установите min для этого индекса.Таким образом, 5 - это минимальное число [min = 0], пока вы не увидите 4 [так что теперь min = 1], но затем вы сравните 3 с тем, что хранится в 4 [когда min = 1], а затем поймете, что вы должны установить min = 2.... и т. д.

Answer 3

Ваш вопрос в вашем комментарии

min = i;//Selection sort algorithm says that find the minimum in the
        // array, but first element is not minimum.What's point here?

Суть в том, что вы можете предположить, что первый, который вы проверяете, является самым низким, поэтому у вас есть место для начала. В конце концов, это может быть не минимальный показатель для всех, но из тех, что вы проверяли в этой итерации, он пока самый низкий!

Answer 4

Сначала вы должны найти минимум, а не предполагать, что первый элемент является минимумом

int[] array = {5, 4, 3, 2, 1};
for ( int i = 0; i < array.length; i++ ) {

  //find minimum, starting from index i
  int minIndex = i;
  int min = array[i];
  for ( int j = i + 1; j < array.length; j++ ) {
    if ( array[ j ] < min ) {
      minIndex = j;
      min = array[j];
    }
  }

  // now move the smallest element to the front, and the element at index i to the index of the minimal element
  int temp = array[ i ];
  array[ i ] = min;
  array[ minIndex ] = temp;
}

Answer 5

Алгоритм сортировки выбора сортирует массив путем многократного поиска минимального элемента (с учетом возрастающего порядка) из несортированной части и размещения его в начале. Алгоритм поддерживает два подмассива в данном массиве.

1) Подмассив, который уже отсортирован. 2) Оставшийся подмассив, который не отсортирован.

На каждой итерации сортировки выбора минимальный элемент (с учетом возрастающего порядка) из несортированного подмассива выбирается и перемещается в отсортированный подмассив.

Пример:

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64 

Java-код:

void sort(int arr[]) 
    { 
        int n = arr.length; 

        // One by one move boundary of unsorted subarray 
        for (int i = 0; i < n-1; i++) 
        { 
            // Find the minimum element in unsorted array 
            int min_idx = i; 
            for (int j = i+1; j < n; j++) 
                if (arr[j] < arr[min_idx]) 
                    min_idx = j; 

            // Swap the found minimum element with the first 
            // element 
            int temp = arr[min_idx]; 
            arr[min_idx] = arr[i]; 
            arr[i] = temp; 
        } 
    } 

И помните, что массивы передаются по ссылке!

Answer 6

передать несортированный массив получить отсортированный массив

 public int[] selectionSort(int[] list) {
            int i, j, minValue, minIndex, temp = 0;
            for (i = 1; i < list.length; i++) {
                minValue = list[i];
                minIndex = i;
                j = i - 1;
                for (j = i; j < list.length; j++) {

                    if (list[j] < minValue) {
                        minValue = list[j];
                        minIndex = j;
                    }

                }
                if (list[i] > minValue) {
                    temp = list[i];
                    list[i] = list[minIndex];
                    list[minIndex] = temp;
                }

            }
            return list;
        }

Answer 7

Сортировка выбора - это алгоритм, который формирует элементы массива в порядке ANSI или DENSI.Сложность времени в лучшем, среднем и худшем случаях равна (n ² ).Сортировка выбора не лучше для сортировки массива ... Реализация сортировки выбора приведена ниже:

import java.util.Scanner;

class selection{
      public static void main(String a[]){

             Scanner sc=new Scanner(System.in);
             System.out.print("size :");
             int n=sc.nextInt();

             int i,j,tmp,minVal;

             int[] ar=new int[n];

             for(i=0;i<n;i++){
                  ar[i]=sc.nextInt();
             }

             for(i=0;i<(n-1);i++){
                  minVal=ar[i];
                  for(j=(i+1);j<n;j++){
                          if(minVal>ar[j]){
                                  minVal=ar[j];
                                  tmp=ar[i];
                                  ar[i]=minVal;
                                  ar[j]=tmp;
                          }
                  }

            }

            for(i=0;i<n;i++){
                  System.out.print(ar[i]+"  ");
            }
  }

Answer 8

открытый класс Selectionsort {

открытый статический int arr [];public static int y;

public static void main (String args []) {

System.out.println ("Введите номер элемента, который вы хотите ввести для сортировки");

int nofele= Integer.parseInt(args[0]);

System.out.println("Enter number of element entered for sorting is "+ "\n" +nofele);

arr = new int[nofele];

System.out.println("Entered array is");

for(int i=1,j=0;i<=nofele;i++,j++){

arr[j]=Integer.parseInt(args[i]);

  System.out.println(arr[j]);

}

System.out.println("Sorted array for selection sort is ");

for(int k=0;k<nofele-1;k++)  {





  for(int l=nofele-k,b=1;l>=2;l--,b++){

    if(arr[k]>arr[k+b]){



     int temp=arr[k];

      arr[k]=arr[k+b];

      arr[k+b] = temp;


    }     

  }

   System.out.println(arr[k]);

}

   System.out.println(arr[nofele-1]);

}

}

Answer 9

    int[] arr = {5,4,3,2,1};

    for (int i = 0; i < arr.length - 1; i++)
         {
            int index = i;
              for (int j = i + 1; j < arr.length; j++)
                  if (arr[j] < arr[index]) 
                   index = j;

            int smallerNumber = arr[index];  
            arr[index] = arr[i];
            arr[i] = smallerNumber;
      }

Это правильный метод сортировки выбора. То, что вы делали неправильно, вы меняете местами во внутреннем цикле, но на самом деле обмен должен быть выполнен после первого полного цикла внутреннего цикла, где минимальный элемент равенопределяется.

Answer 10

Предположим, самый низкий элемент, который требует сканирования всех элементов, а затем поменять его на первую позицию.

private static void selectionSortMethod(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {  //no of iterations for array length
            for (int j = i + 1; j < arr.length; j++) {  //starting from next index to lowest element(assuming 1st index as lowest)
                if (arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }

        }
         //print 
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }