Existem diversos algoritmos para colocar os elementos de uma lista em ordem. Um dos mais simples e mais implementados é o Bubble Sort. Nele, trocamos todos os elementos adjacentes que estejam fora de ordem:

________________________________________________________________

Podemos ver que agora que o algoritmo foi concluído, a lista de números está ordenada.

Em JavaScript:

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

Ao invés disso, podemos parar a execução do algoritmo quando percebermos que ele já está ordenado:

function bubbleSort2(l){
  const n = l.length

  for (let i = 0; i < n; i++){
    let switch = false;
    for (let j = 0; j < n-i-1; j++){
      if (l[j] > l[j+1]){
        [l[j], l[j+1]] = [l[j+1], l[j]];
        switch = true;
      }
    }
    if (!switch){
      return
    }
  }
}
                    

A complexidade do Bubble Sort é O(n²)

Para colocar os elementos de uma lista em ordem crescente, o método Selection Sort vai selecionando o menor elemento da lista e inserindo-o na frente dos demais, repetidamente. O algoritmo mantém a lista dividida em duas partes ao longo de sua execução:

• Os elementos já ordenados, no início da lista.
• O restante da lista a ser ordenada.

________________________________________________________________

Exemplo:

________________________________________________________________

Em JavaScript:

function selectionSort(l){
  for (let i = 0; i < l.length; i++){
    let smallerPos = i
    for (let j = i + 1; j < l.length;j++):
      if (l[smallerPos] > l[j]){
        smallerPos = j
        }
      }
    [l[i], l[smallerPos]] = [l[smallerPos], l[i]]
  }
}
                    

Um vantagem deste método é que ele nunca troca dois elementos de posição mais do que O(n) vezes.

O método Insertion Sort é um método simples de ordenação, que simula a forma como ordenamos as cartas de um baralho:

1. Inicialmente, escolho um elemento qualquer e insiro numa nova sequência, que por enquanto está ordenada.
2. Em seguida, escolho um outro elemento qualquer dentre os que faltam, e insiro-o ordenadamente na lista que contém os elementos já ordenados.
3. Caso ainda haja elementos a serem inseridos, volte ao passo 2.

________________________________________________________________

Exemplo:

________________________________________________________________

Em JavaScript:

function insertionSort(l){

  for (let k = 1; k < l.length; k++){
    const elem = l[k];
    let pos = k - 1;

    while (pos >== 0) && l[pos] > elem){
      l[pos + 1] = l[pos];
      pos = pos - 1;
    }

    l[pos + 1] = elem;
  }
}
                    

O método de ordenação Merge Sort é um algoritmo recursivo mais eficiente que o Bubble, Selection e Insertion Sort. A complexidade dele é O(n × lg n), enquanto os outros três são O(n²). Quando a complexidade de um algoritomo é O(f(n)), significa que o tempo é sempre proporcional a f(n) (no melhor caso, no pior caso e na média).

O algoritmo vai dividindo a sequência ao meio, até que haja apenas 1 elemento. Depois, vai mesclando as subsequências de forma que se mantenham ordenadas.

________________________________________________________________

Exemplo:

Resumindo, os passos acima, a ideia do algoritmo é a seguinte:

1. Se houver no máximo um elemento na sequência, ela está ordenada.
2. Se não, encontre o meio da sequência e divida-a em duas metades.
3. Recursivamente, ordene a metade da esquerda usando o próprio Merge Sort.
4. Recursivamente, ordene a metade da direita usando o próprio Merge Sort.
5. Junte as duas metades, de forma que o resultado se mantenha ordenado.

________________________________________________________________

O algoritmo em JavaScript é:

function mergeSort(arr){
  if (arr.length > 1){
    const mid = arr.length // 2;
    const leftArray = arr.slice(0, mid);
    const rightArray = arr.slice(mid + 1);

    mergeSort(leftArray);
    mergeSort(righttArray);
    
    merge(arr, leftArray, rightArray);
  }
}
                    

Para que ele funcione, é necessário criar uma função auxiliar que recebe duas listas ordenadas, e salva seus elementos em uma sequência ordenada:

function merge(arr, leftArray, rightArray){
  let i = 0;
  let j = 0;
  let k = 0;

  while (i < leftArray.length && j < rightArray.length){
    if (leftArray[i] < rightArray[j]){
        arr[k] = leftArray[i];
        i++;
    } else{
        arr[k] = rightArray[j];
        j++;
    }
    k++;
  }

  while (i < leftArray.length){
    arr[k] = leftArray[i];
    i++;
    k++;
  }

  while (j < rightArray.length){
    arr[k] = rightArray[j];
    j++;
    k++;
  } 
}
                    

Assim como o Merge Sort, o Quick Sort também divide o problema em problemas menores. Como vantagem, ele não necessita de armazenamento exxtra para criar sublistas. Como desvantagem, sua eficiência pode ser prejudicada se a escolha do pivô for ruim.

O algoritmo seleciona um elemento qualquer como o pivô. Em seguida, divide a sequência entre os menores que o pivô à sua esquerda e os maiores à direita. Em seguida, ordena cada sublista recursivamente.

No exemplo a seguir, fazemos toda a ordenação de uma sequência utilizando o Quick Sort:

Em JavaScript:

function quickSort(arr, inf, sup){
  if (inf < sup){
    const pos = particao(arr, inf, sup);
    quickSort(arr, inf, pos - 1);
    quickSort(arr, pos + 1, sup);
  }
}
                    

Para que o algoritmo funcione, a função auxiliar "partition" realiza a separacao entre menores e maiores, e retorna o índice do pivô após a partição:

function partition(arr, inf, sup){
  const pivot = arr[inf];
  let i = inf + 1;
  let j = sup;

  while (i <== j){
    while (i <== j && arr[i] <== pivot){
        i++;
    }
    while (j >== i && arr[j] > pivot){
        j--;
    }
    if (i < j){
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[inf], arr[j]] = [arr[j], arr[inf]];
  return j;
}