Sortare recursivă de selecție Java (Programare, Java, Recursivitate, Pseudocod, Sortare De Selecție)

iCV a intrebat.
a intrebat.

Am căutat o sortare de selecție recursivă, folosind doar 2 parametri:

  • Matricea care trebuie sortată
  • o valoare k, care indică până la ce element trebuie sortat.

Exemplu: SelectionSort(array[] a, int k) cu a fiind {6,3,5,7,2} și k fiind 2 va sorta primele 3 elemente și va păstra neatinse ultimele elemente.

Mă gândeam să încep cu o declarație if pentru k fiind 0, iar dacă acesta ar fi cazul, ar returna matricea așa cum este, deoarece nu se poate sorta o matrice de mărimea 1. Ceva de genul:

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)
}

Nu am nici o idee despre cum să fac partea „else”, deoarece știu doar că trebuie să apeleze din nou metoda.Nu am voie să creez alte metode. De asemenea, trebuie să mă asigur că folosesc exact 2 parametri, nici mai mult, nici mai puțin.

Trebuie să lucrez în pseudocod, dar înțeleg ceva din Java, așa că dacă cineva m-ar putea ajuta folosind fie pseudo, fie Java, mi-ar fi de mare ajutor

Comentarii

  • Bună ziua și bine ați venit, deși ar fi o provocare interesantă, nu este filozofia site-ului să ofere cod scris de la zero. Probabil că ar trebui să începi cu el, să faci tot ce poți și să revii când te blochezi cu ceva. –  > Por Yassin Hajaj.
2 răspunsuri
Thomas Fritsch

Mai întâi câteva observații la codul tău:

  • Metodele dvs. sort și selectionSort nu trebuie să returneze un int[] array, deoarece obiectul array a rămâne același tot timpul.Doar conținutul din acest array se schimbă.Prin urmare, puteți folosi void ca tip de returnare.
  • În aplicația dvs. if utilizați (k == 0) în loc de (k = 0)

Ați rezolvat deja prima parte.Iată cum puteți face a doua parte în pseudocod:

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]
        }
    }
}

Sunt sigur că sunteți în măsură să rafinați pseudocodul în cod Java real.

Vallas

EDIT: OP a clarificat întrebarea, acest lucru ar putea să nu fie relevant pentru OP, dar ar putea fi pentru viitorii vizitatori.

Vă rugăm să țineți cont de comentariul la întrebarea dvs. pentru data viitoare. Doar de data asta, te ajut pentru că ești nou. Făcând o simplă căutare pe Google, am găsit cea mai mare parte a codului de mai jos pe acest site. Am adăugat selectionSort eu însumi pentru a se potrivi cu parametrii dvs. Rețineți că Stack Overflow nu este un serviciu de scriere de cod (chiar dacă oamenii dau cod destul de des, aceasta nu este o cerință într-un răspuns).

    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;
    }