La plupart du temps, lors de l'écriture de boucles, j'écris généralement de mauvaises conditions aux limites (par exemple: résultat erroné) ou mes hypothèses sur les terminaisons de boucle sont erronées (par exemple: boucle tournant à l'infini). Bien que mes hypothèses soient correctes après quelques essais et erreurs, je me suis senti trop frustré à cause du manque de modèle informatique correct dans ma tête.

/**
 * Inserts the given value in proper position in the sorted subarray i.e. 
 * array[0...rightIndex] is the sorted subarray, on inserting a new value 
 * our new sorted subarray becomes array[0...rightIndex+1].
 * @param array The whole array whose initial elements [0...rightIndex] are 
 * sorted.
 * @param rightIndex The index till which sub array is sorted.
 * @param value The value to be inserted into sorted sub array.
 */
function insert(array, rightIndex, value) {
    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];
    }   
    array[j + 1] = value; 
};

Les erreurs que j'ai commises initialement étaient:

1. Au lieu de j> = 0, je l’ai gardé j> 0.
2. Vous avez confondu si tableau [j + 1] = valeur ou tableau [j] = valeur.

Quels sont les outils / modèles mentaux pour éviter de telles erreurs?

Tester

Non, sérieusement, testez.

Je code depuis plus de 20 ans et je n’ai toujours pas confiance en moi pour écrire une boucle correctement la première fois. J'écris et exécute des tests qui prouvent que cela fonctionne avant que je suppose que cela fonctionne. Testez chaque côté de chaque condition limite. Par exemple, un rightIndex0 devrait faire quoi? Que diriez-vous de -1?

Rester simple

Si les autres ne peuvent pas voir ce que cela fait en un coup d'œil, vous le rendez trop difficile. N'hésitez pas à ignorer les performances si cela signifie que vous pouvez écrire quelque chose de facile à comprendre. Rendez-le seulement plus rapidement dans le cas peu probable où vous en auriez vraiment besoin. Et même alors seulement une fois que vous êtes absolument sûr de savoir exactement ce qui vous ralentit. Si vous pouvez obtenir une amélioration réelle de Big O , cette activité n’est peut-être pas vaine, mais même dans ce cas, rendez votre code aussi lisible que possible.

Par un

Connaissez la différence entre compter vos doigts et compter les espaces entre vos doigts. Parfois, les espaces sont ce qui est réellement important. Ne laissez pas vos doigts vous distraire. Savoir si votre pouce est un doigt. Sachez si l’écart entre votre petit doigt et votre pouce compte comme un espace.

commentaires

Avant de vous perdre dans le code, essayez de dire ce que vous voulez dire en anglais. Énoncez clairement vos attentes. N'expliquez pas comment fonctionne le code. Explique pourquoi tu le fais faire ce qu'il fait. Gardez les détails de mise en œuvre en dehors de cela. Il devrait être possible de refactoriser le code sans avoir à changer le commentaire.

Le meilleur commentaire est un bon nom.

Si vous pouvez dire tout ce que vous devez dire avec un bon nom, ne le répétez pas avec un commentaire.

Les abstractions

Les objets, les fonctions, les tableaux et les variables sont des abstractions qui ne valent que les noms qui leur sont donnés. Donnez-leur des noms qui garantissent que lorsque les gens regarderont à l'intérieur, ils ne seront pas surpris par ce qu'ils trouveront.

Noms courts

Utilisez des noms courts pour des choses de courte durée. iest un bon nom pour un index dans une belle boucle serrée dans une petite portée qui le rend évident. Si la ivie est suffisamment longue pour se disperser, ligne après ligne, avec d'autres idées et noms avec lesquels on peut confondre, iil est temps de donner iun beau nom explicatif.

Noms longs

Ne raccourcissez jamais un nom simplement pour des raisons de longueur de ligne. Trouvez un autre moyen de présenter votre code.

Espace blanc

Les défauts aiment se cacher dans un code illisible. Si votre langue vous permet de choisir votre style d'indentation, soyez au moins cohérent. Ne faites pas que votre code ressemble à un flot de bruit. Le code devrait ressembler à une marche en formation.

Constructions en boucle

Apprenez et passez en revue les structures de boucle dans votre langue. Regarder un débogueur mettre en évidence une for(;;)boucle peut être très instructif. Apprenez toutes les formes. while, do while, while(true), for each. Utilisez le plus simple possible. Regardez en amorçant la pompe . Apprenez quoi breaket continuefaites si vous en avez. Connaître la différence entre c++et ++c. N'ayez pas peur de rentrer tôt, à condition de toujours fermer tout ce qui doit être fermé. Enfin bloque ou de préférence quelque chose qui le marque pour la fermeture automatique lorsque vous l'ouvrez: Using statement / Try with Resources .

Boucles alternatives

Laissez quelque chose d'autre faire la boucle si vous le pouvez. C'est plus facile pour les yeux et déjà débogué. Ceux - ci se présentent sous plusieurs formes: collections ou cours d' eau qui permettent map(), reduce(), foreach(), et d' autres méthodes qui appliquent un lambda. Rechercher des fonctions spécialisées comme Arrays.fill(). Il y a aussi la récursivité, mais attendez-vous à ce que cela facilite les choses dans des cas particuliers. En règle générale, n'utilisez pas la récursivité jusqu'à ce que vous voyiez à quoi ressemblerait l'alternative.

Oh, et test.

Tester, tester, tester.

Ai-je mentionné le test?

Il y avait encore une chose. Je ne m'en souviens pas. Commencé avec un T ...

Lors de la programmation, il est utile de penser à:

• conditions préalables
• post-conditions
• variantes
• et invariants (de boucles ou de types )

et en explorant un territoire inexploré (comme jongler avec des indices) , il peut être très, très , utile de ne pas penser à peu près , mais les rendre réellement les explicite dans le code avec des affirmations .

Prenons votre code original:

/**
 * Inserts the given value in proper position in the sorted subarray i.e. 
 * array[0...rightIndex] is the sorted subarray, on inserting a new value 
 * our new sorted subarray becomes array[0...rightIndex+1].
 * @param array The whole array whose initial elements [0...rightIndex] are 
 * sorted.
 * @param rightIndex The index till which sub array is sorted.
 * @param value The value to be inserted into sorted sub array.
 */
function insert(array, rightIndex, value) {
    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];
    }   
    array[j + 1] = value; 
};

