Рекурсивная сортировка выбора Java

Я искал рекурсивную сортировку выбора, используя только 2 параметра:

  • Массив, который нужно отсортировать
  • значение k, которое указывает, до какого элемента он должен быть отсортирован.

Пример: SelectionSort(array[] a, int k) со значением {6,3,5,7,2} и k, равным 2, отсортирует первые 3 элемента и оставит нетронутыми последние элементы.

Я думал о том, чтобы начать с оператора if для k, равного 0, и если бы это было так, он просто вернул бы массив как есть, поскольку вы не можете отсортировать массив размером 1. Что-то вроде:

public int[] sort(int[] a){
    a = selectionSort(a, n-1);
    return a;
}

public int[] selectionSort(int[] a, int k){
    if (k = 0){
        return a;
    }
    else{
        selectionSort(a, k-1 );
               ... (part i really don't know)
}

Я понятия не имею, как сделать часть «else», так как я знаю только, что он должен снова вызвать метод. Мне не разрешено создавать другие методы. Мне также нужно убедиться, что я использую ровно 2 параметра, ни больше, ни меньше.

Я должен работать с псевдокодом, но я немного понимаю Java, поэтому, если бы кто-то мог помочь мне, используя либо псевдокод, либо Java, это было бы очень полезно.


java recursion selection-sort pseudocode
person iCV    schedule 27.05.2018    source источник
comment
Привет и добро пожаловать, хотя это было бы интересной задачей, философия сайта не заключается в том, чтобы предоставлять код, написанный с нуля. Вы, вероятно, должны начать с этого, сделать все возможное и вернуться, когда вы застряли с чем-то.   -  person Yassin Hajaj    schedule 27.05.2018

Ответы (2)


arrow_upward
2
arrow_downward

Сначала несколько замечаний к вашему коду:

  • Ваши методы sort и selectionSort не должны возвращать массив int[], поскольку объект массива a все время остается одним и тем же. Меняется только содержимое этого массива. Следовательно, вы можете использовать void в качестве возвращаемого типа.
  • В вашем if используйте (k == 0) вместо (k = 0)

Вы уже разобрались с первой частью. Вот как вы можете сделать вторую часть в псевдокоде:

public void selectionSort(int[] a, int k) {
    if (k == 0) {
        return;
    }
    else {
        selectionSort(a, k-1 );
        find x such that a[x] is the smallest of a[k] ... a[a.length - 1]
        if (a[k-1] > a[x]) {
            swap a[k-1] and a[x]
        }
    }
}

Я уверен, что вы сможете преобразовать псевдокод в настоящий код Java.

person Thomas Fritsch    schedule 27.05.2018

arrow_upward
1
arrow_downward

РЕДАКТИРОВАТЬ: ОП разъяснил вопрос, это может быть неактуально для ОП, но может быть для будущих посетителей.

Пожалуйста, имейте в виду комментарий к вашему вопросу в следующий раз. Только на этот раз я помогу тебе, потому что ты новичок. Выполнив простой поиск в Google, я нашел большую часть приведенного ниже кода на этом сайте. Я сам добавил метод selectionSort под ваши параметры. Обратите внимание, что Stack Overflow не является службой написания кода (хотя люди довольно часто дают код, это не является обязательным требованием в ответе).

    public void selectionSort(int a[], int n) 
    {
      recurSelectionSort(a, n, 0);
    }

    // Recursive selection sort. n is size of a[] and index
    // is index of starting element.
    static void recurSelectionSort(int a[], int n, int index)
    {

        // Return when starting and size are same
        if (index == n)
           return;

        // calling minimum index function for minimum index
        int k = minIndex(a, index, n-1);

        // Swapping when index nd minimum index are not same
        if (k != index){
           // swap
           int temp = a[k];
           a[k] = a[index];
           a[index] = temp;
        }
        // Recursively calling selection sort function
        recurSelectionSort(a, n, index + 1);
    }

    // Return minimum index
    static int minIndex(int a[], int i, int j)
    {
        if (i == j)
            return i;

        // Find minimum of remaining elements
        int k = minIndex(a, i + 1, j);

        // Return minimum of current and remaining.
        return (a[i] < a[k])? i : k;
    }
person Vallas    schedule 27.05.2018