Insertion binaire Trier de la même manière que l'insertion normale Tri

Question

J'essaie donc de comprendre comment utiliser correctement le tri par insertion binaire sans avoir besoin d'une méthode d'échange ou quoi que ce soit de ce genre. Un de mes amis m'a donné une interprétation approximative du code nécessaire, mais je n'arrive pas à le faire comme je le veux.

private static int binaryInsertionSort(int[] b) 
{ 
    int left, right, middle, i, m; 
    int compareCount = 0; 
    for (int j = 1; j < b.length; j++) 
    { 
     left = b[j - 1]; 
     right = b[j + 1]; 
     if (b[j] < b[left]) 
     { 
      i = left; 
     } 
     else 
     { 
      i = left + 1; 
     } 
     m = b[j]; 
     for(int k = 0; k < (j - i - 1); k++) 
     { 
      b[j - k] = b[j - k - 1]; 
      compareCount++; 
     } 
     b[i] = m; 
    } 
    return compareCount; 
} 

L'int compareCount est simplement juste pour voir combien de comparaisons sont effectuées au cours de la méthode. Maintenant, ce que j'essaie de faire est d'organiser un tableau d'entiers de manière régulière, spécifiquement comme b [0] = 1, b [1] = 2, ...... b [63] = 64. Dans mon principal méthode je crée le tableau et assigner des valeurs à l'inverse: b [0] = 64, b [1] = 63, etc. Comment puis-je obtenir ce code pour les réorganiser dans le mode normal que je cherche? J'ai été capable de le faire très simplement avec un tri normal, mais c'est un peu plus compliqué à mes yeux.

Answer 1

Nevermind. Après beaucoup de bricolage et de détails spécifiques avec un autre ami, nous avons réussi à trouver exactement comment faire cela.

public static int binaryInsertionSort(int[] b) 
{ 
    int lo, mid, hi, temp; 
    int compareCount = 0; 
    for (int i = 1; i < b.length; i++) 
    { 
     lo = 0; 
     hi = i; 
     mid = i/2; 
     do 
     { 
      if (b[i] > b[mid]) 
      { 
       lo = mid + 1; 
       compareCount++; 
      } 
      else if (b[i] < b[mid]) 
      { 
       hi = mid; 
       compareCount++; 
      } 
      else 
      { 
       compareCount++; 
       break; 
      } 
      mid = lo + ((hi - lo)/2); 
     } while (lo < hi); 
     if (mid < i) 
     { 
      temp = b[i]; 
      for (int j = i - 1; j >= mid; j--) 
      { 
       b[j + 1] = b[j]; 
       compareCount++; 
      } 
      b[mid] = temp; 
     } 
    } 
    return compareCount; 
} 

Très difficile, mais avec effort vient récompenses. Peu importe que personne n'ait répondu, je remercie quand même ceux qui ont vu ma question.