Et vérifiez ce que nous avons:

• condition préalable: array[0..rightIndex]est trié
• post-condition: array[0..rightIndex+1]est trié
• invariant: 0 <= j <= rightIndexmais cela semble un peu redondant; ou @Jules noté dans les commentaires, à la fin d'un « rond », for n in [j, rightIndex+1] => array[j] > value.
• invariant: à la fin d'un "round", array[0..rightIndex+1]est trié

Ainsi, vous pouvez d’abord écrire une is_sortedfonction ainsi qu’une minfonction travaillant sur une tranche de tableau, puis affirmer:

function insert(array, rightIndex, value) {
    assert(is_sorted(array[0..rightIndex]));

    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];

        assert(min(array[j..rightIndex+1]) > value);
        assert(is_sorted(array[0..rightIndex+1]));
    }   
    array[j + 1] = value; 

    assert(is_sorted(array[0..rightIndex+1]));
};

Il y a aussi le fait que votre condition de boucle est un peu compliquée; vous voudrez peut-être vous simplifier la tâche en séparant les choses:

function insert(array, rightIndex, value) {
    assert(is_sorted(array[0..rightIndex]));

    for (var j = rightIndex; j >= 0; j--) {
        if (array[j] <= value) { break; }

        array[j + 1] = array[j];

        assert(min(array[j..rightIndex+1]) > value);
        assert(is_sorted(array[0..rightIndex+1]));
    }   
    array[j + 1] = value; 

    assert(is_sorted(array[0..rightIndex+1]));
};

Maintenant, la boucle est simple ( jva de rightIndexà 0).

Enfin, cela doit maintenant être testé:

• penser aux conditions aux limites ( rightIndex == 0, rightIndex == array.size - 2)
• penser à valueêtre plus petit array[0]ou plus grand quearray[rightIndex]
• penser à valueêtre égal à array[0], array[rightIndex]ou un indice moyen

Ne sous-estimez pas non plus le fuzzing . Vous avez des assertions en place pour détecter les erreurs, alors générez un tableau aléatoire et triez-le en utilisant votre méthode. Si une assertion est déclenchée, vous trouvez un bogue et pouvez étendre votre suite de tests.

Utiliser les tests unitaires / TDD

Si vous avez vraiment besoin d'accéder à des séquences via une forboucle, vous pouvez éviter les erreurs grâce aux tests unitaires , et plus particulièrement au développement piloté par les tests .

Imaginez que vous deviez implémenter une méthode prenant les valeurs supérieures à zéro, dans l'ordre inverse. À quels cas de test pouvez-vous penser?

1. Une séquence contient une valeur supérieure à zéro.

   Actual: [5]. Attendu: [5].

   La mise en œuvre la plus simple qui satisfait aux exigences consiste à simplement renvoyer la séquence source à l'appelant.

2. Une séquence contient deux valeurs, toutes deux supérieures à zéro.

   Actual: [5, 7]. Attendu: [7, 5].

   Maintenant, vous ne pouvez pas simplement renvoyer la séquence, mais vous devez l'inverser. Souhaitez-vous utiliser une for (;;)boucle, une autre construction de langage ou une méthode de bibliothèque n'a pas d'importance.

3. Une séquence contient trois valeurs, l'une étant zéro.

   Actual: [5, 0, 7]. Attendu: [7, 5].

   Maintenant, vous devriez changer le code pour filtrer les valeurs. Là encore, cela pourrait être exprimé par un ifénoncé ou un appel à votre méthode de cadre préférée.

4. En fonction de votre algorithme (puisqu'il s'agit de tests en boîte blanche, l'implémentation est importante), vous devrez peut-être gérer spécifiquement le [] → []cas de séquence vide , ou peut-être pas. Ou vous pouvez faire en sorte que le cas limite où toutes les valeurs sont négatives [-4, 0, -5, 0] → []est traitée correctement, ou même que les valeurs négatives aux limites sont: [6, 4, -1] → [4, 6]; [-1, 6, 4] → [4, 6]. Dans de nombreux cas, toutefois, vous ne subirez que les trois tests décrits ci-dessus: aucun test supplémentaire ne vous fera changer de code et ne serait donc pas pertinent.

Travailler à un niveau d'abstraction supérieur

Cependant, dans de nombreux cas, vous pouvez éviter la plupart de ces erreurs en travaillant à un niveau d'abstraction plus élevé, en utilisant des bibliothèques / frameworks existants. Ces bibliothèques / frameworks permettent de restaurer, trier, scinder et joindre les séquences, d’insérer ou de supprimer des valeurs dans des tableaux ou des listes à double liaison, etc.

Habituellement, foreachpeut être utilisé à la place de for, ce qui rend la vérification des conditions aux limites non pertinente: la langue le fait pour vous. Certaines langues, telles que Python, n'ont même pas la for (;;)construction, mais seulement for ... in ....

En C #, LINQ est particulièrement pratique lorsque vous travaillez avec des séquences.

var result = source.Skip(5).TakeWhile(c => c > 0);

est beaucoup plus lisible et moins sujet aux erreurs par rapport à sa forvariante:

for (int i = 5; i < source.Length; i++)
{
    var value = source[i];
    if (value <= 0)
    {
        break;
    }

    yield return value;
}

Je suis d'accord avec d'autres personnes qui disent tester votre code. Cependant, il est également bon de bien faire les choses en premier lieu. J'ai souvent tendance à me tromper sur les conditions aux limites et j'ai donc développé des astuces mentales pour prévenir de tels problèmes.

Avec un tableau indexé 0, vos conditions normales vont être:

for (int i = 0; i < length; i++)

ou

for (int i = length - 1; i >= 0; i--)

Ces modèles devraient devenir une seconde nature, vous ne devriez pas avoir à y penser du tout.

Mais tout ne suit pas exactement ce modèle. Donc, si vous n'êtes pas sûr d'avoir bien écrit, voici votre prochaine étape:

Branchez les valeurs et évaluez le code dans votre propre cerveau. Faites en sorte que la réflexion soit aussi simple que possible. Que se passe-t-il si les valeurs pertinentes sont des 0? Que se passe-t-il s'ils sont 1?

for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
    array[j + 1] = array[j];
}   
array[j + 1] = value;

Dans votre exemple, vous ne savez pas si cela devrait être [j] = valeur ou [j + 1] = valeur. Il est temps de commencer à l’évaluer manuellement:

