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

Как упоминалось ранее, вы не обновляете переменную 'min' во внутреннем цикле.Цель внутреннего цикла - найти индекс наименьшего элемента.Вы также должны переместить «своп» во внешний цикл.Ниже приведен псевдокод выбора сортировки:

Selection Sort
Inputs:
  A: an array
  n: the number of elements in A to sort

Procedure SELECTION-SORT (A, n)
1. For i = 0 to n – 1:
  A. Set minIndex to i.
  B. For j = i + 1 to n:
    i. If A[j] < A[minIndex], then set minIndex to j. // Add this
  C. Swap A[i] with A[minIndex]. // Move this to outside of the inner loop

Посмотрите на ссылку на мой блог ниже, чтобы увидеть полное объяснение алгоритма сортировки выбора.Существуют реализации на Java, C ++, Python и JavaScript.

http://brianredd.com/algorithm/selection-sort

Answer 2

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

import java.util.Arrays;

public class SelectionSort {

  public static void main(String[] args) {
    int[] input = new int[] {5,2,4,6,1,3};
    System.out.println( Arrays.toString(selectionSort(input)) );
  }

  public static int[] selectionSort(int[] input) {
    int length = input.length;
    int minimumValue = Integer.MAX_VALUE;

    for (int i = 0; i < length; ++i) {
        // find the minimumValue when j > i and swap it  with input[i] location
        for (int j =i; j < length; ++j) {
          if (input[j] <= minimumValue ) {
            minimumValue = input[j];
            input[j] = input[i];
            input[i] = minimumValue;
          }
        }
        minimumValue = Integer.MAX_VALUE;
    }
    return input;
  }

}

Я добавил в GitHub .

Answer 3

/* Implementation of selection sort */

import java.util.Arrays;
import java.util.Scanner;


public class SelectionSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        System.out.println("Enter the number of elements of the array");
        int n = in.nextInt();
        int []a = new int[n];
        System.out.println("Enter the integer array of elements");
        for (int i=0; i<n ; i++)
        {
            a[i] = in.nextInt();
        }
        System.out.println("Before Sorting: "+Arrays.toString(a));
        a = sort(a);
        System.out.println("After Sorting: "+Arrays.toString(a));
    }

    private static int[] sort(int[] a) {
        // TODO Auto-generated method stub

        for(int i=0; i<a.length-1;i++)
        {
            int index=i;
            for(int j=i+1; j<a.length;j++)

                if(a[j]<a[index])
                {
                    index=j;
                }
                int small = a[index];
                a[index] = a[i];
                a[i]=small;

        }
        return a;
    }
}

Answer 4

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

Пример:

3,1,2

Предположим, 3 (позиция 1) наименьшая. Сравните с позицией 2, 1 <3, поэтому предположим, что позиция 2. имеет наименьшее значение. Сравните с позицией 3, 3 <1. Так как мы находимся в конце, переключатель наименьший с первой позицией. (позиции 1 и 2)</p>

1,3,2

Теперь, поскольку позиция 1 выполнена, начните с позиции 2. Предположим, что 3 (позиция 2) является наименьшим значением. Сравните с позицией 3 (2). 2 <3, поэтому предположим, что позиция 3 имеетНаименьшее значение. Поскольку мы находимся в конце массива, мы переключаем позиции 2 и 3 </p>

1,2,3

Готово

Answer 5

Просто передайте массив и размер массива

private void selectionSort() {
    for (int i = 0; i < arraySize; i++) {
        for (int j = i; j < arraySize; j++) {
            if (array[i] > array[j])
                swapValues(i,j);
        }
    }
}
private void swapValues(int posOne, int posTwo) {
    int tValue = array[posOne];
    array[posOne] = array[posTwo];
    array[posTwo] = tValue;
}

Answer 6

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

private static void selectionSort (int [] arr) {

        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }

Answer 7

public class SelectionSort {

public static void main(String[] args) {
    int[] A = {5,4,3,2,1};
    int l = A.length;

    for (int i = 0; i < l-1; ++i ){
        int minPos = i;

        // Find the location of the minimal element
        for (int j = i + 1; j < l; ++j){
            if ( A[j] < A[minPos]){
                minPos = j;
            }
        }

        if (minPos != i){
            int temp = A[i];
            A[i] = A[minPos];   
            A[minPos] = temp;
        }
    }
    System.out.println(Arrays.toString(A));
}
}