Tri récursif avec uniquement un tableau comme entrée

Question

J'ai écrit quelques programmes récursifs courts et je fais maintenant un tri récursif. J'ai utilisé jusqu'à présent 2 entrées, le tableau et un index. Existe-t-il une méthode récursive pour le tri qui n'a besoin que d'un tableau en entrée? Je pensais que Bubble Sort fonctionnerait pour cela, mais cela utilise également un index pour garder une trace de la position.

Et au cas où quelqu'un veut savoir, j'avais un HW pour faire un tri récursif (ce que j'ai déjà fait, en utilisant un tableau et un index), c'est juste pour voir s'il est possible de le faire sans index.

Answer 1

je crois une sorte de fusion récursive peut être réalisée avec seulement un tableau en tant que paramètre: http://en.wikipedia.org/wiki/Merge_sort

Edit: Je suppose que vous pouvez sauter l'index comme ceci:

function bubble_sort(arr) 
{ 
    for (i=0 to arr.length-1) 
    { 
     if(arr[i] > arr[i+1]) 
     { 
      swap(arr, i); 
      return bubble_sort(arr); 
     } 
    } 
    return arr; 
} 

Ce n'est pas un tri parfait des bulles car l'indice de départ est toujours nul. La complexité est toujours O (n^2). Si vous êtes prêt à cloner le tableau (et perdre beaucoup de mémoire), vous pouvez remplacer

return bubble_sort(arr); 

Avec:

return combineArrays(arr.subArray(0, i), bubble_sort(arr.subArray(i, n))); 

Ensuite, il est valide, mais le gaspillage, la manière de parvenir à une récursif tri à bulles avec uniquement un tableau en tant que paramètre.