Qu'advient-il si vous avez une longueur de tableau 0? La réponse devient évidente: rightIndex doit être (longueur - 1) == -1, donc j commence à -1, donc pour insérer à l’indice 0, vous devez ajouter 1.

Nous avons donc prouvé que la condition finale était correcte, mais pas à l’intérieur de la boucle.

Qu'advient-il si vous avez un tableau avec 1 élément, 10, et nous essayons d'insérer un 5? Avec un seul élément, rightIndex devrait commencer à 0. Donc, la première fois dans la boucle, j = 0, donc "0> = 0 && 10> 5". Puisque nous voulons insérer le 5 à l'index 0, le 10 doit être déplacé vers l'index 1, donc tableau [1] = tableau [0]. Comme cela se produit lorsque j est égal à 0, array [j + 1] = array [j + 0].

Si vous essayez d'imaginer un large réseau et ce qui se passe lors de l'insertion dans un emplacement arbitraire, votre cerveau sera probablement submergé. Mais si vous vous en tenez à des exemples simples de taille 0/1/2, il devrait être facile de faire un survol mental rapide et de voir où vos conditions aux limites se dégradent.

Imaginez que vous n’ayez jamais entendu parler du problème des poteaux de clôture et je vous dis que j’ai 100 poteaux de clôture en ligne droite, combien de segments les sépare. Si vous essayez d’imaginer 100 poteaux de clôture dans votre tête, vous allez être submergé. Alors, quel est le plus petit nombre de poteaux de clôture pour faire une clôture valide? Vous avez besoin de 2 pour faire une clôture, alors imaginez 2 poteaux, et l’image mentale d’un segment unique entre les poteaux le rend très clair. Vous n'êtes pas obligé de rester là à compter les posts et les segments car vous avez transformé le problème en quelque chose de intuitivement évident pour votre cerveau.

Une fois que vous pensez que c'est correct, il est bon de le tester et de vous assurer que l'ordinateur fait ce que vous pensez, mais ce devrait être une simple formalité.

Je suis trop frustré à cause du manque de modèle informatique correct dans ma tête.

Est un point très intéressant à cette question et il a généré ce commentaire: -

Il n'y a qu'un moyen: mieux comprendre votre problème. Mais c'est aussi général que votre question est. - Thomas Junk

... et Thomas a raison. Ne pas avoir l'intention claire d'une fonction devrait être un drapeau rouge - une indication claire que vous devez immédiatement ARRÊTER, saisir un crayon et du papier, vous éloigner de l'EDI et décomposer le problème correctement; ou du moins votre santé mentale - vérifiez ce que vous avez fait.

J'ai vu tellement de fonctions et de classes devenir un désordre complet parce que les auteurs ont tenté de définir l'implémentation avant d'avoir complètement défini le problème. Et c'est si facile à gérer.

