Javascript Girl
  1. Javascript Girl
  3. Javascript double algorithme de tri
Intereting Posts
Javascript ne s'exécutera pas après la charge Insérer automatiquement la date et l'heure dans le champ de saisie de formulaire? JQuery, setTimeout ne fonctionne pas Comment puis-je obtenir, manipuler et remplacer un nœud de texte en utilisant jQuery? AngularJS – Rendre les balises HTML contenues dans une chaîne Comment obtenir la valeur d'un div à l'aide de javascript Ajoutant du texte html à la glissade d'image jquery surdimensionnée Problème de comportement javascript inattendu Comment mettre en ligne un texte svg dans javascript? Javascript domready? Traitant des dates sur l'axe d3.js Google crawl – display: none & display: block Pourquoi l'événement de chargement de jQuery ne fonctionnera-t-il pas sur des éléments de script insérés dynamiquement? Les caractères suédois vérifient-ils avec javascript? La fonction de rappel Javascript passe sur Android

Javascript double algorithme de tri

J'ai récemment passé une entrevue où ils m'ont demandé de proposer un algorithme de tri qui m'a vraiment réussi. Est-ce que quelqu'un connaît la solution à cela si cela devait être fait en javascript?

Problème 1: Tri double

Écrivez une méthode qui accepte un ensemble de chaînes. Chaque élément peut être un nombre ( "165" ) ou un mot ( "dog" ). Votre méthode devrait trier et imprimer le tableau de sorte que (1) Les mots sont imprimés par ordre alphabétique et les nombres dans l'ordre numérique, et (2) l'ordre des mots et des nombres dans le tableau est le même.

Exemples (entrée => sortie): 

 sort(['5', '4', 'dog', '1', 'cat']) => ['1', '4', 'cat', '5', 'dog'] sort(['dog', 'cat']) => ['cat', 'dog'] sort('5', '3') => ['3', '5']

Vous pouvez utiliser les fonctions de tri des bibliothèques standard et supposer que toutes les entrées seront valides. Si vous faites d'autres hypothèses, documentez-les également. Vous pouvez utiliser n'importe quel langage de programmation que vous souhaitez.

En outre, vous pouvez supposer que vous recevrez une méthode d'utilité qui renvoie si une chaîne donnée est un nombre valide (par exemple, isNumber() , où isNumber('dog') renvoie false et isNumber('15') renvoie true ) .

Voici une approche simple: filtrer le tableau d'entrée dans des tableaux distincts de seulement des chaînes et des nombres seulement. Ensuite, trier les tableaux homogènes par leur ordre naturel. Ensuite, produisez un groupe trié fin peuplé par le type d'indices dans le tableau d'origine.

Par exemple: 

 function doubleSort(arr) { // Separate the values by type. var numbers=[], strings=[]; arr.forEach(function(x) { if (isNumber(x)) { numbers.push(Number(x)); } else { strings.push(x); } }); // Sort strings and numbers separately. strings.sort(); numbers.sort(function(a, b) { return a - b; }); // Merge the sorted arrays by type from the input array. var sorted=[], nextNumber=0, nextString=0; arr.forEach(function(x) { if (isNumber(x)) { sorted.push(String(numbers[nextNumber++])); } else { sorted.push(strings[nextString++]); } }); return sorted; } // XXX: lots of pitfalls but good enough for this exercise. function isNumber(x) { return Number(x).toString() === x; }

La performance Big-O est liée par l'algorithme de tri sous-jacent, donc probablement O(n log n) .

Même idée et performance que l'autre réponse. Mais écrit dans quelque chose comme coffeescript, il est donc plus facile de lire

Entrez la description de l'image ici

Voici une variation maladroite sur le quicksort qui va trier les nombres ou les mots in situ. (J'ai modifié un quick quicksort régulier posté par Paul Lewis , je ne sais pas si tous les kinks sont complètement éliminés …). 

 function isNumber(x,y) { return y ? Number(x).toString() !== x : Number(x).toString() === x; } function less(a,b,y){ return y ? a < b : Number(a) < Number(b) } function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; } function partition(array, pivot, left, right, what) { var store = left, pivotValue = array[pivot]; swap(array, pivot, right); for (var v = left; v < right; v++) { if (less(array[v],pivotValue,what) && isNumber(array[v],what)) { swap(array, v, store); store++; } } while(!isNumber(array[store],what)) store++; swap(array, right, store); return store; } function doubleQSort(array, left, right, what) { while(!isNumber(array[right],what) && right > left) right--; while(!isNumber(array[left],what) && left < right) left++; var pivot = null; if (left < right) { pivot = (right + left) >> 1; while(!isNumber(array[pivot],what)) pivot--; newPivot = partition(array, pivot, left, right, what); doubleQSort(array, left, newPivot - 1,what); doubleQSort(array, newPivot + 1, right,what); } }

Sortie: 

 var things = ['dog', 'asdf','31','11','6','fat','cat', '4']; doubleQSort(things,0,things.length - 1,'words'); doubleQSort(things,0,things.length - 1); console.log(things); [ "asdf", "cat", "4", "6", "11", "dog", "fat", "31" ]