const shellSort = async(tab) => { 
  let nbOpe = 0;
  let n = tab.length; 
  for (let gap = Math.floor(n/2); gap > 0; gap = Math.floor(gap/2)) { 
    for (let i = gap; i < n; i += 1) { 
      let temp = tab[i];
      let j;
      for (j = i; j >= gap && tab[j - gap] > temp; j -= gap) 
        tab[j] = tab[j - gap]; 
        nbOpe++;
    tab[j] = temp; 
    nbOpe++;                     
    }  
  }   
} 
          

function swap(tab, index1, index2){
  let tmp = tab[index1];
  tab[index1] = tab[index2];
  tab[index2] = tmp;
}
          
const selectionSort = async (tab) => {
  let nbOpe = 0;
  for (let i = 0; i tab[j]){
        minIndex = j;
      }
    }
    swap(tab,i,minIndex);
    nbOpe++;
  }
  return nbOpe;
}
          

const insertionSort = async(tab) =>{
  let nbOpe = 0;
  let lock;
  let j;
  for(let i=1; i= 0 && tab[j] > lock){
          tab[j+1] = tab[j];
          nbOpe++;
          j-=1;
      }
      tab[j+1] = lock;
      nbOpe++;
    }
  }
}
          

const partition = async(tab, debut, fin) => {
  let pivot = tab[debut];
  let swapIndex = debut;
  for (let i = debut + 1; i <= fin; i++) {
      // On parcours le sous tableau
      if (pivot > tab[i]) {
          swapIndex++;
          if (i !== swapIndex) {
              swap(tab,i,swapIndex);
          }
      }
  }
  if (swapIndex !== debut) {
      // On met le pivot au bon endroit
      swap(tab,swapIndex,debut);
  }
  return swapIndex;
}

const quickSort = async(tab, debut = 0, fin = tab.length - 1) => {
  if (debut >= fin){
      return;
  } 
  let pivotIndex = partition(tab, debut, fin);
  // Gauche
  quickSort(tab, debut, pivotIndex - 1);
  // Droite
  quickSort(tab, pivotIndex + 1, fin);
  return tab;
}
        

const bubbleSort = async (tab) => {
  for(let i = 0; i < tab.length; i++) {
      for(let j = 0; j < (tab.length-i-1); j++) {
         if(tab[j] > tab[j+1]) {
              swap(tab,j,j+1);
          }
      }
  }
}
  

  function countSort(tab) => {
    let max = 0;
    for(let i = 0; i < tab.length; i++){
        // On cherche le max du tableau
        if (tab[i] > max){
            max = tab[i];
        }
    }
    let countTab = new Array(max+1);
    let res = tab.slice(); // On copie le tableau de base
    countTab.fill(0);
    for(let i = 0; i < tab.length; i++){
        // On met dans countTab le nombre de fois que le numéro de l'index est dans le tab de base
        countTab[tab[i]] ++;
    }
    for(let i = 1; i < countTab.length; i++){
        // On fait la somme cumulative des elem de countTab
        countTab[i] = countTab[i] + countTab[i-1];
    }
    for(let i = tab.length-1; i >= 0; i--){
        res[countTab[tab[i]]-1] = tab[i];
        countTab[tab[i]]--;
    }
}

function getPosition(num, place){
  return  Math.floor(Math.abs(num)/Math.pow(10,place))% 10
}

const radixSort = async (tab) => {
    let max = 0;

    for(let i = 0; i < tab.length; i++){
        if(tab[i] > max){
            max = tab[i];
        }
    }

    for (let i = 0; i < max; i++) {
        let buckets = Array.from({ length: 10 }, () => [ ])
        for (let j = 0; j < tab.length; j++) {
          buckets[getPosition(tab[ j ], i)].push(tab[ j ]);
        }
        tab = [ ].concat(...buckets);
    }
    return tab
}

  function merge(tabGauche, tabDroit){
    let res = [];
    while (tabGauche.length && tabDroit.length) {
      // On ajoute le plus petit en premier
      if (tabGauche[0] < tabDroit[0]) {
        res.push(tabGauche.shift());
      } else {
        res.push(tabDroit.shift());
      }
    }
    // On concatene le tableau trié avec celui de la partie gauche et la partie droite
    return (res.concat(tabGauche)).concat(tabDroit);
}

function mergeSort(tab){
    if (tab.length <= 1){
        return tab;
    }
    let tabGauche = mergeSort(tab.slice(0, Math.floor(tab.length / 2)))
    let tabDroit = mergeSort(tab.slice(Math.floor(tab.length / 2)))
    return merge(tabGauche, tabDroit)
}

function shuffle(tab){
  for (let i = tab.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [tab[i], tab[j]] = [tab[j], tab[i]];
  }
  return tab;
}

function sorted(tab){
  for (let i = 0; i < tab.length - 1; i++) {
      if (tab[i] > tab[i + 1]) {
          return false;
      }
  }
  return true;
}

function bogoSort(tab){
  while (!sorted(tab)) {
      tab = shuffle(tab);
  }
}

function gnomeSort(tab){
  let i = 0;
  while (i < tab.length) {
      if (i === 0 || tab[i] >= tab[i - 1]) {
          i++;
      } else {
          swap(tab, i, i - 1);          
          i--;
      }
  }
}

function cocktailSort(tab){
  let start = 0;
  let end = tab.length - 1;
  let swapped = true;

  while (swapped) {
      swapped = false;

      for (let i = start; i < end; i++) {
          if (tab[i] > tab[i + 1]) {
              swap(tab, i, i + 1);
              swapped = true;
          }
      }

      if (!swapped) {
          break;
      }

      swapped = false;
      end--;

      for (let i = end - 1; i >= start; i--) {
          if (tab[i] > tab[i + 1]) {
              swap(tab, i, i + 1);
              swapped = true;
          }
      }

      start++;
  }
};

function oddEvenSort(tab){
  let sorted = false;
  while (!sorted) {
      sorted = true;
      // Phase impair 
      for (let i = 1; i < tab.length - 1; i += 2) {
          if (tab[i] > tab[i + 1]) {
              swap(tab, i, i + 1);
              sorted = false;
          }
      }
      // Phase pair 
      for (let i = 0; i < tab.length - 1; i += 2) {
          if (tab[i] > tab[i + 1]) {
              swap(tab, i, i + 1);

              sorted = false;
          }
      }
  }
};

function pigeonholeSort(tab){
  let min = Math.min(...tab);
  let max = Math.max(...tab);
  let range = max - min + 1;
  let pigeonholes = new Array(range).fill(0);
  let index = 0;

  for (let i = 0; i < tab.length; i++) {
      pigeonholes[tab[i] - min]++;
  }

  for (let i = 0; i < range; i++) {
      while (pigeonholes[i] > 0) {
          tab[index] = i + min;
          pigeonholes[i]--;
          index++;
      }
  }
};