Si vous ne comprenez pas bien le problème, il est également peu probable que vous codiez la solution optimale (en termes d'efficacité ou de clarté) et que vous ne pourrez pas créer de tests unitaires réellement utiles dans une méthodologie TDD.

Prenez votre code ici à titre d'exemple, il contient un certain nombre de défauts potentiels que vous n'avez pas encore pris en compte, par exemple: -

• Et si rightIndex est trop bas? (indice: il va entraîner la perte de données)
• Et si rightIndex est en dehors des limites du tableau? (obtiendrez-vous une exception, ou venez-vous de créer vous-même un buffer overflow?)

Il existe quelques autres problèmes liés aux performances et à la conception du code ...

• Ce code devra-t-il être mis à l'échelle? Garder le tableau trié est-il la meilleure option, ou devriez-vous regarder d'autres options (comme une liste chaînée?)
• pouvez-vous être sûr de vos hypothèses? (pouvez-vous garantir que le tableau sera trié, et si ce n'était pas le cas?)
• réinventez-vous la roue? Les tableaux triés sont un problème bien connu, avez-vous étudié les solutions existantes? Existe-t-il une solution disponible dans votre langue (comme SortedList<t>en C #)?
• Devriez-vous copier manuellement une entrée de tableau à la fois? ou votre langage fournit-il des fonctions communes comme celles de JScript Array.Insert(...)? ce code serait-il plus clair?

Ce code peut être amélioré de nombreuses façons, mais tant que vous n'avez pas correctement défini ce que vous avez besoin de faire, vous ne développez pas de code, vous le corrigez simplement dans l'espoir que cela fonctionnera. Investissez le temps dedans et votre vie deviendra plus facile.

Les erreurs off-by-one sont l’une des erreurs de programmation les plus courantes. Même les développeurs expérimentés se trompent parfois. Les langages de niveau supérieur ont généralement des constructions d'itération similaires foreachou mapévitant toute indexation explicite. Mais parfois, vous avez besoin d'une indexation explicite, comme dans votre exemple.

Le défi est de savoir comment penser les plages de cellules d'un tableau. Sans modèle mental clair, il devient difficile de savoir quand inclure ou exclure les points finaux.

Lors de la description des plages d'un tableau, la convention est d' inclure la limite inférieure, exclure la limite supérieure . Par exemple, la plage 0..3 correspond aux cellules 0,1,2. Ces conventions sont utilisées dans des langues 0 indexées, par exemple la slice(start, end)méthode JavaScript renvoie le sous - tableau commençant par l' index startjusqu'à l' exclusion des index end.

Il est plus clair de penser que les index de plage décrivent les limites entre les cellules d’un tableau. L'illustration ci-dessous est un tableau de longueur 9, et les nombres situés sous les cellules sont alignés sur les bords et correspondent à la description des segments de tableau. Par exemple, il ressort clairement de l'illustration que la plage 2..5 correspond aux cellules 2,3,4.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │   -- cell indexes, e.g array[3]
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
0   1   2   3   4   5   6   7   8   9   -- segment bounds, e.g. slice(2,5) 
        └───────────┘ 
          range 2..5

Ce modèle est cohérent avec le fait que la longueur du tableau soit la limite supérieure d’un tableau. Un tableau de longueur 5 a les cellules 0..5, ce qui signifie qu'il y a les cinq cellules 0,1,2,3,4. Cela signifie également que la longueur d'un segment est la limite supérieure moins la limite inférieure, c'est-à-dire que le segment 2..5 a 5-2 = 3 cellules.

Avoir ce modèle à l'esprit lors d'une itération vers le haut ou vers le bas rend beaucoup plus clair le moment d'inclure ou d'exclure les points finaux. Lorsque vous effectuez une itération vers le haut, vous devez inclure le point de départ mais exclure le point de fin. Lorsque vous effectuez une itération vers le bas, vous devez exclure le point de départ (la limite supérieure) mais inclure le point final (la limite inférieure).

Puisque vous parcourez votre code itérativement, vous devez inclure la limite basse, 0, pour pouvoir itérer tout le temps j >= 0.

Compte tenu de cela, votre choix d'avoir l' rightIndexargument représentant le dernier index dans le sous-tableau rompt la convention. Cela signifie que vous devez inclure les deux points de terminaison (0 et rightIndex) dans l'itération. Cela rend également difficile la représentation du segment vide (dont vous avez besoin lorsque vous démarrez le tri). En réalité, vous devez utiliser -1 comme rightIndex lors de l'insertion de la première valeur. Cela semble assez peu naturel. Il semble plus naturel d’ rightIndexindiquer l’indice après le segment, donc 0 représente le segment vide.

Bien entendu, votre code est particulièrement déroutant, car il étend le sous-tableau trié avec un, en remplaçant l'élément immédiatement après le sous-tableau trié initialement. Donc, vous lisez à partir de l'indice j mais vous écrivez la valeur à j + 1. Ici, vous devez juste préciser que j est la position dans le sous-tableau initial, avant l’insertion. Lorsque les opérations sur les index deviennent trop difficiles, cela m'aide à les représenter sur un morceau de papier quadrillé.

L'introduction de votre question me fait penser que vous n'avez pas appris à coder correctement. Toute personne qui programme dans un langage impératif pendant plus de quelques semaines devrait vraiment avoir sa boucle de départ correctement dès la première fois dans plus de 90% des cas. Peut-être vous précipitez-vous pour commencer à coder avant d'avoir suffisamment réfléchi au problème.

Je vous suggère de corriger cette lacune en (ré) apprenant à écrire des boucles - et je recommanderais quelques heures de travail sur une gamme de boucles avec du papier et un crayon. Prenez un après-midi pour le faire. Ensuite, passez environ 45 minutes par jour à travailler sur le sujet jusqu'à ce que vous le compreniez vraiment.

C'est très bien de tester, mais vous devriez le faire dans l'espoir que vos limites de boucle (et le reste de votre code) soient correctes.

Peut-être que je devrais mettre un peu de chair dans mon commentaire:

Il n'y a qu'un moyen: mieux comprendre votre problème. Mais c'est aussi général que votre question est

Votre point est

Bien que mes hypothèses soient correctes après quelques essais et erreurs, je me suis senti trop frustré à cause du manque de modèle informatique correct dans ma tête.

Quand je lis trial and error, mon réveil sonne. Bien sûr, beaucoup d’entre nous connaissent l’état d’esprit, quand on veut régler un petit problème et qu’il a cerné la tête à d’autres choses et commence à deviner d’une façon ou d’une autre, pour que le code soit conforme seemà ce qu’il est censé faire. Certaines solutions rigolotes en découlent - et certaines d’entre elles sont de pur génie . mais pour être honnête: la plupart ne le sont pas . Moi compris, connaissant cet état.

Indépendamment de votre problème concret, vous avez posé des questions sur la manière d'améliorer:

1) test

Cela a été dit par d'autres et je n'aurais rien de précieux à ajouter

2) Analyse du problème

Il est difficile de donner un conseil à cela. Je ne pourrais vous donner que deux astuces qui vous aideront probablement à améliorer vos compétences dans ce domaine:

• le plus évident et le plus trivial est, à long terme, le plus efficace: résoudre de nombreux problèmes. Tout en pratiquant et en répétant, vous développez l’état d’esprit qui vous aide pour les tâches futures. La programmation est comme toute autre activité à améliorer par la pratique du travail acharné

Les Katas de code sont un moyen, ce qui pourrait aider un peu.

Comment pouvez-vous devenir un grand musicien? Il est utile de connaître la théorie et de comprendre les mécanismes de votre instrument. Cela aide d'avoir du talent. Mais finalement, la grandeur vient de la pratique; appliquer la théorie encore et encore, en utilisant les commentaires pour s'améliorer à chaque fois.

Code Kata

Un site que j'aime beaucoup: Code Wars

Atteindre la maîtrise grâce aux défis Améliorez vos compétences en vous entraînant avec d'autres sur de vrais défis de code

Ce sont des problèmes relativement petits qui vous aident à améliorer vos compétences en programmation. Et ce que j'aime le plus dans Code Wars , c'est que vous pouvez comparer votre solution à une autre .

Ou peut-être devriez-vous jeter un coup d’œil sur Exercism.io où vous obtenez les commentaires de la communauté.

• L’autre conseil est presque aussi trivial: Apprenez à résoudre les problèmes Vous devez vous entraîner, décomposant les problèmes en problèmes vraiment mineurs. Si vous dites que vous avez des problèmes pour écrire des boucles , vous faites l'erreur de considérer la boucle dans son ensemble et de ne pas la déconstruire en morceaux. Si vous apprenez à démonter les choses étape par étape , vous apprendrez à éviter de telles erreurs.

Je sais - comme je l'ai dit plus haut que vous êtes parfois dans un tel état - qu'il est difficile de décomposer des "choses simples" en tâches plus "simples"; mais ça aide beaucoup.

Je me souviens que lorsque j’ai appris la programmation de façon professionnelle , j’avais de gros problèmes pour déboguer mon code. Quel était le problème? Hybris - L'erreur ne peut pas être dans telle ou telle région du code, car je sais qu'elle ne peut pas l'être. Et en conséquence? J'ai parcouru le code au lieu de l’analyser, mais j’ai dû apprendre, même si c’était fastidieux de décomposer mon code en instructions .

3) Développer une ceinture à outils

En plus de connaître votre langue et vos outils - je sais que ce sont les choses brillantes que les développeurs pensent en premier - apprendre les algorithmes (ou lecture).

Voici deux livres pour commencer:

• Introduction dans les algortihms

• Algorithmes

C'est comme apprendre quelques recettes pour commencer à cuisiner. Au début, vous ne savez pas quoi faire, vous devez donc regarder ce que les chefs précédents ont cuisiné pour vous. La même chose vaut pour les algortihms. Les algorithmes ressemblent à des recettes de cuisine pour des repas courants (structures de données, tri, hachage, etc.). Si vous les connaissez (essayez au moins de le faire) par cœur, vous avez un bon point de départ.

3a) Connaître les constructions de programmation

Ce point est un dérivé - pour ainsi dire. Connaissez votre langue - et mieux: connaissez les constructions possibles dans votre langue.

Un point commun pour le code mauvais ou inefficent est parfois, que le programmeur ne connaît pas la différence entre les différents types de boucles ( for-, while-et do-loops). Ils sont tous interchangeables. mais dans certaines circonstances, choisir une autre construction en boucle conduit à un code plus élégant.

Et il y a l'appareil de Duff ...

PS:

sinon votre commentaire ne vaut rien que Donal Trump.

Oui, nous devrions rendre le codage génial!

Une nouvelle devise pour Stackoverflow.

Si j'ai bien compris le problème, votre question est de savoir comment obtenir des boucles dès le premier essai, et non pas pour s'assurer que votre boucle est correcte (pour laquelle la réponse serait testée comme expliqué dans d'autres réponses).

Ce que je considère comme une bonne approche est d’écrire la première itération sans boucle. Une fois que vous avez fait cela, vous devriez remarquer ce qui devrait être changé entre les itérations.

Est-ce un nombre, comme un 0 ou un 1? Dans ce cas, vous avez probablement besoin d’un bingo, mais vous avez également votre point de départ i. Pensez alors combien de fois vous voulez exécuter la même chose, et vous aurez également votre condition finale.

Si vous ne savez pas EXACTEMENT le nombre de fois qu'il s'exécutera, vous n'avez pas besoin d'un, mais d'un temps ou d'un temps.

Techniquement, toute boucle peut être convertie en une autre boucle, mais le code est plus facile à lire si vous utilisez la bonne boucle. Voici donc quelques astuces:

1. Si vous vous trouvez en train d'écrire un if () {...; break;} dans un for, vous avez besoin de temps et vous avez déjà la condition

2. "While" est peut-être la boucle la plus utilisée dans toutes les langues, mais cela ne devrait pas être imo. Si vous vous trouvez en train d’écrire bool ok = True; while (check) {faire quelque chose et, espérons-le, changer à un moment donné}; alors vous n'avez pas besoin d'un certain temps, mais d'un peu, car cela signifie que vous avez tout ce dont vous avez besoin pour exécuter la première itération.

Maintenant un peu de contexte ... Quand j'ai appris à programmer (Pascal), je ne parlais pas anglais. Pour moi, "pour" et "tant que" n'avait pas beaucoup de sens, mais le mot clé "répéter" (faire en C) est presque identique dans ma langue maternelle, je l'utilisais donc pour tout. À mon avis, répéter (faire pendant) est la boucle la plus naturelle, car vous voulez presque toujours que quelque chose soit fait, puis vous voulez que ce soit refait, et encore, jusqu'à ce qu'un objectif soit atteint. "Pour" est juste un raccourci qui vous donne un itérateur et place étrangement la condition au début du code, même si, presque toujours, vous voulez que quelque chose soit fait jusqu'à ce que quelque chose se produise. En outre, while n'est qu'un raccourci pour if () {do while while ()}. Les raccourcis sont bien pour plus tard,

Je vais donner un exemple plus détaillé de la façon d'utiliser les conditions préalables / postérieures et les invariants pour développer une boucle correcte. Ensemble, ces affirmations sont appelées spécification ou contrat.

Je ne suggère pas que vous essayez de faire cela pour chaque boucle. Mais j'espère que vous trouverez utile de voir le processus de réflexion impliqué.

Pour ce faire, je vais traduire votre méthode dans un outil appelé Microsoft Dafny , conçu pour prouver l'exactitude de telles spécifications. Il vérifie également la terminaison de chaque boucle. Veuillez noter que Dafny n'a pas de forboucle, j'ai donc dû utiliser une whileboucle à la place.

Enfin, je montrerai comment vous pouvez utiliser ces spécifications pour concevoir une version légèrement plus simple de votre boucle. Cette version de boucle plus simple ne comporte pas la condition de boucle j > 0et l’affectation array[j] = value- comme ce fut votre intuition initiale.

Dafny prouvera pour nous que ces deux boucles sont correctes et font la même chose.

Je ferai ensuite une déclaration générale, basée sur mon expérience, sur la façon d’écrire une boucle en arrière correcte, qui vous aidera peut-être si vous faites face à cette situation à l’avenir.

Première partie - Rédaction d'une spécification pour la méthode

Le premier défi auquel nous sommes confrontés consiste à déterminer ce que la méthode est réellement censée faire. À cette fin, j'ai conçu des conditions pré et post spécifiant le comportement de la méthode. Pour rendre la spécification plus précise, j'ai amélioré la méthode afin qu'elle renvoie l'index où elle a valueété insérée.

method insert(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  // the method will modify the array
  modifies arr
  // the array will not be null
  requires arr != null
  // the right index is within the bounds of the array
  // but not the last item
  requires 0 <= rightIndex < arr.Length - 1
  // value will be inserted into the array at index
  ensures arr[index] == value 
  // index is within the bounds of the array
  ensures 0 <= index <= rightIndex + 1
  // the array to the left of index is not modified
  ensures arr[..index] == old(arr[..index])
  // the array to the right of index, up to right index is
  // shifted to the right by one place
  ensures arr[index+1..rightIndex+2] == old(arr[index..rightIndex+1])
  // the array to the right of rightIndex+1 is not modified
  ensures arr[rightIndex+2..] == old(arr[rightIndex+2..])

Cette spécification capture complètement le comportement de la méthode. Mon observation principale à propos de cette spécification est que cela serait simplifié si la procédure était passée à la valeur rightIndex+1plutôt qu'à rightIndex. Mais comme je ne vois pas d'où cette méthode est appelée, je ne sais pas quel effet ce changement aurait sur le reste du programme.

Deuxième partie - Déterminer un invariant de boucle

Maintenant que nous avons une spécification pour le comportement de la méthode, nous devons ajouter une spécification du comportement de la boucle qui convaincra Dafny que l’exécution de la boucle se terminera et aboutira à l’état final souhaité array.

Ce qui suit est votre boucle originale, traduite en syntaxe Dafny avec des invariants de boucle ajoutés. Je l'ai également changé pour retourner l'index où la valeur a été insérée.

{
    // take a copy of the initial array, so we can refer to it later
    // ghost variables do not affect program execution, they are just
    // for specification
    ghost var initialArr := arr[..];


    var j := rightIndex;
    while(j >= 0 && arr[j] > value)
       // the loop always decreases j, so it will terminate
       decreases j
       // j remains within the loop index off-by-one
       invariant -1 <= j < arr.Length
       // the right side of the array is not modified
       invariant arr[rightIndex+2..] == initialArr[rightIndex+2..]
       // the part of the array looked at by the loop so far is
       // shifted by one place to the right
       invariant arr[j+2..rightIndex+2] == initialArr[j+1..rightIndex+1]
       // the part of the array not looked at yet is not modified
       invariant arr[..j+1] == initialArr[..j+1] 
    {
        arr[j + 1] := arr[j];
        j := j-1;
    }   
    arr[j + 1] := value;
    return j+1; // return the position of the insert
}

Cela se vérifie chez Dafny. Vous pouvez le voir vous-même en suivant ce lien . Donc, votre boucle implémente correctement la spécification de méthode que j'ai écrite dans la première partie. Vous devrez décider si cette spécification de méthode correspond réellement au comportement souhaité.

Notez que Dafny produit ici une preuve d'exactitude. C'est une garantie d'exactitude bien plus forte que celle que l'on peut éventuellement obtenir en testant.

Troisième partie - une boucle plus simple

Maintenant que nous avons une spécification de méthode qui capture le comportement de la boucle. Nous pouvons modifier en toute sécurité l'implémentation de la boucle tout en gardant la certitude que nous n'avons pas changé le comportement de la boucle.

J'ai modifié la boucle afin qu'elle corresponde à vos intuitions d'origine concernant la condition de la boucle et la valeur finale de j. Je dirais que cette boucle est plus simple que celle que vous avez décrite dans votre question. Il est plus souvent capable d'utiliser jque de j+1.

1. Commencez j à rightIndex+1

2. Changez la condition de boucle en j > 0 && arr[j-1] > value

3. Changer le devoir en arr[j] := value

4. Décrémentez le compteur de boucle à la fin de la boucle plutôt qu'au début

Voici le code. Notez que les invariants de boucle sont aussi un peu plus faciles à écrire maintenant:

method insert2(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  modifies arr
  requires arr != null
  requires 0 <= rightIndex < arr.Length - 1
  ensures 0 <= index <= rightIndex + 1
  ensures arr[..index] == old(arr[..index])
  ensures arr[index] == value 
  ensures arr[index+1..rightIndex+2] == old(arr[index..rightIndex+1])
  ensures arr[rightIndex+2..] == old(arr[rightIndex+2..])
{
    ghost var initialArr := arr[..];
    var j := rightIndex+1;
    while(j > 0 && arr[j-1] > value)
       decreases j
       invariant 0 <= j <= arr.Length
       invariant arr[rightIndex+2..] == initialArr[rightIndex+2..]
       invariant arr[j+1..rightIndex+2] == initialArr[j..rightIndex+1]
       invariant arr[..j] == initialArr[..j] 
    {
        j := j-1;
        arr[j + 1] := arr[j];
    }   
    arr[j] := value;
    return j;
}

Quatrième partie - conseils sur le bouclage arrière

Après avoir écrit et prouvé correctement de nombreuses boucles sur plusieurs années, j’ai le conseil général suivant sur les boucles arrière.

Il est presque toujours plus facile de penser et d'écrire une boucle arrière (décrémentation) si la décrémentation est effectuée au début de la boucle plutôt qu'à la fin.

Malheureusement, la forconstruction de la boucle dans de nombreuses langues rend cela difficile.

Je soupçonne (mais ne peux pas prouver) que cette complexité est à l'origine de la différence d'intuition quant à ce que devrait être la boucle et ce qu'elle devait être en réalité. Vous êtes habitué à penser aux boucles en avant (incrémentation). Lorsque vous voulez écrire une boucle arrière (décrémentation), essayez de créer la boucle en essayant d'inverser l'ordre dans lequel les choses se passent dans une boucle avant (incrémentante). Mais en raison de la façon dont la forconstruction fonctionne, vous avez omis d'inverser l'ordre de l'affectation et de mettre à jour la variable de boucle - ce qui est nécessaire pour une véritable inversion de l'ordre des opérations entre une boucle en amont et en aval.

Cinquième partie - bonus

Juste pour compléter, voici le code que vous obtenez si vous passez rightIndex+1à la méthode plutôt que rightIndex. Cette modification élimine tous les +2décalages qui sont par ailleurs nécessaires pour penser à la correction de la boucle.

method insert3(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  modifies arr
  requires arr != null
  requires 1 <= rightIndex < arr.Length 
  ensures 0 <= index <= rightIndex
  ensures arr[..index] == old(arr[..index])
  ensures arr[index] == value 
  ensures arr[index+1..rightIndex+1] == old(arr[index..rightIndex])
  ensures arr[rightIndex+1..] == old(arr[rightIndex+1..])
{
    ghost var initialArr := arr[..];
    var j := rightIndex;
    while(j > 0 && arr[j-1] > value)
       decreases j
       invariant 0 <= j <= arr.Length
       invariant arr[rightIndex+1..] == initialArr[rightIndex+1..]
       invariant arr[j+1..rightIndex+1] == initialArr[j..rightIndex]
       invariant arr[..j] == initialArr[..j] 
    {
        j := j-1;
        arr[j + 1] := arr[j];
    }   
    arr[j] := value;
    return j;
}

Obtenir cela facilement et couramment est une question d'expérience. Bien que le langage ne vous permette pas de l'exprimer directement ou que vous utilisiez un cas plus complexe que ne le permet le système intégré simple, vous pensez qu'il s'agit d'un niveau supérieur tel que "visitez chaque élément une fois par ordre" et le codeur plus expérimenté traduit cela instantanément dans les détails appropriés, car il l'a déjà fait tant de fois.

Même dans ce cas, dans des cas plus complexes, il est facile de se tromper, car ce que vous écrivez n’est généralement pas ce qu’il faut de mieux . Avec des langages et des bibliothèques plus modernes, vous n'écrivez pas une chose facile, car il existe une construction prédéfinie. En C ++, le mantra moderne est "utiliser des algorithmes plutôt que d'écrire du code".

Donc, la meilleure façon de s’assurer que c’est bien, pour ce genre de chose en particulier, est d’examiner les conditions aux limites . Parcourez le code dans votre tête pour les quelques cas où les choses changent. Si le index == array-max, que se passe-t-il? Qu'en est- il max-1? Si le code tourne mal, ce sera à l'une de ces limites. Certaines boucles doivent s’inquiéter du premier ou du dernier élément, ainsi que de la construction en boucle qui établit les limites correctement; Par exemple, si vous vous référez a[I]et a[I-1]que se passe-t-il quand Iest la valeur minimale?

Aussi, regardez les cas où le nombre d'itérations (correctes) est extrême: si les limites se rencontrent et que vous aurez 0 itérations, cela fonctionnera-t-il sans cas particulier? Et qu’en est-il de la première itération, où la limite inférieure est également la limite supérieure en même temps?

L'examen des cas marginaux (des deux côtés de chaque bord) est ce que vous devez faire lorsque vous écrivez la boucle et ce que vous devez faire lors de la révision du code.

J'essaierai déjà de rester à l'écart des sujets mentionnés à gogo.

Quels sont les outils / modèles mentaux pour éviter de telles erreurs?

Outils

Pour moi, le plus grand outil pour mieux écrire foret whileboucles est de ne pas écrire une forou des whileboucles du tout.

La plupart des langues modernes tentent de résoudre ce problème d’une manière ou d’une autre. Par exemple, Java, tout en ayant Iteratordès le début, ce qui était un peu maladroit à utiliser, a introduit une syntaxe raccourcie pour les utiliser plus facilement dans une version plus récente. C # les a aussi, etc.

Ma langue actuelle, Ruby, a adopté l’approche fonctionnelle ( .each, .mapetc.) à part entière. C'est très puissant. Je viens de faire un comptage rapide dans une base de code Ruby sur laquelle je travaille: dans environ 10 000 lignes de code, il y a zéro foret environ 5 while.

Si j'étais obligé de choisir une nouvelle langue, la recherche de boucles fonctionnelles / basées sur les données comme celle-ci serait très élevée dans la liste des priorités.

Modèles mentaux

Gardez à l'esprit que whilec'est le minimum d'abstraction que vous puissiez obtenir, juste un peu plus haut goto. À mon avis, la situation forest encore pire au lieu d’être meilleure car elle associe étroitement les trois parties de la boucle.

Donc, si je suis dans un environnement où forest utilisé, alors je m'assure que les 3 parties sont parfaitement simples et toujours les mêmes. Cela signifie que je vais écrire

limit = ...;
for (idx = 0; idx < limit; idx++) { 

Mais rien de plus complexe. J'aurai peut-être un compte à rebours de temps en temps, mais je ferai de mon mieux pour l'éviter.

Si whileje l' utilise , je reste à l'écart des manigances internes compliquées impliquant la condition de boucle. Le test à l'intérieur while(...)sera aussi simple que possible et j'éviterai breakde mon mieux. De plus, la boucle sera courte (lignes de code de comptage) et toutes les plus grandes quantités de code seront factorisées.

Surtout si la condition réelle tant que complexe est complexe, je vais utiliser une "variable de condition" qui est très facile à repérer, et ne place pas la condition dans la whiledéclaration elle-même:

repeat = true;
while (repeat) {
   repeat = false; 
   ...
   if (complex stuff...) {
      repeat = true;
      ... other complex stuff ...
   }
}

(Ou quelque chose comme ça, dans la bonne mesure, bien sûr.)

Cela vous donne un modèle mental très facile qui est "cette variable est exécutée de 0 à 10 monotone" ou "cette boucle est exécutée jusqu'à ce que cette variable soit false / true". La plupart des cerveaux semblent être capables de gérer parfaitement ce niveau d'abstraction.

J'espère que ça t'as aidé.

Les boucles inversées, en particulier, peuvent être difficiles à raisonner car bon nombre de nos langages de programmation sont orientés vers l'itération en aval, à la fois dans la syntaxe commune pour les boucles et par l'utilisation d'intervalles de demi-ouverture à base zéro. Je ne dis pas qu'il est faux que les langues fassent ces choix; Je dis simplement que ces choix compliquent la réflexion sur les boucles inverses.

En général, rappelez-vous qu'une boucle for est simplement un sucre syntaxique construit autour d'une boucle while:

// pseudo-code!
for (init; cond; step) { body; }

est équivalent à:

// pseudo-code!
init;
while (cond) {
  body;
  step;
}

(éventuellement avec une couche supplémentaire d'étendue pour conserver les variables déclarées dans l'étape d'init locale à la boucle).

Cela convient à de nombreux types de boucles, mais il est malaisé d’avoir le pas en dernier. Lorsque je travaille en arrière, je trouve qu'il est plus facile de démarrer l'index de boucle avec la valeur après celle que je veux et de déplacer la steppartie en haut de la boucle, comme ceci:

auto i = v.size();  // init
while (i > 0) {  // simpler condition because i is one after
    --i;  // step before the body
    body;  // in body, i means what you'd expect
}

ou, en tant que boucle for:

for (i = v.size(); i > 0; ) {
    --i;  // step
    body;
}

Cela peut sembler déroutant, car l'expression de l'étape est dans le corps plutôt que dans l'en-tête. C'est un effet secondaire regrettable de la syntaxe de boucle for for inhérente au biais direct. Pour cette raison, certains diront que vous faites plutôt ceci:

for (i = v.size() - 1; i >= 0; --i) {
    body;
}

Mais c'est un désastre si votre variable d'index est un type non signé (comme cela pourrait être en C ou C ++).

Gardant cela à l’esprit, écrivons votre fonction d’insertion.

1. Puisque nous allons travailler en arrière, nous allons laisser l’index de boucle être l’entrée après le slot de tableau "courant". Je concevrais la fonction pour prendre la taille de l’entier plutôt que l’index du dernier élément car les plages semi-ouvertes sont le moyen naturel de représenter des plages dans la plupart des langages de programmation et parce qu’elles nous permettent de représenter un tableau vide sans avoir recours à à une valeur magique comme -1.

   function insert(array, size, value) {
     var j = size;
   

2. Bien que la nouvelle valeur soit plus petite que l’ élément précédent , continuez à vous déplacer. Bien sûr, l'élément précédent peut être vérifié que s'il est un élément précédent, donc nous devons d' abord vérifier que nous ne sommes pas au début:

     while (j != 0 && value < array[j - 1]) {
       --j;  // now j become current
       array[j + 1] = array[j];
     }
   

3. Cela laisse jlà où nous voulons la nouvelle valeur.

     array[j] = value; 
   };
   

Programmation Pearls de Jon Bentley donne une explication très claire du type d'insertion (et d'autres algorithmes), ce qui peut vous aider à construire vos modèles mentaux pour ce type de problèmes.

Êtes-vous simplement confus sur ce que forfait réellement une boucle et sur les mécanismes de son fonctionnement?

for(initialization; condition; increment*)
{
    body
}

1. Tout d'abord, l'initialisation est exécutée
2. Ensuite, la condition est vérifiée
3. Si la condition est vraie, le corps est exécuté une fois. Si non passez à # 6
4. Le code d'incrément est exécuté
5. Goto # 2
6. Fin de boucle

Il pourrait être utile pour vous de réécrire ce code en utilisant une construction différente. Voici la même chose en utilisant une boucle while:

initialization
while(condition)
{
    body
    increment
}

Voici quelques autres suggestions:

• Pouvez-vous utiliser une autre construction de langage comme une boucle foreach? Cela prend en charge la condition et l'étape d'incrément pour vous.
• Pouvez-vous utiliser une fonction Carte ou Filtre? Certaines langues ont des fonctions avec ces noms qui parcourent en interne une collection pour vous. Vous venez de fournir la collection et le corps.
• Vous devriez vraiment passer plus de temps à vous familiariser avec les forboucles. Vous les utiliserez tout le temps. Je vous suggère de parcourir une boucle for dans un débogueur pour voir comment il s'exécute.

* Notez que bien que j'utilise le terme "incrément", c'est juste du code qui se trouve après le corps et avant la vérification de la condition. Ce peut être un décrément ou rien du tout.

Tentative de compréhension supplémentaire

Pour les algorithmes non triviaux avec des boucles, vous pouvez essayer la méthode suivante:

1. Créez un tableau fixe avec 4 positions et mettez quelques valeurs dans, pour simuler le problème;
2. Ecrivez votre algorithme pour résoudre le problème donné , sans boucle et avec indexation codée en dur ;
3. Après cela, substituez des indexations codées en dur dans votre code avec une variable iou j, et incrémentez / décrémentez ces variables si nécessaire (mais toujours sans aucune boucle);
4. Réécrivez votre code et placez les blocs répétitifs dans une boucle , en remplissant les conditions de pré et post;
5. [ facultatif ] réécrivez votre boucle afin qu'elle se présente sous la forme de votre choix (pour / while / do while);
6. Le plus important est d'écrire votre algorithme correctement. après cela, vous refactorisez et optimisez votre code / boucles si nécessaire (mais cela pourrait rendre le code non trivial pour un lecteur)

Ton problème

//TODO: Insert the given value in proper position in the sorted subarray
function insert(array, rightIndex, value) { ... };

Écrire le corps de la boucle manuellement plusieurs fois

Utilisons un tableau fixe à 4 positions et essayons d'écrire l'algorithme manuellement, sans boucle:

           //0 1 2 3
var array = [2,5,9,1]; //array sorted from index 0 to 2
var leftIndex = 0;
var rightIndex = 2;
var value = array[3]; //placing the last value within the array in the proper position

//starting here as 2 == rightIndex

if (array[2] > value) {
    array[3] = array[2];
} else {
    array[3] = value;
    return; //found proper position, no need to proceed;
}

if (array[1] > value) {
    array[2] = array[1];
} else {
    array[2] = value;
    return; //found proper position, no need to proceed;
}

if (array[0] > value) {
    array[1] = array[0];
} else {
    array[1] = value;
    return; //found proper position, no need to proceed;
}

array[0] = value; //achieved beginning of the array

//stopping here because there 0 == leftIndex

Réécrire, en supprimant les valeurs codées en dur

//consider going from 2 to 0, going from "rightIndex" to "leftIndex"

var i = rightIndex //starting here as 2 == rightIndex

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

//stopping here because there 0 == leftIndex

Traduire en boucle

Avec while:

var i = rightIndex; //starting in rightIndex

while (true) {
    if (array[i] > value) { //refactor: this can go in the while clause
        array[i+1] = array[i];
    } else {
        array[i+1] = value;
        break; //found proper position, no need to proceed;
    }

    i--;
    if (i < leftIndex) { //refactor: this can go (inverted) in the while clause
        array[i+1] = value; //achieved beginning of the array
        break;
    }
}

Refactorisez / réécrivez / optimisez la boucle comme vous le souhaitez:

Avec while:

var i = rightIndex; //starting in rightIndex

while ((array[i] > value) && (i >= leftIndex)) {
    array[i+1] = array[i];
    i--;
}

array[i+1] = value; //found proper position, or achieved beginning of the array

avec for:

for (var i = rightIndex; (array[i] > value) && (i >= leftIndex); i--) {
    array[i+1] = array[i];
}

array[i+1] = value; //found proper position, or achieved beginning of the array

PS: le code suppose que l’entrée est valide et que ce tableau ne contient pas de répétitions;

C'est pourquoi j'éviterais d'écrire des boucles qui fonctionnent sur des indices bruts, en faveur d'opérations plus abstraites, dans la mesure du possible.

Dans ce cas, je ferais quelque chose comme ceci (en pseudo-code):

array = array[:(rightIndex - 1)] + value + array[rightIndex:]

Dans votre exemple, le corps de la boucle est assez évident. Et il est évident que certains éléments doivent être modifiés à la fin. Donc, vous écrivez le code, mais sans le début de la boucle, la condition de fin et l'affectation finale.

Ensuite, vous vous écartez du code et découvrez quel est le premier mouvement à effectuer. Vous changez le début de la boucle pour que le premier coup soit correct. Vous vous éloignez à nouveau du code et découvrez quel est le dernier mouvement à exécuter. Vous modifiez la condition de fin pour que le dernier mouvement soit correct. Et finalement, vous vous écartez de votre code, déterminez ce que doit être la dernière tâche et corrigez le code en conséquence.