O que é um algoritmo de ordenação?

Os algoritmos de ordenação são um conjunto de instruções que recebem um array ou lista como entrada e organizam os itens em uma ordem específica.

As ordenações mais comumente realizadas são a numérica ou a alfabética (também chamada de lexicográfica) e podem ser em ordem crescente (A-Z, 0-9) ou decrescente (Z-A, 9-0).

Por que algoritmos de ordenação são importantes?

Os algoritmos de ordenação são importantes em Ciência da Computação porque a ordenação pode, muitas vezes, reduzir a complexidade de um problema. Esses algoritmos têm aplicações diretas em algoritmos de busca, algoritmos de banco de dados, métodos de divisão e conquista, algoritmos de estrutura de dados e muito mais.

Vantagens e desvantagens dos algoritmos

Ao usar algoritmos diferentes, algumas perguntas devem ser feitas. Qual o tamanho da coleção que está sendo ordenada? Quanta memória está disponível para uso? A coleção precisa crescer?

As respostas a essas perguntas podem determinar qual algoritmo funcionará melhor para a situação. Alguns algoritmos como a ordenação por intercalação (merge sort, em inglês) podem precisar de muito espaço para serem executados, enquanto a ordenação por inserção nem sempre é a mais rápida, mas não requer muitos recursos para isso.

Você deve determinar quais são os requisitos do sistema e suas limitações antes de decidir qual algoritmo usar.

Algoritmos de ordenação comuns

Alguns dos algoritmos de ordenação mais comuns são:

• Selection Sort (ordenação por seleção)
• Bubble Sort
• Insertion Sort (ordenação por inserção)
• Merge Sort (ordenação por intercalação)
• Quick Sort (ordenação rápida)
• Heap Sort
• Counting Sort
• Radix Sort
• Bucket Sort

Antes de detalharmos cada um deles, contudo, vamos aprender um pouco mais sobre como são classificados os algoritmos de ordenação.

Classificação de um algoritmo de ordenação

Os algoritmos de ordenação podem ser categorizados com base nos seguintes parâmetros:

1. Baseado no número de trocas ou inversões necessários: Este é o número de vezes que o algoritmo troca os elementos para ordenar uma entrada. A ordenação por seleção requer o número mínimo de trocas.
2. Baseado no número de comparações: Este é o número de vezes que o algoritmo compara elementos para ordenar uma entrada. Usando a notação Big-O, os exemplos de algoritmos de ordenação listados acima requerem, pelo menos, O(nlogn) comparações no melhor caso e O(n^2) comparações no pior caso para a maioria das saídas.
3. Baseado no uso ou não de recursão: Alguns algoritmos, tal como Quick Sort (ordenação rápida), usa técnicas recursivas para ordenar uma entrada. Outros algoritmos de ordenação, como  Selection Sort (ordenação por seleção) ou  Insertion Sort (ordenação por inserção), usam técnicas não recursivas. Por fim, alguns algoritmos de ordenação, como  Merge Sort (ordenação por intercalação), usam tanto técnicas recursivas como não recursivas para ordenar uma entrada.
4. Baseado na estabilidade: Algoritmos de ordenação são considerados  estáveis se o algoritmo mantiver a ordem relativa dos elementos com chaves iguais. Em outras palavras, dois elementos equivalentes permanecem, após a ordenação, na mesma ordem em que estavam antes da ordenação.
   Imagine, por exemplo, que tenhamos um array de entrada [1, 2, 3, 2, 4]. Para ajudar na diferenciação entre os valores que são iguais – neste caso, os 2 – usaremos 2a e 2b, tornando o array  [1, 2a, 3, 2b, 4].
   Algoritmos de ordenação estáveis manterão a ordem de 2a e 2b. Ou seja, teremos o algoritmo ordenado [1, 2a, 2b, 3, 4]. Já os instáveis, por sua vez, não mantêm a ordem dos valores iguais, resultando em [1, 2b, 2a, 3, 4]. Insertion sort ,  Merge Sort  e  Bubble Sort são estáveis, enquanto Heap Sort  e Quick Sort não são.
5. Baseado na necessidade de espaço adicional: Alguns algoritmos podem ordenar uma lista sem criar outra inteiramente nova. Chamamos um algoritmo assim de algoritmo de ordenação  in loco e ele requer um espaço adicional O(1) constante para a ordenação. Quando os algoritmos não são in loco,  uma outra lista é criada durante a ordenação.
   Insertion sort  e  Quick sort realizam a ordenação in loco, já que os elementos são movidos em torno de um ponto fixo e não utilizam um array à parte durante o processo de ordenação.
   No Merge sort, por outro lado, o tamanho da entrada deve ser alocado de antemão para armazenar a saída durante o processo de ordenação. Isso exige um espaço adicional na memória para o processo de ordenação.

Bucket Sort

Bucket Sort é um algoritmo de ordenação por comparação que opera em elementos dividindo-os em diferentes buckets (segmentos menores de mesmo tamanho) e, em seguida, ordenando esses buckets individualmente. Cada bucket é ordenado individualmente usando um algoritmo de ordenação separado ou aplicando o algoritmo de bucket sort recursivamente.

Bucket Sort é útil principalmente quando a entrada é distribuída uniformemente em um intervalo. Por exemplo, suponhamos que tenhamos recebido um array grande de números de ponto flutuante uniformemente distribuídos entre os limites inferior e superior e precisamos ordená-lo.

Uma maneira simples de se resolver esse problema seria usar um algoritmo de ordenação, como o Merge sort, o Heap Sort ou o Quick Sort. No entanto, esses algoritmos garantem uma complexidade de tempo de, no melhor caso, O(NlogN). Usando o bucket sort, contudo, a tarefa acima pode ser concluída em tempo O(N).

Pseudocódigo para Bucket Sort:

void bucketSort(float[] a,int n)

{

    for(each floating integer 'x' in a)

    {
        insert x into bucket[n*x]; 
    }

    for(each bucket)

    {
        sort(bucket);
    }

}

Counting Sort

Counting Sort é uma técnica de ordenação baseada em chaves compreendidas em um intervalo específico. Ela funciona contando o número de objetos com valores de chave distintos (tipo de hash). Em seguida, fazendo alguma operação para calcular a posição de cada objeto na sequência de saída.

Exemplo:

Para simplificar, considere os dados no intervalo de 0 a 9. 
Dados de entrada: 1, 4, 1, 2, 7, 5, 2
  1) Use um array para armazenar a contagem de cada objeto único.
  Índice:       0  1  2  3  4  5  6  7  8  9
  Contagem:     0  2  2  0  1  1  0  1  0  0

  2) Modifique o array de contagem de modo que cada elemento em cada índice armazene a soma das contagens anteriores. 
  Índice:       0  1  2  3  4  5  6  7  8  9
  Contagem:     0  2  4  4  5  6  6  7  7  7

O array de contagem modificado indica a posição que cada objeto ocupará no array de saída.
 
  3) Posicione cada objeto do array de entrada no array de saída de modo que sua posição final seja igual ao seu valor de contagem menos 1.
  Processe os dados de entrada: 1, 4, 1, 2, 7, 5, 2. A contagem do valor (no array de contagem) é 2.
  Assim, coloque o valor 1 no índice 1 (2 - 1) do array de saída. Subtraia 1 do valor de contagem aramazenado no índice 1 do array de contagem, de modo que o próximo valor do array de entrada seja colocado em uma posição, no array de saída, igual a esse valor menos 1.
  

Propriedades

• Complexidade espacial: O(K)
• Desempenho no melhor caso: O(n+K)
• Desempenho médio: O(n+K)
• Desempenho no pior caso: O(n+K)
• Estável: Sim (K é o número de elementos distintos no array)

Implementação em JavaScript

let numbers = [1, 4, 1, 2, 7, 5, 2];
let count = [];
let i, z = 0;
let max = Math.max(...numbers);      
// inicializar o contador
for (i = 0; i <= max; i++) {
    count[i] = 0;
}
for (i=0; i < numbers.length; i++) {
    count[numbers[i]]++;
}
for (i = 0; i <= max; i++) {
    while (count[i]-- > 0) {
        numbers[z++] = i;
    }
}
// dar como resultado o array ordenado
for (i=0; i < numbers.length; i++) {
    console.log(numbers[i]);
}

Implementação em C++

#include <iostream>

void countSort(int upperBound, int lowerBound, std::vector<int> numbersToSort) //limites superior e inferior dos números no vetor
{
  int range = upperBound - lowerBound;                  //cria um intervalo grande o suficiente para obter todos os números entre o mínimo e o máximo
  std::vector<int> counts (range);                      //inicializa contagens do tamanho do intervalo
  std::fill(counts.begin(), counts.end(), 0);           //preenche os vetores com zeros
  
  for (int i = 0; i < numbersToSort.size(); i++)
  {
      int index = numbersToSort[i] - lowerBound; //Por exemplo, se 5 for o limite inferior e numberToSort[i] for 5. index será 0 e o       counts[index]+= 1;                         //contagem de 5 será armazenada em counts[0]
  }
  
  std::cout << counts << std::endl;
} 

Implementação em Swift

func countingSort(_ array: [Int]) {
  // Cria um array para armazenar a contagem de cada elemento
  let maxElement = array.max() ?? 0
  var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
  
  for element in array {
    countArray[element] += 1
  }
  var z = 0
  var sortedArray = [Int](repeating: 0, count: array.count)

  for index in 1 ..< countArray.count {
    //exibe o elemento de índice o número de vezes necessárias
    while countArray[index] > 0 {
      sortedArray[z] = index
      z += 1
      countArray[index] -= 1
    }
  }
  
  print(sortedArray)
}

Insertion Sort (ordenação por inserção)

Insertion sort é um algoritmo de ordenação simples para um pequeno número de elementos.

Exemplo:

Em insertion sort, você compara o elemento  chave  com os elementos anteriores. Se os elementos anteriores são maiores do que o elemento chave, então você move o elemento anterior para a próxima posição.

Comece do índice 1 até o tamanho do array de entrada.

[ 8 3 5 1 4 2 ]

Passo 1 :

      chave = 3 //começando no índice 1.

      Aqui a `chave` será comparada com os elementos anteriores.

      Neste caso, `chave` é comparada com 8. Como 8 > 3, movemos o elemento 8 para a próxima posição e inserimos a `chave` na posição anterior.

      Resultado: [ 3 8 5 1 4 2 ]

Passo 2 :

      chave = 5 //índice 2

      8 > 5 //movemos o 8 para o índice 2 e inserimos o 5 no índice 1.

      Resultado: [ 3 5 8 1 4 2 ]

Passo 3 :

      chave = 1 //índice 3

      8 > 1     => [ 3 5 1 8 4 2 ]  

      5 > 1     => [ 3 1 5 8 4 2 ]

      3 > 1     => [ 1 3 5 8 4 2 ]

      Resultado: [ 1 3 5 8 4 2 ]

Passo 4 :

      chave = 4 //índice 4

      8 > 4   => [ 1 3 5 4 8 2 ]

      5 > 4   => [ 1 3 4 5 8 2 ]

      3 > 4   ≠>  pare

      Resultado: [ 1 3 4 5 8 2 ]

Passo 5 :

      chave = 2 //índice 5

      8 > 2   => [ 1 3 4 5 2 8 ]

      5 > 2   => [ 1 3 4 2 5 8 ]

      4 > 2   => [ 1 3 2 4 5 8 ]

      3 > 2   => [ 1 2 3 4 5 8 ]

      1 > 2   ≠> pare

      Resultado: [1 2 3 4 5 8]

O algoritmo mostrado abaixo é uma versão ligeiramente otimizada para evitar trocar o elemento chave em cada iteração. Aqui, o elemento  chave  será trocado ao final da iteração (step).

    InsertionSort(arr[])
      for j = 1 to arr.length
         key = arr[j]
         i = j - 1
         while i >= 0 and arr[i] > key
            arr[i+1] = arr[i]
            i = i - 1
         arr[i+1] = key
		

Aqui está uma implementação detalhada em JavaScript:

function insertion_sort(A) {
    var len = array_length(A);
    var i = 1;
    while (i < len) {
        var x = A[i];
        var j = i - 1;
        while (j >= 0 && A[j] > x) {
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j+1] = x;
        i = i + 1;
    }
}

Uma implementação rápida em Swift é mostrada abaixo:

  var array = [8, 3, 5, 1, 4, 2]

  func insertionSort(array:inout Array<Int>) -> Array<Int>{
      for j in 0..<array.count {
          let key = array[j]
          var i = j-1

          while (i > 0 && array[i] > key){
              array[i+1] = array[i]
              i = i-1
          }
          array[i+1] = key
      }
      return array
  }

O exemplo Java é mostrado abaixo:

public int[] insertionSort(int[] arr) {
      for (int j = 1; j < arr.length; j++) {
         int key = arr[j];
         int i = j - 1;
         while (i >= 0 && arr[i] > key) {
            arr[i+1] = arr[i];
            i -= 1;
         }
         arr[i+1] = key;
      }
      return arr;
}

E em  c....

void insertionSort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       j = i-1;
       while (j >= 0 && arr[j] > key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   } 
} 

Propriedades:

• Complexidade espacial: O(1)
• Complexidade temporal: O(n), O(n* n), O(n* n) para o melhor, médio e pior caso, respectivamente.
• Melhor caso: o array já está ordenado
• Caso médio: o array está ordenado aleatoriamente
• Pior caso: o array está ordenado em ordem inversa.
• Ordenação in loco: Sim
• Estável: Sim

Heapsort

Heapsort é um algoritmo de ordenação eficiente baseado no uso de estruturas de dados denominadas heaps (máxima/mínima). Um heap é uma estrutura de dados baseada em árvore que satisfaz a propriedade heap – ou seja, para um heap máximo, a chave de qualquer nó é menor ou igual à chave de seu pai (se tiver um pai).

Essa propriedade pode ser aproveitada para acessar o elemento máximo no heap em tempo O(logn) usando o método maxHeapify. Realizamos esta operação n vezes, cada vez movendo o elemento máximo no heap para o topo do heap e extraindo-o do heap para um array ordenado. Assim, após n iterações teremos uma versão ordenada do array de entrada.

O algoritmo exige que uma estrutura de dados heap seja construída primeiro. O algoritmo não é estável, o que significa que ao comparar objetos com a mesma chave, a ordenação original não será preservada.

Este algoritmo é executado em tempo O(nlogn) e requer espaço adicional O(1) [O(n) incluindo o espaço necessário para armazenar os dados de entrada], uma vez que todas as operações são executadas inteiramente in loco.

A complexidade de tempo melhor, pior e média do Heapsort é O(nlogn). Embora heapsort tenha uma complexidade de pior caso melhor do que o quicksort, quando bem implementado, o quicksort é executado mais rapidamente na prática. Heapsort é um algoritmo baseado em comparação, portanto, pode ser usado para conjuntos de dados não numéricos, na medida em que alguma relação (propriedade de heap) possa ser definida sobre os elementos.

Uma implementação em Java é apresentada abaixo :

import java.util.Arrays;
public class Heapsort {

	public static void main(String[] args) {
		//array de teste
		Integer[] arr = {1, 4, 3, 2, 64, 3, 2, 4, 5, 5, 2, 12, 14, 5, 3, 0, -1};
		String[] strarr = {"hope you find this helpful!", "wef", "rg", "q2rq2r", "avs", "erhijer0g", "ewofij", "gwe", "q", "random"};
		arr = heapsort(arr);
		strarr = heapsort(strarr);
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(strarr));
	}
	
	//O(nlogn) TEMPO, O(1) ESPAÇO, NÃO ESTÁVEL
	public static <E extends Comparable<E>> E[] heapsort(E[] arr){
		int heaplength = arr.length;
		for(int i = arr.length/2; i>0;i--){
			arr = maxheapify(arr, i, heaplength);
		}
		
		for(int i=arr.length-1;i>=0;i--){
			E max = arr[0];
			arr[0] = arr[i];
			arr[i] = max;
			heaplength--;
			arr = maxheapify(arr, 1, heaplength);
		}
		
		return arr;
	}
	
	//Cria maxheap a partir de um array
	public static <E extends Comparable<E>> E[] maxheapify(E[] arr, Integer node, Integer heaplength){
		Integer left = node*2;
		Integer right = node*2+1;
		Integer largest = node;
		
		if(left.compareTo(heaplength) <=0 && arr[left-1].compareTo(arr[node-1]) >= 0){
			largest = left;
		}
		if(right.compareTo(heaplength) <= 0 && arr[right-1].compareTo(arr[largest-1]) >= 0){
			largest = right;
		}	
		if(largest != node){
			E temp = arr[node-1];
			arr[node-1] = arr[largest-1];
			arr[largest-1] = temp;
			maxheapify(arr, largest, heaplength);
		}
		return arr;
	}
}

Implementação em C++

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; 
    int l = 2*i + 1;  
    int r = 2*i + 2;
    if (l < n && arr[l] > arr[largest]) 
        largest = l;
    if (r < n && arr[r] > arr[largest]) 
        largest = r;
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
  
        
        heapify(arr, n, largest); 
    } 
} 
  
 
void heapSort(int arr[], int n) 
{ 
    
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
  
    
    for (int i=n-1; i>=0; i--) 
    { 

        swap(arr[0], arr[i]); 
  
        
        heapify(arr, i, 0); 
    } 
} 
void printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; ++i) 
        cout << arr[i] << " "; 
    cout << "\n"; 
} 
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Array ordenado: \n"; 
    printArray(arr, n); 
}

Radix Sort

Prerrequisito: Counting Sort

QuickSort, MergeSort e HeapSort são algoritmos de ordenação baseados em comparação. CountSort não é. Tem a complexidade de O(n+k), onde k é o elemento máximo do array de entrada. Portanto, se k é O(n), CountSort se torna ordenação linear, o que é melhor do que algoritmos de ordenação baseados em comparação que possuem complexidade de tempo O(nlogn).

A ideia é estender o algoritmo CountSort para obter uma melhor complexidade de tempo quando k for O(n2). Aí vem a ideia do Radix Sort.

O algoritmo:

Para cada dígito i onde i varia do dígito menos significativo ao dígito mais significativo de um número, ordene o array de entrada usando o algoritmo countsort de acordo com o i-ésimo dígito. Usamos a countsort porque é uma ordenação estável.

Exemplo: Suponha que o array de entrada seja:

10, 21, 17, 34, 44, 11, 654, 123

Com base no algoritmo, vamos ordenar o array de entrada de acordo com o dígito das unidades (dígito menos significativo).

0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:

Assim, o array se torna 10, 21, 11, 123, 24, 44, 654, 17.

Agora, vamos ordenar de acordo com o dígito da dezena:

0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:

Agora, o array se torna: 10, 11, 17, 21, 123, 34, 44, 654.

Por fim, ordenamos de acordo com o dígito da centena (dígito mais significativo):

0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:

O array se torna: 10, 11, 17, 21, 34, 44, 123, 654, o qual está ordenado. É assim que nosso algoritmo funciona.

Uma implementação em  C:

void countsort(int arr[],int n,int place){

        int i,freq[range]={0};         //o intervalo para números inteiros é 10, pois os dígitos variam de 0 a 9
        int output[n];

        for(i=0;i<n;i++)
                freq[(arr[i]/place)%range]++;

        for(i=1;i<range;i++)
                freq[i]+=freq[i-1];
        
        for(i=n-1;i>=0;i--){
                output[freq[(arr[i]/place)%range]-1]=arr[i];
                freq[(arr[i]/place)%range]--;
        }
        
        for(i=0;i<n;i++)
                arr[i]=output[i];
}

void radixsort(ll arr[],int n,int maxx){            //maxx é o elemento máximo do array

        int mul=1;
        while(maxx){
                countsort(arr,n,mul);
                mul*=10;
                maxx/=10;
        }
}

Selection Sort

Selection Sort é um dos algoritmos de ordenação mais simples. Esse algoritmo recebe seu nome pela maneira como ele percorre o array ao longo das iterações: ele seleciona o menor elemento atual e o troca de lugar.

Veja como funciona:

1. Encontre o menor elemento no array e troque-o de lugar com o primeiro elemento.
2. Encontre o segundo menor elemento e troque com o segundo elemento no array.
3. Encontre o terceiro menor elemento e troque com o terceiro elemento no array.
4. Repita o processo de encontrar o próximo menor elemento e trocá-lo na posição correta até que todo o array esteja ordenado.

Mas, como você escreveria o código para encontrar o índice do segundo menor valor em um array?

Uma maneira fácil é notar que o menor valor já foi trocado para o índice 0, então o problema se reduz a encontrar o menor elemento no array começando no índice 1.

A ordenação por seleção sempre leva o mesmo número de comparações de chave — N(N − 1)/2.

Implementação em C/C++

O programa C++ a seguir contém uma implementação iterativa e recursiva do algoritmo Selection Sort. Ambas implementações são invocadas na função main().

#include <iostream>
#include <string>
using namespace std;

template<typename T, size_t n>
void print_array(T const(&arr)[n]) {
    for (size_t i = 0; i < n; i++)
        std::cout << arr[i] << ' ';
    cout << "\n";
}

int minIndex(int a[], int i, int j) {
    if (i == j)
        return i;
    int k = minIndex(a, i + 1, j);
    return (a[i] < a[k]) ? i : k;
}

void recurSelectionSort(int a[], int n, int index = 0) {
    if (index == n)
        return;
    int k = minIndex(a, index, n - 1);
    if (k != index)
        swap(a[k], a[index]);
    recurSelectionSort(a, n, index + 1);
}

void iterSelectionSort(int a[], int n) {
    for (int i = 0; i < n; i++)
    {
        int min_index = i;
        int min_element = a[i];
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < min_element)
            {
                min_element = a[j];
                min_index = j;
            }
        }
        swap(a[i], a[min_index]);
    }
}

int main() {
    int recurArr[6] = { 100,35, 500, 9, 67, 20 };
    int iterArr[5] = { 25, 0, 500, 56, 98 };

    cout << "Selection Sort Recursivo"  << "\n";
    print_array(recurArr); // 100 35 500 9 67 20
    recurSelectionSort(recurArr, 6);
    print_array(recurArr); // 9 20 35 67 100 500

    cout << "Selection Sort Iterativo" << "\n";
    print_array(iterArr); // 25 0 500 56 98
    iterSelectionSort(iterArr, 5);
    print_array(iterArr); // 0 25 56 98 500
}

Implementação em JavaScript

function selection_sort(A) {
    var len = A.length;
    for (var i = 0; i < len - 1; i = i + 1) {
        var j_min = i;
        for (var j = i + 1; j < len; j = j + 1) {
            if (A[j] < A[j_min]) {
                j_min = j;
            } else {}
        }
        if (j_min !== i) {
            swap(A, i, j_min);
        } else {}
    }
}

function swap(A, x, y) {
    var temp = A[x];
    A[x] = A[y];
    A[y] = temp;
}

Implementação em Python

def selection_sort(arr):
    if not arr:
        return arr
    for i in range(len(arr)):
        min_i = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_i]:
                min_i = j
        arr[i], arr[min_i] = arr[min_i], arr[i]

Implementação em Java

public void selectionsort(int array[])
{
    int n = array.length;            //método para calcular o tamanho do array 
    for (int i = 0; i < n-1; i++)
    {
        int index = i;
        int min = array[i];          // tomando o elemento min como i-ésimo elemento do array
        for (int j = i+1; j < n; j++)
        {
            if (array[j] < array[index])
            {
                index = j;
                min = array[j];
            }
        }
        int t = array[index];         //Troque os elementos de lugar
        array[index] = array[i];
        array[i] = t;
    }
}

Implementação em MATLAB

function [sorted] = selectionSort(unsorted)
    len = length(unsorted);
    for i = 1:1:len
        minInd = i;
        for j = i+1:1:len
           if unsorted(j) < unsorted(minInd) 
               minInd = j;
           end
        end
        unsorted([i minInd]) = unsorted([minInd i]);    
    end
    sorted = unsorted;
end

Propriedades

• Complexidade espacial:  O(n)
• Complexidade temporal:  O(n2)
• Ordenação in loco:  Sim
• Estável:  Não

Bubble Sort

Assim como as bolhas sobem do fundo de um copo, bubble sort é um algoritmo simples que ordena uma lista, permitindo que valores mais baixos ou mais altos borbulhem até o topo. O algoritmo percorre uma lista e compara valores adjacentes, trocando-os se não estiverem na ordem correta.

Com uma complexidade de pior caso de O(n^2), a ordenação por bolhas é muito lenta em comparação com outros algoritmos de ordenação como o quicksort. A vantagem é que é um dos algoritmos de ordenação mais fáceis de entender e implementar do zero.

Do ponto de vista técnico, o bubble sort é razoável para ordenar arrays de tamanho pequeno ou, especialmente, ao executar algoritmos de ordenação em computadores com recursos de memória notavelmente limitados.

Exemplo:

Primeira passagem pela lista:

• Começando com [4, 2, 6, 3, 9], o algoritmo compara os dois primeiros elementos no array, 4 e 2. Ele os troca porque 2 < 4: [2, 4, 6, 3, 9]
• Ele compara os dois próximos valores, 4 e 6. Como 4 < 6, e estes já estão em ordem, o algoritmo segue em frente: [2, 4, 6, 3, 9]
• Os próximos dois valores são trocados, porque 3 < 6: [2, 4, 3, 6, 9]
• Os dois últimos valores, 6 e 9, já estão em ordem, então o algoritmo não os troca.

Segunda passagem pela lista:

• 2 < 4, então não há necessidade de trocar as posições: [2, 4, 3, 6, 9]
• O algoritmo troca os próximos dois valores, porque 3 < 4: [2, 3, 4, 6, 9]
• Sem trocas, porque 4 < 6: [2, 3, 4, 6, 9]
• Novamente, 6 < 9, logo, nenhuma troca ocorre: [2, 3, 4, 6, 9]

A lista já está ordenada, mas o algoritmo bubble sort não percebe isso. Em vez disso, ele precisa concluir uma passagem inteira pela lista sem trocar nenhum valor para saber que a lista está ordenada.

Terceira passagem pela lista:

• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]
• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]
• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]
• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]

Claramente bubble sort está longe de ser o algoritmo de ordenação mais eficiente. Ainda assim, é simples entender e implementar você mesmo.

Propriedades

• Complexidade espacial: O(1)
• Performance no melhor caso: O(n)
• Performance no caso médio: O(n*n)
• Performance no pior caso: O(n*n)
• Estável: Sim

Explicação em vídeo

Bubble sort algorithm (em inglês)

Exemplo em JavaScript

let arr = [1, 4, 7, 45, 7,43, 44, 25, 6, 4, 6, 9],
    sorted = false;

while(!sorted) {
  sorted = true;
  for(var i=0; i < arr.length; i++) {
    if(arr[i] < arr[i-1]) {
      let temp = arr[i];
      arr[i] = arr[i-1];
      arr[i-1] = temp;
      sorted = false;
    }
  }
}

Exemplo em Java

public class BubbleSort {
    static void sort(int[] arr) {
        int n = arr.length;
        int temp = 0;
         for(int i=0; i < n; i++){
                 for(int x=1; x < (n-i); x++){
                          if(arr[x-1] > arr[x]){
                                 temp = arr[x-1];
                                 arr[x-1] = arr[x];
                                 arr[x] = temp;
                         }

                 }
         }

    }
    public static void main(String[] args) {

		for(int i=0; i < 15; i++){
			int arr[i] = (int)(Math.random() * 100 + 1);
		}

                System.out.println("array before sorting\n");
                for(int i=0; i < arr.length; i++){
                        System.out.print(arr[i] + " ");
                }
                bubbleSort(arr);
                System.out.println("\n array after sorting\n");
                for(int i=0; i < arr.length; i++){
                        System.out.print(arr[i] + " ");
                }

        }
}

Exemplo em C++

// Implementação por recursão
void bubblesort(int arr[], int n)
{
	if(n==1)	//Caso inicial
		return;
	bool swap_flag = false;
	for(int i=0;i<n-1;i++)	//Após essa passada, o elemento maior é movido para o local desejado.
	{
		if(arr[i]>arr[i+1])
		{
			int temp=arr[i];
			arr[i]=arr[i+1];
			arr[i+1]=temp;
			swap_flag = true;
		}
	}
        // Se não houver a troca de dois elementos no laço, retorna, pois o array está ordenado
	if(swap_flag == false)
		return;
	bubblesort(arr,n-1);	//Recursão para o restante do array
}

Exemplo em Swift

func bubbleSort(_ inputArray: [Int]) -> [Int] {
    guard inputArray.count > 1 else { return inputArray } // Garantir que nosso array de entrada tem mais de 1 elemento
    var numbers = inputArray // Argumentos de função são constantes por padrão em Swift, então fazemos uma cópia
    for i in 0..<(numbers.count - 1) {
        for j in 0..<(numbers.count - i - 1) {
            if numbers[j] > numbers[j + 1] {
                numbers.swapAt(j, j + 1)
            }
        }
    }
    return numbers // retorna o array ordenado
} 

Exemplo em Python

def bubbleSort(arr): 
    n = len(arr) 
    for i in range(n):
        for j in range(0, n-i-1):
                if arr[j] > arr[j+1] : 
                        arr[j], arr[j+1] = arr[j+1], arr[j]
    print(arr)

Exemplo em PHP

function bubble_sort($arr) {
    $size = count($arr)-1;
    for ($i=0; $i<$size; $i++) {
        for ($j=0; $j<$size-$i; $j++) {
            $k = $j+1;
            if ($arr[$k] < $arr[$j]) {
                // Troca os elementos nos índices: $j, $k
                list($arr[$j], $arr[$k]) = array($arr[$k], $arr[$j]);
            }
        }
    }
    return $arr;// retorna o array ordenado
}

$arr = array(1,3,2,8,5,7,4,0);
print("Before sorting");
print_r($arr);

$arr = bubble_sort($arr);
print("After sorting by using bubble sort");
print_r($arr);

Exemplo em C

#include <stdio.h>

int BubbleSort(int array[], int n);

int main(void) {
  int arr[] = {10, 2, 3, 1, 4, 5, 8, 9, 7, 6};
  BubbleSort(arr, 10);

  for (int i = 0; i < 10; i++) {
    printf("%d", arr[i]);
  }
  return 0;
}
int BubbleSort(int array[], n)
{
for (int i = 0 ; i < n - 1; i++)
  {
    for (int j = 0 ; j < n - i - 1; j++)     //n é o tamanho do array
    {
      if (array[j] > array[j+1])      // Para o uso com ordem decrescente 
      {
        int swap   = array[j];
        array[j]   = array[j+1];
        array[j+1] = swap;
      }
    }
  }
}

Quick Sort

Quick sort é um eficiente algoritmo de ordenação que emprega a técnica de divisão e conquista. A complexidade temporal no caso médio do Quick Sort é O(nlog(n)), sendo O(n^2) no pior caso dependendo da seleção do elemento pivô, que divide o array atual em dois subarrays.

Por exemplo, a complexidade de tempo do Quick Sort é aproximadamente O(nlog(n)) quando a seleção do pivô divide o array original em dois sub arrays de tamanhos quase iguais.

Por outro lado, se o algoritmo, que seleciona o elemento pivô dos arrays de entrada, produz consistentemente 2 sub-arrays com uma grande diferença em termos de tamanho, o algoritmo de ordenação rápida pode atingir a complexidade temporal de pior caso de O(n^2 ).

As etapas envolvidas no Quick Sort são:

• Escolha um elemento para servir como pivô, neste caso, o último elemento do array é o pivô.
• Particionamento: Ordene o array de forma que todos os elementos menores que o pivô fiquem à esquerda e todos os elementos maiores que o pivô fiquem à direita.
• Execute o algoritmo recursivamente, levando em consideração o pivô anterior para subdividir adequadamente os arrays esquerdo e direito. (Uma explicação mais detalhada pode ser encontrada nos comentários abaixo)

Exemplos de implementação em várias linguagens

Implementação em JavaScript:

const arr = [6, 2, 5, 3, 8, 7, 1, 4];

const quickSort = (arr, start, end) => {

  if(start < end) {

    // Você pode aprender sobre como o valor do pivô é derivado nos comentários abaixo
    let pivot = partition(arr, start, end);

    // Certifique-se de ler os comentários abaixo para entender por que pivô - 1 e pivô + 1 são usados
    // Estas são as chamadas recursivas do quickSort
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
  } 

}

const partition = (arr, start, end) => { 
  let pivot = end;
  // Defina i como start - 1 para que ele possa acessar o primeiro índice no caso de o valor em arr[0] ser maior que arr[pivot]
  // Os comentários abaixo explicarão o comentário acima
  let i = start - 1,
      j = start;

  // Incrementar j até o índice anterior ao pivô
  while (j < pivot) {

    // If the value is greater than the pivot increment j
    if (arr[j] > arr[pivot]) {
      j++;
    }

    // Quando o valor em arr[j] for menor que o pivô:
    // incremente i (arr[i] será um valor maior que arr[pivot]) e troque o valor em arr[i] e arr[j]
    else {
      i++;
      swap(arr, j, i);
      j++;
    }

  }

  //O valor em arr[i + 1] será maior que o valor de arr[pivot]
  swap(arr, i + 1, pivot);

  //Você retorna i + 1, pois os valores à esquerda dele são menores que arr[i+1], e os valores à direita são maiores que arr[i + 1]
  // Dessa forma, quando os quicksorts recursivos são chamados, os novos sub-arrays não incluirão este valor pivô usado anteriormente
  return i + 1;
}

const swap = (arr, firstIndex, secondIndex) => {
  let temp = arr[firstIndex];
  arr[firstIndex] = arr[secondIndex];
  arr[secondIndex] = temp;
}

quickSort(arr, 0, arr.length - 1);
console.log(arr);

Implementação em C

#include<stdio.h>  
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
}
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];     
    int i = (low - 1);  
  
    for (int j = low; j <= high- 1; j++) 
    { 
        if (arr[j] <= pivot) 
        { 
            i++;    
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
}
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    {
        int pi = partition(arr, low, high); 
  
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 
  

void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("n"); 
} 
  

int main() 
{ 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    quickSort(arr, 0, n-1); 
    printf("Sorted array: n"); 
    printArray(arr, n); 
    return 0; 
} 

Implementação em Python3

import random

z=[random.randint(0,100) for i in range(0,20)]

def quicksort(z):
    if(len(z)>1):        
        piv=int(len(z)/2)
        val=z[piv]
        lft=[i for i in z if i<val]
        mid=[i for i in z if i==val]
        rgt=[i for i in z if i>val]

        res=quicksort(lft)+mid+quicksort(rgt)
        return res
    else:
        return z
        
ans1=quicksort(z)
print(ans1)

Implementação em MATLAB

a = [9,4,7,3,8,5,1,6,2];

sorted = quicksort(a,1,length(a));

function [unsorted] =  quicksort(unsorted, low, high)
    if low < high
        [pInd, unsorted] = partition(unsorted, low, high);
        unsorted = quicksort(unsorted, low, pInd-1);
        unsorted = quicksort(unsorted, pInd+1, high);
    end

end

function [pInd, unsorted] = partition(unsorted, low, high)
    i = low-1;
    for j = low:1:high-1
        if unsorted(j) <= unsorted(high)
            i = i+1;
            unsorted([i,j]) = unsorted([j,i]);
            
        end
    end
    unsorted([i+1,high]) = unsorted([high,i+1]);
    pInd = i+1;

end

A complexidade espacial do quick sort é  O(n) . Esta é uma melhoria em relação a outros algoritmos de ordenação de divisão e conquista, que têm complexidade espacial de  O(nlong(n)).

Quick sort consegue isso alterando a ordem dos elementos dentro de um determinado array. Compare isso com o algoritmo merge sort que cria 2 arrays, cada um com tamanho n/2, a cada chamada da função.

No entanto existe o problema deste algoritmo de ordenação ser de tempo O(n*n)  se o pivô é sempre mantido no meio. Um problema que pode ser contornado utilizando-se um pivô aleatório

Complexidade

O uso de memória no melhor, médio e pior caso corresponde a n log(n)n, log(n)n e 2log(n) respectivamente. It's not a stable algorithm, and quicksort is usually done in-place with O(log(n)) stack space.

A complexidade espacial do quick sort é O(n). Esta é uma melhoria em relação a outros algoritmos de ordenação de divisão e conquista, que ocupam espaço O(n log(n)).

Timsort

Timsort é um algoritmo de ordenação rápido que trabalha com complexidade O(N log(N)) estável.

Timsort é uma mistura de Insertion Sort e Mergesort. Esse algoritmo é implementado no método Arrays.sort() em Java, bem como nas funções sorted() e sort() em Python. As partes menores são ordenadas usando o Insertion Sort e posteriormente mescladas usando Mergesort.

Uma rápida implementação em Python:

def binary_search(the_array, item, start, end):
    if start == end:
        if the_array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = round((start + end)/ 2)

    if the_array[mid] < item:
        return binary_search(the_array, item, mid + 1, end)

    elif the_array[mid] > item:
        return binary_search(the_array, item, start, mid - 1)

    else:
        return mid

"""
Insertion sort utilizada pelo timsort se o tamanho do array ou da "run" é pequeno.
"""
def insertion_sort(the_array):
    l = len(the_array)
    for index in range(1, l):
        value = the_array[index]
        pos = binary_search(the_array, value, 0, index - 1)
        the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]
    return the_array

def merge(left, right):
    """Recebe duas listas ordenadas e retorna uma única lista ordenada comparando os elementos um de cada vez.
    [1, 2, 3, 4, 5, 6]
    """
    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])

def timsort(the_array):
    runs, sorted_runs = [], []
    length = len(the_array)
    new_run = [the_array[0]]

    # Para cada i no intervalo de 1 até o tamanho do array
    for i in range(1, length):
        #se i está no final da lista
        if i == length - 1:
            new_run.append(the_array[i])
            runs.append(new_run)
            break
        # se o i-ésimo elemento do array for menor que o anterior
        if the_array[i] < the_array[i-1]:
            # se new_run estiver definido como None (nulo)
            if not new_run:
                runs.append([the_array[i]])
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                new_run = []
        # senão se for igual ou maior que
        else:
            new_run.append(the_array[i])

    # para cada item em runs, adicione o item usando insertion sort
    for item in runs:
        sorted_runs.append(insertion_sort(item))
    
    # para cada run em sorted_runs, mescle-as
    sorted_array = []
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    print(sorted_array)

timsort([2, 3, 1, 5, 6, 7])

Complexidade:

Tim sort tem uma complexidade estável de O(N log(N)) e se compara muito bem com Quicksort. Uma comparação de complexidades pode ser encontrada neste gráfico.

Merge Sort

Merge Sort é um algoritmo que emprega a técnica de divisão e conquista. Ele divide o array de entrada em duas metades, chama a si mesmo pelas duas metades e depois mescla as duas metades já ordenadas. A maior parte do algoritmo recebe dois arrays ordenados, e temos que mesclá-los em um único array ordenado. Todo o processo de ordenação de um array de N inteiros pode ser resumido em três etapas:

• Dividir o array em duas metades.
• Ordene a metade esquerda e a metade direita usando o mesmo algoritmo recursivamente.
• Mescle as metades ordenadas.

Existe um algoritmo chamado Two Finger Algorithm que nos ajuda a mesclar dois arrays ordenados. Usar essa sub-rotina e chamar a função merge sort nas metades do array recursivamente nos dará o array ordenado final que estamos procurando.

Como este é um algoritmo baseado em recursão, temos uma relação de recorrência para ele. Uma relação de recorrência é simplesmente uma maneira de representar um problema em termos de seus subproblemas.

T(n) = 2 * T(n / 2) + O(n)

Colocando em linguagem simples, dividimos o subproblema em duas partes em cada etapa e temos uma quantidade linear de trabalho que precisamos realizar para mesclar as duas metades ordenadas em cada etapa.

Complexidade

A maior vantagem de usar Merge sort é que a complexidade temporal é apenas n*log(n) para ordenar um array inteiro. É muito melhor do que a complexidade temporal de n^2 de execução de bubble sort ou insertion sort.

Antes de escrevermos o código, vamos entender como a ordenação por mesclagem funciona com a ajuda de um diagrama.

• Inicialmente temos um array de 6 inteiros não ordenados Arr(5, 8, 3, 9, 1, 2)
• Dividimos o array em duas metades Arr1 = (5, 8, 3) e Arr2 = (9, 1, 2).
• Novamente, nós os dividimos em duas metades: Arr3 = (5, 8) e Arr4 = (3) e Arr5 = (9, 1) e Arr6 = (2).
• Novamente, nós os dividimos em duas metades: Arr7 = (5), Arr8 = (8), Arr9 = (9), Arr10 = (1) e Arr6 = (2).
• Vamos agora comparar os elementos nesses sub-arrays para mesclá-los.

Propriedades:

• Complexidade espacial: O(n)
• Complexidade temporal: O(n*log(n)). A complexidade temporal para o Merge Sort pode não ser óbvia à primeira vista. O fator log(n) entra por causa da relação de recorrência que mencionamos anteriormente.
• Ordenação in-loco: Não em uma implementação típica
• Estável: Sim
• Paralelizável :sim (diversas variantes paralelas são discutidas na terceira edição do livro Introduction to Algorithms Cormen de Leiserson, Rivest, and Stein.)

Implementação em C++

void merge(int array[], int left, int mid, int right)
{
    int i, j, k;

    // tamanho do sub-array esquerdo
int size_left = mid - left + 1;

// tamanho do sub-array direito
int size_right =  right - mid;

/* Criar arrays temporários */
int Left[size_left], Right[size_right];

/* Copiar dados para os arrays temporários L[] e R[] */
for(i = 0; i < size_left; i++)
{
    Left[i] = array[left+i];
}

for(j = 0; j < size_right; j++)
{
    Right[j] = array[mid+1+j];
}

// Mesclar os arrays temporários de volta no arr[left..right]
i = 0; // índice inicial do sub-array esquerdo
j = 0; // índice inicial do sub-array direito
k = left; // índice inicial do array mesclado

while (i < size_left && j < size_right)
{
    if (Left[i] <= Right[j])
    {
        array[k] = Left[i];
        i++;
    }
    else
    {
        array[k] = Right[j];
        j++;
    }
    k++;
}

// Copiar os elementos restantes de Left[]
while (i < size_left)
{
    array[k] = Left[i];
    i++;
    k++;
}

// Copiar os elementos restantes de R[]
while (j < size_right)
{
    array[k] = Right[j];
    j++;
    k++;
}
}

void mergeSort(int array[], int left, int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;

        // Ordenar a primeira e a segunda metade
    mergeSort(array, left, mid);
    mergeSort(array, mid+1, right);

    // Finalmente, mesclá-las
    merge(array, left, mid, right);
}
}

Implementação em JavaScript

function mergeSort (arr) {
  if (arr.length < 2) return arr;
  var mid = Math.floor(arr.length /2);
  var subLeft = mergeSort(arr.slice(0,mid));
  var subRight = mergeSort(arr.slice(mid));
  return merge(subLeft, subRight);
}

Primeiro, verificamos o comprimento do array. Se for 1, simplesmente retornamos o array. Este seria o nosso caso base. Caso contrário, descobriremos o valor do meio e dividiremos o array em duas metades. Agora vamos ordenar ambas metades com chamadas recursivas da função MergeSort.

function merge (a,b) {
    var result = [];
    while (a.length >0 && b.length >0)
        result.push(a[0] < b[0]? a.shift() : b.shift());
    return result.concat(a.length? a : b);
}

Quando mesclamos as duas metades, armazenamos o resultado em um array auxiliar. Vamos comparar o elemento inicial do array esquerdo com o elemento inicial do array direito. O que for menor será enviado para o array de resultados e o removeremos dos respectivos arrays usando o operador [shift() . Se ainda restarem valores no array esquerdo ou direito, simplesmente o concatenamos no final do resultado. Aqui está o resultado ordenado:

var test = [5,6,7,3,1,3,15];
console.log(mergeSort(test));

>> [1, 3, 3, 5, 6, 7, 15]

Um tutorial sobre Merge Sort no YouTube

Aqui está um bom vídeo do YouTube que aborda o tópico em detalhes (em inglês).

Implementação em JS

const list = [23, 4, 42, 15, 16, 8, 3]

const mergeSort = (list) =>{
  if(list.length <= 1) return list;
  const middle = list.length / 2 ;
  const left = list.slice(0, middle);
  const right = list.slice(middle, list.length);
  return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
  var result = [];
  while(left.length || right.length) {
    if(left.length && right.length) {
      if(left[0] < right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    } else if(left.length) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
  return result;
}

console.log(mergeSort(list)) // [ 3, 4, 8, 15, 16, 23, 42 ]

Implementação em C

#include<stdlib.h> 
#include<stdio.h>
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    
    int L[n1], R[n2]; 
  
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j];
    i = 0; 
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    {  
        int m = l+(r-l)/2; 
  
        
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
}
void printArray(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
  
    printf("Given array is \n"); 
    printArray(arr, arr_size); 
  
    mergeSort(arr, 0, arr_size - 1); 
  
    printf("\nSorted array is \n"); 
    printArray(arr, arr_size); 
    return 0; 

Implementação em C++

Vamos considerar o array A = {2,5,7,8,9,12,13} e array B = {3,5,6,9,15} e queremos que o array C esteja ordenado em ordem crescente também.

void mergesort(int A[],int size_a,int B[],int size_b,int C[])
{
     int token_a,token_b,token_c;
     for(token_a=0, token_b=0, token_c=0; token_a<size_a && token_b<size_b; )
     {
          if(A[token_a]<=B[token_b])
               C[token_c++]=A[token_a++];
          else
               C[token_c++]=B[token_b++];
      }
      
      if(token_a<size_a)
      {
          while(token_a<size_a)
               C[token_c++]=A[token_a++];
      }
      else
      {
          while(token_b<size_b)
               C[token_c++]=B[token_b++];
      }

}

Implementação em Python

def merge(left,right,compare):
	result = [] 
	i,j = 0,0
	while (i < len(left) and j < len(right)):
		if compare(left[i],right[j]):
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	while (i < len(left)):
		result.append(left[i])
		i += 1
	while (j < len(right)):
		result.append(right[j])
		j += 1
	return result

def merge_sort(arr, compare = lambda x, y: x < y):
     #Função lambda usada para ordenar um array em ordem crescente e decrescente.
     #Por padrão, ela ordena o array em ordem crescente
	if len(arr) < 2:
		return arr[:]
	else:
		middle = len(arr) // 2
		left = merge_sort(arr[:middle], compare)
		right = merge_sort(arr[middle:], compare)
		return merge(left, right, compare) 

arr = [2,1,4,5,3]
print(merge_sort(arr))

Implementação em Java

public class mergesort {

	public static int[] mergesort(int[] arr,int lo,int hi) {
		
		if(lo==hi) {
			int[] ba=new int[1];
			ba[0]=arr[lo];
			return ba;
		}
		
		int mid=(lo+hi)/2;
		int arr1[]=mergesort(arr,lo,mid);
		int arr2[]=mergesort(arr,mid+1,hi);
		return merge(arr1,arr2);
	}
	
	public static int[] merge(int[] arr1,int[] arr2) {
		int i=0,j=0,k=0;
		int n=arr1.length;
		int m=arr2.length;
		int[] arr3=new int[m+n];
		while(i<n && j<m) {
			if(arr1[i]<arr2[j]) {
				arr3[k]=arr1[i];
				i++;
			}
			else {
				arr3[k]=arr2[j];
				j++;
			}
			k++;
		}
		
		while(i<n) {
			arr3[k]=arr1[i];
			i++;
			k++;
		}
		
		while(j<m) {
			arr3[k]=arr2[j];
			j++;
			k++;
		}
		
		return arr3;
		
	}
	
	public static void main(String[] args) {
		int arr[]= {2,9,8,3,6,4,10,7};
		int[] so=mergesort(arr,0,arr.length-1);
		for(int i=0;i<arr.length;i++)
			System.out.print(so[i]+" ");
	}

}

Boas-vindas! Se você sempre quis aprender e entender o algoritmo de Dijkstra, este artigo é para você. Você verá como ele funciona nos bastidores com uma explicação gráfica passo a passo.

Você aprenderá:

• Conceitos básicos sobre grafos (uma breve revisão).
• Para que o algoritmo de Dijkstra é utilizado.
• Como o algoritmo funciona através de um exemplo passo a passo.

Vamos começar. ✨

🔹 Introdução aos grafos

Vamos começar com uma breve introdução aos grafos.

Conceitos básicos

Grafos são estruturas de dados usadas para representar "conexões" entre pares de elementos.

• Esses elementos são chamados de nós (ou vértices). Eles representam objetos, pessoas ou entidades da vida real.
• As conexões entre os nós são chamadas de arestas.

Esta é uma representação gráfica de um grafo:

Os nós são representados por círculos coloridos e as arestas são representadas por linhas que conectam esses círculos.

💡 Dica: dois nós estarão conectados se houver uma aresta entre eles.

Aplicações

Os grafos são diretamente aplicáveis a cenários do mundo real. Por exemplo, poderíamos usá-los para modelar uma rede de transporte, onde os nós representariam instalações que enviam ou recebem produtos e arestas representariam estradas ou caminhos que os conectam (veja abaixo).

Tipos de grafos

Os grafos podem ser:

• Não dirigidos: se para cada par de nós conectados, você pode ir de um nó para o outro em ambas as direções.
• Dirigidos: se para cada par de nós conectados, você só pode ir de um nó para outro em uma direção específica. Usamos setas em vez de linhas simples para representar arestas dirigidas.

💡 Dica: neste artigo, abordaremos grafos não dirigidos.

Grafos ponderados

Um grafo ponderado é um grafo cujas arestas têm um "peso" ou "custo". O peso de uma aresta pode representar distância, tempo ou qualquer coisa que modele a "conexão" entre o par de nós que ela conecta.

Por exemplo, no grafo ponderado abaixo, você pode ver um número em azul próximo de cada aresta. Este número é usado para representar o peso da aresta correspondente.

💡 Dica: esses pesos são essenciais para o Algoritmo de Dijkstra. Você verá por que a seguir.

🔸 Introdução ao algoritmo de Dijkstra

Agora que você conhece os conceitos básicos de grafos, vamos nos aprofundar nesse algoritmo incrível.

• Propósito e casos de uso
• História
• Elementos básicos do algoritmo
• Requisitos

Propósito e casos de uso

Com o algoritmo de Dijkstra, você poderá encontrar o caminho de menor custo entre nós em um grafo. Particularmente, você poderá encontrar o caminho de menor custo entre um nó (denominado “origem”) e todos os outros nós do grafo, produzindo uma árvore de custo-mínimo.

Este algoritmo é usado em dispositivos GPS para encontrar o caminho mais curto entre a localização atual e o destino. Ele possui ampla aplicação na indústria, principalmente em domínios que requerem modelagem de redes

História

Este algoritmo foi criado e publicado pelo Dr. Edsger W. Dijkstra, um brilhante cientista da computação e engenheiro de software holandês.

Em 1959, ele publicou um artigo de 3 páginas intitulado "A note on two problems in connexion with graphs" (Uma nota sobre dois problemas em conexão com grafos, em tradução livre), onde explicou seu novo algoritmo.

Durante uma entrevista em 2001, o dr. Dijkstra revelou como e por que desenvolveu o algoritmo:

Qual é o caminho mais curto para viajar de Roterdã a Groningen? É o algoritmo para o caminho mais curto, que projetei em aproximadamente 20 minutos. Certa manhã, eu estava fazendo compras em Amsterdã com minha noiva e, cansado, sentamos no terraço do café para beber uma xícara de café e eu estava pensando se poderia fazer isso, e então, desenvolvi o algoritmo para o caminho mais curto . Como eu disse, foi uma invenção de 20 minutos. Na verdade, foi publicado em 1959, três anos depois. A publicação continua bem legal. Uma das razões por que ela é tão legal foi que eu a desenhei sem lápis e papel. Sem lápis e papel, você é quase forçado a evitar todas as complexidades evitáveis. Eventualmente, esse algoritmo se tornou, para minha grande surpresa, um dos pilares da minha fama. — Conforme citado no artigo Edsger W. Dijkstra em An interview with Edsger W. Dijkstra (Uma entrevista com Edsger W. Dijkstra).

⭐ Inacreditável, não? Em apenas 20 minutos, o Dr. Dijkstra desenvolveu um dos algoritmos mais famosos da história da Ciência da Computação.

Noções básicas do algoritmo de Dijkstra

• O Algoritmo de Dijkstra basicamente começa no nó que você escolhe (o nó de origem) e analisa o grafo para encontrar o caminho de menor custo entre esse nó e todos os outros nós do grafo.
• O algoritmo mantém o registro da distância mais curta atualmente conhecida de cada nó até o nó de origem e atualiza esses valores se encontrar um caminho de menor custo.
• Uma vez que o algoritmo encontrou o caminho de menor custo entre o nó de origem e outro nó, esse nó é marcado como "visitado" e adicionado ao caminho.
• O processo continua até que todos os nós do grafo tenham sido adicionados ao caminho. Desta forma, temos um caminho que conecta o nó de origem a todos os outros nós seguindo o caminho de menor custo possível para chegar a cada nó.

Requisitos

O Algoritmo de Dijkstra só funciona com grafos com pesos positivos. Isso porque, durante o processo, os pesos das arestas devem ser somados para encontrar o caminho de menor custo.

Se houver um peso negativo no grafo, o algoritmo não funcionará corretamente. Uma vez que um nó tenha sido marcado como "visitado", o caminho atual para esse nó é marcado como o caminho de menor custo para chegar a esse nó. E pesos negativos podem alterar isso se o peso total puder ser decrementado após essa etapa ter ocorrido.

🔹 Exemplo do algoritmo de Dijkstra

Agora que você sabe mais sobre esse algoritmo, vamos ver como ele funciona nos bastidores com um exemplo passo a passo.

Temos este grafo:

O algoritmo gerará o caminho de menor custo (neste caso, o caminho mais curto) do nó 0 para todos os outros nós do grafo.

💡 Dica: neste caso, assumiremos que o peso das arestas representa a distância entre dois nós.

Teremos o caminho mais curto do nó 0 ao nó 1, do nó 0 ao nó 2, do nó 0 ao nó 3, e assim por diante para cada nó do grafo.

Inicialmente, temos esta lista de distâncias (veja a lista abaixo):

• A distância do nó de origem até ele mesmo é 0. Para este exemplo, o nó de origem será o nó 0, mas pode ser qualquer nó que você escolher.
• A distância do nó de origem para todos os outros nós ainda não foi determinada, então usamos o símbolo do infinito para representar isso inicialmente.

Também temos esta lista (veja abaixo) para acompanhar os nós que ainda não foram visitados (nós que não foram incluídos no caminho):

💡 Dica: lembre-se de que o algoritmo é concluído quando todos os nós forem adicionados ao caminho.

Como estamos escolhendo começar no nó 0, podemos marcar esse nó como visitado. De forma equivalente, nós o cortamos da lista de nós não visitados e adicionamos uma borda vermelha ao nó correspondente no diagrama:

Agora precisamos verificar a distância do nó 0 até seus nós adjacentes. Como você pode ver, estes são os nós  1 e 2 (veja as bordas vermelhas):

💡 Dica: isso não significa que estamos adicionando imediatamente os dois nós adjacentes ao caminho mais curto. Antes de adicionar um nó a este caminho, precisamos verificar se encontramos o caminho mais curto para alcançá-lo. Estamos simplesmente fazendo um processo de exame inicial para ver as opções disponíveis.

Precisamos atualizar as distâncias do nó 0 ao 1 e ao nó 2 com os pesos das arestas que os conectam ao nó 0 (origem). Estes pesos são 2 e 6, respectivamente:

Após atualizar as distâncias dos nós adjacentes, precisamos:

• Selecionar o nó mais próximo do nó de origem com base nas distâncias conhecidas atuais.
• Marcá-lo como visitado.
• Adicioná-lo ao caminho.

Se verificarmos a lista de distâncias, podemos ver que o nó 1 tem a menor distância até a origem (distância igual a 2), então, nós o adicionamos ao caminho.

No diagrama, podemos representar isso com uma aresta vermelha:

Marcamos com um quadrado vermelho na lista para representar que foi "visitado" e que encontramos o caminho mais curto para este nó:

Riscamos da lista de nós não visitados:

Agora, precisamos analisar os novos nós adjacentes para encontrar o caminho mais curto para alcançá-los. Analisaremos apenas os nós que são adjacentes aos nós que já fazem parte do caminho mais curto (o caminho marcado com arestas vermelhas).

Os nós 3 e 2 são ambos adjacentes aos nós que já estão no caminho porque estão diretamente conectados aos nós1 e 0, respectivamente, como você pode ver abaixo. Esses são os nós que analisaremos na próxima etapa.

Como já temos a distância do nó de origem ao nó 2 anotado em nossa lista, não precisamos atualizar a distância desta vez. Precisamos apenas atualizar a distância do nó de origem ao novo nó adjacente (o nó 3):

Essa distância é igual a 7. Vamos ver o porquê.

Para encontrar a distância do nó de origem para outro nó (neste caso, nó 3), somamos os pesos de todas as arestas que formam o caminho mais curto para chegar a esse nó:

• No caso do nó 3: a distância total é 7 porque adicionamos os pesos das arestas que formam o caminho0 -> 1 -> 3 (2  para a aresta 0 -> 1 e 5 para a aresta 1 -> 3).

Agora que temos a distância até os nós adjacentes, temos que escolher qual nó será adicionado ao caminho. Devemos selecionar o nó não visitado com a distância mais curta (atualmente conhecida) até o nó de origem.

A partir da lista de distâncias, podemos detectar imediatamente que este é um nó 2 cuja distância é 6:

Adicionamos ao caminho graficamente com uma borda vermelha ao redor do nó e uma aresta vermelha:

Também o marcamos como visitado adicionando um pequeno quadrado vermelho na lista de distâncias e riscando-o da lista de nós não visitados:

Agora precisamos repetir o processo para encontrar o caminho mais curto do nó de origem até o novo nó adjacente, que é o nó 3.

Você pode ver que temos dois caminhos possíveis 0 -> 1 -> 3 ou 0 -> 2 -> 3. Vamos ver como podemos decidir qual é o caminho mais curto.

O nó 3 já possui uma distância na lista que foi registrada anteriormente (7, veja a lista abaixo). Essa distância foi resultado de um passo anterior, onde somamos os pesos 5 e 2 das duas arestas que precisávamos cruzar para seguir o caminho 0 -> 1 -> 3.

Mas agora temos outra alternativa. Se escolhermos seguir o caminho0 -> 2 -> 3, precisaríamos seguir duas arestas 0 -> 2 e 2 -> 3 com pesos 6 e 8, respectivamente, o que representa uma distância total igual a 14.

Claramente, a primeira distância (existente) é menor (7 x 14), então escolheremos manter o caminho original 0 -> 1 -> 3. Só atualizamos a distância se o novo caminho for mais curto.

Portanto, adicionamos este nó ao caminho usando a primeira alternativa: 0 -> 1 -> 3.

Marcamos este nó como visitado e o riscamos da lista de nós não visitados:

Agora, repetimos esse processo.

Precisamos verificar os novos nós adjacentes que não visitamos até agora. Desta vez, esses nós são os nós 4 e 5, já que ambos são adjacentes ao nó 3.

Atualizamos as distâncias desses nós até o nó de origem, sempre tentando encontrar um caminho mais curto, se possível:

• No caso do nó 4: a distância é 17 para o caminho  0 -> 1 -> 3 -> 4.
• No caso do nó 5: a distância é 22 para o caminho 0 -> 1 -> 3 -> 5.

💡 Dica: Observe que só podemos considerar estender o caminho mais curto (marcado em vermelho). Não podemos considerar caminhos que nos levarão através de arestas que não foram adicionadas ao caminho mais curto (por exemplo, não podemos formar um caminho que passe pela aresta2 -> 3).

Precisamos escolher qual nó não visitado será marcado como visitado. Neste caso, é o nó 4 porque tem a distância mais curta na lista de distâncias. Adicionamos graficamente no diagrama:

Também o marcamos como "visitado" adicionando um pequeno quadrado vermelho na lista:

E o riscamos da lista de nós não visitados:

E repetimos o processo novamente. Verificamos os nós adjacentes: nós 5 e 6. Precisamos analisar cada caminho possível que podemos seguir para alcançá-los a partir de nós que já foram marcados como visitados e adicionados ao caminho.

No caso do nó 5:

• A primeira opção é seguir o caminho 0 -> 1 -> 3 -> 5, que tem uma distância de 22 para o nó de origem (2 + 5 + 15). Essa distância já foi registrada na lista de distâncias em uma etapa anterior.
• A segunda opção seria seguir o caminho 0 -> 1 -> 3 -> 4 -> 5, que tem uma distância de 23 para o nó de origem (2 + 5 + 10 + 6).

Claramente, o primeiro caminho é mais curto, então o escolhemos para nó 5.

No caso do nó 6:

• O caminho disponível é 0 -> 1 -> 3 -> 4 -> 6, que tem uma distância de 19 para o nó de origem (2 + 5 + 10 + 2).

Marcamos o nó com a distância mais curta (atualmente conhecida) como visitada. Neste caso, o nó6.

E o riscamos da lista de nós não visitados:

Agora temos este caminho (marcado em vermelho):

Apenas um nó ainda não foi visitado, o nó 5. Vamos ver como podemos incluí-lo no caminho.

Existem três caminhos diferentes que podemos seguir para alcançar o nó 5a partir dos nós que foram adicionados ao caminho:

• Opção 1: 0 -> 1 -> 3 -> 5 com uma distância de 22 (2 + 5 + 15).
• Opção 2: 0 -> 1 -> 3 -> 4 -> 5 com uma distância de 23 (2 + 5 + 10 + 6).
• Opção 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 com uma distância de 25 (2 + 5 + 10 + 2 + 6).

Selecionamos o caminho: 0 -> 1 -> 3 -> 5 com uma distância de 22.

Marcamos o nó como visitado e o riscamos da lista de nós não visitados:

E aí está! Temos o resultado final com o caminho mais curto do nó 0 até cada nó do grafo.

No diagrama, as linhas vermelhas marcam as arestas que pertencem ao caminho mais curto. Você precisa seguir essas arestas para seguir o caminho mais curto para chegar a um determinado nó no grafo a partir do nó 0.

Por exemplo, se você deseja alcançar o nó 6 a partir do nó 0, basta seguir as arestas vermelhas e estará, automaticamente, seguindo o caminho mais curto 0 -> 1 -> 3 -> 4 - > 6.

🔸 Resumindo

• Os grafos são usados para modelar conexões entre objetos, pessoas ou entidades. Eles têm dois elementos principais: nós e arestas. Os nós representam objetos e as arestas representam as conexões entre esses objetos.
• O algoritmo de Dijkstra encontra o caminho mais curto entre um determinado nó (que é chamado de "nó de origem") e todos os outros nós em um grafo.
• Este algoritmo usa os pesos das arestas para encontrar o caminho que minimiza a distância total (peso) entre o nó de origem e todos os outros nós.

Eu realmente espero que você tenha gostado do artigo e o tenha achado útil. Agora, você sabe como o algoritmo de Dijkstra funciona nos bastidores. Siga a autora no Twitter (@EstefaniaCassN) e confira os cursos da autora on-line.

Embora nada realmente mude, exceto a data, um novo ano deixa todos nós com a esperança de começar de novo. Se você adicionar um pouco de planejamento, algumas metas bem planejadas e um roteiro de aprendizagem, terá uma ótima receita para um ano cheio de crescimento.

Esta postagem pretende fortalecer seu plano, fornecendo uma estrutura de aprendizagem, recursos e ideias de projetos para ajudá-lo a construir um portfólio sólido de trabalho apresentando experiência em ciência de dados.

Apenas uma observação: preparei este roteiro com base na minha experiência pessoal em ciência de dados. Este não é o plano de aprendizagem definitivo. Você pode adaptar este roteiro para melhor se adequar a qualquer domínio ou campo de estudo específico que lhe interesse. Além disso, ele foi criado com o Python em mente, pois eu pessoalmente prefiro essa linguagem.

O que é um roteiro de aprendizagem?

Um roteiro de aprendizagem é uma extensão de um programa de estudos. Ele traça um mapa de habilidades de vários níveis com detalhes sobre quais habilidades você deseja aprimorar, como você medirá o resultado em cada nível e técnicas para dominar ainda mais cada habilidade.

Meu roteiro atribui pesos a cada nível com base na complexidade e semelhança de sua aplicação no mundo real. Eu também adicionei um tempo estimado para um iniciante completar cada nível com exercícios e projetos.

Aqui está uma pirâmide que descreve as habilidades de alto nível em ordem de complexidade e aplicação no setor.

Ela marcará a base de nossa estrutura. Agora teremos que nos aprofundar em cada um desses estratos para completar nossa estrutura com detalhes mais específicos e mensuráveis.

A especificidade vem do exame dos tópicos críticos em cada camada e dos recursos necessários para dominar esses tópicos.

Podemos medir o conhecimento adquirido, aplicando os tópicos aprendidos a vários projetos do mundo real. Adicionei algumas ideias de projetos, portais e plataformas que você pode usar para medir sua proficiência.

NOTA importante: viva um dia de cada vez, um vídeo/blog/capítulo por dia. É um amplo espectro para se cobrir. Não se sobrecarregue!

Vamos mergulhar profundamente em cada um desses estratos, começando pela base.

1. Como aprender sobre programação ou engenharia de software

(Tempo estimado: 2-3 meses)

Primeiro, certifique-se de ter boas habilidades de programação. Toda descrição de trabalho de ciência de dados exigirá experiência em programação em pelo menos uma linguagem.

Tópicos específicos de programação a serem conhecidos incluem:

• Estruturas de dados comuns (tipos de dados, listas, dicionários, conjuntos, tuplas), funções, lógica, controle de fluxo, algoritmos de busca e ordenação, programação orientada a objetos e trabalho com bibliotecas externas
• Scripts de SQL: consultas a bancos de dados usando JOIN, funções de agregação e subconsultas
• Tranquilidade no uso do Terminal, controle de versão usando Git e GitHub

Recursos para aprender Python:

• learnpython.org [gratuito]— um recurso gratuito para iniciantes. Abrange todos os tópicos básicos de programação desde o básico. Você dispõe de um shell interativo para praticar esses tópicos lado a lado.
• Kaggle [gratuito]— um guia gratuito e interativo para aprender Python. É um tutorial curto que cobre todos os tópicos importantes para a ciência de dados.
• Certificações de Python no freeCodeCamp [gratuito] – o freeCodeCamp oferece diversas certificações baseadas em Python, como computação científica, análise de dados e aprendizagem de máquina.
• Curso de Python no canal do freeCodeCamp no YouTube [gratuito] — Este é um curso de 5 horas que você pode fazer para praticar os conceitos básicos.
• Python intermediário [gratuito]— Outro curso gratuito apresentado no freecodecamp.org pelo Patrick.
• Python for Everybody Specialization (Especialização em Python para todos) no Coursera [pago] — esta é uma especialização que abrange conceitos de nível iniciante, estruturas de dados em Python, coleta de dados da web e uso de bancos de dados com Python.

Recursos para aprender Git e GitHub

• Guia para Git e GitHub [gratuito]: complete esses tutoriais e laboratórios para ter uma ideia sólida de controle de versão. Esses cursos o ajudarão a contribuir ainda mais para projetos de código aberto.
• Aqui temos um curso intensivo sobre Git e GitHub no canal do freeCodeCamp no YouTube.

Recursos para aprender SQL

• Aqui, temos um curso sobre SQL e bancos de dados no canal do freeCodeCamp no YouTube
• Introdução ao SQL e SQL avançado no Kaggle.
• Treehouse oferece um bom curso introdutório sobre SQL aqui.

Meça sua experiência resolvendo muitos problemas e construindo pelo menos 2 projetos:

• Resolva muitos problemas em: HackerRank (recomendado para iniciantes) e LeetCode (resolva questões fáceis ou de nível médio)
• Extração de dados de um site/endpoints  de APIs — tente escrever scripts em Python para extrair dados de páginas da web que permitem scraping (raspagem da web) como o soundcloud.com. Armazene os dados extraídos em um arquivo CSV ou em um banco de dados SQL.
• Jogos como pedra-papel-tesoura, girar o novelo, forca, simulador de rolagem de dados, jogo da velha e assim por diante.
• Aplicativos web simples, como um programa para baixar vídeos do YouTube, bloqueador de sites, reprodutor de música, verificador de plágio e assim por diante.

Hospede esses projetos em páginas do GitHub Pages ou simplesmente mantenha os códigos no GitHub para que você aprenda a usar o Git.

2. Como aprender sobre coleta de dados e  "data wrangling" (limpeza/manipulação)

(Tempo estimado: 2 meses)

Uma parte significativa do trabalho de ciência de dados está centrada em encontrar dados adequados que possam ajudá-lo a resolver seu problema. Você pode coletar dados de diferentes fontes legítimas — scraping (raspagem - se o site permitir), APIs, bancos de dados e repositórios disponíveis publicamente.

Uma vez que você tenha os dados em mãos, como um analista, frequentemente, você se encontrará limpando dataframes, trabalhando com arrays multidimensionais, usando cálculos descritivos/científicos e manipulando dataframes para agregar dados.

No mundo real, raramente, os dados são encontrados limpos, formatados e prontos para uso. Pandas e NumPy são as duas bibliotecas que estão à sua disposição para transformar dados brutos em dados prontos para análise.

À medida que você começar a se sentir confortável escrevendo programas em Python, sinta-se à vontade para começar a ter aulas sobre o uso de bibliotecas como pandas e numpy.

Recursos para aprender sobre coleta e limpeza de dados:

• Curso sobre Numpy, Pandas, matplotlib e seaborn no freeCodeCamp [gratuito].
• Tutorial prático da HackerEarth sobre manipulação de dados com NumPy e Pandas, usando o Python.
• Tutorial sobre pandas da Kaggle [gratuito] — um tutorial prático curto e conciso que o guiará pelas habilidades mais comuns de manipulação de dados.
• Curso de limpeza de dados da Kaggle.
• Curso de Introdução à Ciência de Dados usando Python do Coursera  — este é o primeiro curso da Especialização em Ciência de Dados com Python.

Ideias de projetos de coleta de dados:

• Colete dados de um site/API (aberto para consumo público) de sua escolha e transforme os dados para armazená-los de diferentes fontes em um arquivo ou tabela agregada (DB). Exemplos de APIs incluem: TMDB, quandl, Twitter API, e assim por diante.
• Escolha qualquer conjunto de dados disponível publicamente e defina um conjunto de perguntas que você gostaria de responder depois de analisar o conjunto de dados e o domínio. Manipule os dados para encontrar respostas para essas perguntas usando Pandas e NumPy.

3. Como aprender sobre análise exploratória de dados, Business Acumen, and Storytelling

(Tempo estimado: 2–3 meses)

A próxima etapa a ser dominada compreende a análise de dados e o storytelling (contar a história, em inglês). Extrair insights dos dados e, em seguida, comunicá-los aos gestores, fazendo uso de expressões simples e visualizações é a principal responsabilidade de um analista de dados.

A parte do storytelling exige que você seja proficiente em visualização de dados, além de possuir excelentes habilidades de comunicação.

Tópicos específicos de análise de dados exploratórios e storytelling para aprender incluem:

• Análise de dados exploratória — definição de perguntas, tratamento de dados faltantes, pontos fora da curva (também conhecidos pela palavra em inglês, outliers), formatação, filtragem, análises univariada e multivariada.
• Visualização de dados — construção de gráficos, usando bibliotecas como matplotlib, seaborn e plotly. Saber como escolher o gráfico certo para comunicar as conclusões obtidas a partir dos dados.
• Desenvolvimento de dashboards — uma boa porcentagem de analistas usa apenas o Excel ou uma ferramenta especializada como Power BI e Tableau para criar dashboards que resumem/agregam dados para ajudar os gestores a tomar decisões.
• Conhecimento de negócios: faça as perguntas certas e responda as que são realmente relacionadas às métricas de negócios. Pratique a redação de relatórios, blogs e apresentações claras e concisas.

Recursos para aprender mais sobre análise de dados:

• Aprenda análise de dados com Python neste curso gratuito no canal do freeCodeCamp no YouTube.
• Análise de dados com Python — da IBM no Coursera. O curso abrange data wrangling, análise exploratória e desenvolvimento de modelos simples usando Python.
• Visualização de dados — Kaggle. Outro curso interativo que permite praticar a construção de gráficos comumente utilizados.
• Desenvolva senso de produto e business acumen com estes livro: Measure what matters (Avalie o que importa), Decode and conquer (Decodificar e Conquistar), Cracking the PM interview.

Ideias de projetos de análise de dados

• Análise exploratória de bancos de dados de filmes para encontrar a fórmula para criar filmes lucrativos (use como inspiração). Use conjuntos de dados de saúde, finanças, OMS, censos anteriores, comércio eletrônico e assim por diante.
• Construa dashboards (jupyter notebooks, excel, tableau) usando os recursos fornecidos acima.

4. Como aprender sobre engenharia de dados

(Tempo estimado: 4–5 meses)

A engenharia de dados sustenta as equipes de Pesquisa e Desenvolvimento, tornando os dados limpos acessíveis a engenheiros de pesquisa e cientistas em empresas orientadas a big data. É um campo por si só, e você pode pular esta seção se quiser se concentrar apenas na parte dos algoritmos estatísticos.

As responsabilidades de um engenheiro de dados incluem construir uma arquitetura de dados eficiente, simplificar o processamento de dados e manter sistemas de dados em grande escala.

Engenheiros de dados usam o Shell (interface de linha de comando – CLI), SQL e Python/Scala para criar pipelines de extração, transformação e carga de dados (ETL, do inglês Extract, Transform and Load), automatizar tarefas do sistema de arquivos e otimizar as operações do banco de dados para torná-las de alto desempenho.

Outra habilidade essencial é implementar essas arquiteturas de dados que exigem proficiência em provedores de serviços em nuvem como AWS, Google Cloud Platform, Microsoft Azure e outros.

Recursos para aprender engenharia de dados:

• Data Engineering Nanodegree da Udacity — no que diz respeito a uma lista compilada de recursos, não encontrei um curso mais bem estruturado sobre engenharia de dados que cubra todos os principais conceitos do zero.
• Especialização em Engenharia de Dados, Big Data e Aprendizagem de Máquina na GCP — Você pode concluir esta especialização oferecida pelo Google no Coursera, que orienta você por todas as principais APIs e serviços oferecidos pela GCP (Google Cloud Platform) para criar uma solução de dados completa.

Ideias de projetos/preparação para certificações em engenharia de dados:

• AWS Certified Machine Learning (US$ 300) — um exame supervisionado oferecido pela AWS adiciona algum peso ao seu perfil (embora não garanta nada), requer uma compreensão razoável dos serviços da AWS e ML.
• Professional Data Engineer — este também é um exame supervisionado e avalia suas habilidades para projetar sistemas de processamento de dados, implantar modelos de aprendizagem de máquina em um ambiente de produção e garantir a qualidade e a automação das soluções.

5. Como aprender sobre Estatística Aplicada e Matemática

(Tempo estimado: 4–5 meses)

Os métodos estatísticos são uma parte central da ciência de dados. Quase todas as entrevistas de ciência de dados se concentram predominantemente em estatísticas descritivas e inferenciais.

As pessoas geralmente começam a programar algoritmos de aprendizagem de máquina sem uma compreensão clara dos métodos estatísticos e matemáticos subjacentes que explicam o funcionamento desses algoritmos. Esta, claro, não é a melhor maneira de fazer isso.

Tópicos em que você deve se concentrar em Estatística Aplicada e Matemática:

• Estatística Descritiva — ser capaz de resumir os dados é uma habilidade poderosa, mas nem sempre. Aprenda sobre medidas de posição (média, mediana, moda, estatísticas ponderadas, estatísticas truncadas) e variabilidade para descrever os dados.
• Estatística Inferencial — projetar testes de hipóteses, testes A/B, definir métricas de negócios, analisar os dados coletados e resultados de experimentos usando intervalo de confiança, valor p e valores alfa.
• Álgebra Linear, Cálculo uni e multivariado para entender as funções de custo, gradiente e otimizadores em aprendizagem de máquina.

Recursos para aprender sobre Estatística e Matemática:

• Aprenda Estatística de nível universitário neste curso gratuito de 8 horas no canal do freeCodeCamp no YouTube
• [Livro] Estatística prática para cientistas de dados (altamente recomendado) — um guia completo sobre todos os métodos estatísticos importantes, juntamente com aplicações/exemplos claros e concisos.
• [Livro] Naked Statistics — um guia não técnico, mas detalhado, para entender o impacto das estatísticas em nossos eventos de rotina, esportes, sistemas de recomendação e muitos outros casos.
• Statistical thinking in Python — um curso básico para ajudá-lo a começar a pensar estatisticamente. Há uma segunda parte para este curso também.
• Intro to Descriptive Statistics— oferecido pela Udacity. Consiste em aulas em vídeo, explicando medidas amplamente utilizadas de posição e variabilidade (desvio padrão, variância, desvio médio absoluto).
• Inferential Statistics, Udacity — o curso consiste em aulas em vídeo que ensinam você a tirar conclusões a partir de dados que podem não ser imediatamente óbvios. Ele se concentra no desenvolvimento de hipóteses e usa testes comuns, como teste t, ANOVA e regressão.
• E aqui está um guia de Estatística para Ciência de Dados para ajudá-lo a começar no caminho certo.

Ideias de projetos de Estatística:

• Resolva os exercícios fornecidos nos cursos acima e tente passar por vários conjuntos de dados públicos onde você pode aplicar esses conceitos estatísticos. Faça perguntas como “Existem evidências suficientes para concluir que a idade média das mães que dão à luz em Boston é superior a 25 anos no nível de significância de 0,05”?
• Tente projetar e executar pequenos experimentos com seus colegas/grupos/turmas, pedindo que eles interajam com um aplicativo ou respondam a uma pergunta. Execute métodos estatísticos nos dados coletados quando tiver uma boa quantidade de dados após um período de tempo. Isso pode ser muito difícil de conseguir, mas deve ser muito interessante.
• Analise os preços das ações, criptomoedas e hipóteses de design em torno do retorno médio ou qualquer outra métrica. Determine se você pode rejeitar a hipótese nula ou deixar de fazê-lo usando valores críticos.

6. Como aprender sobre aprendizagem de máquina e IA

(Tempo estimado: 4–5 meses)

Depois de se questionar e passar por todos os principais conceitos mencionados acima, agora você deve estar pronto para começar com os sofisticados algoritmos de ML (Machine Learning - Aprendizagem de Máquina).

Há três tipos principais de aprendizagem:

1. Aprendizagem supervisionada — inclui problemas de regressão e classificação. Estude regressão linear simples, regressão múltipla, regressão polinomial, Naive Bayes, regressão logística, KNNs, árvores de classificação, modelos ensemble. Saiba mais sobre as métricas de avaliação.
2. Aprendizagem não supervisionada— agrupamento e redução de dimensionalidade são as duas aplicações amplamente utilizadas de aprendizagem não supervisionada. Mergulhe profundamente em PCA, agrupamento K-means, agrupamento hierárquico e misturas gaussianas.
3. Aprendizagem por reforço (não obrigatório*) — ajuda você a construir sistemas de autorrecompensa. Aprenda a otimizar recompensas, usando a biblioteca TF-Agents, criando Q-networks profundas e assim por diante.

A maioria dos projetos de ML precisa que você domine várias tarefas explicadas neste artigo.

Recursos para aprender sobre Aprendizagem de Máquina:

• Aqui temos um curso completo  de Aprendizagem de máquina usando Python e a biblioteca SciKitLearn no canal do freeCodeCamp no YouTube.
• [Livro] Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow, 2nd Edition — um dos meus livros favoritos de todos os tempos sobre aprendizagem de máquina. Não cobre apenas as derivações matemáticas teóricas, mas também mostra a implementação de algoritmos através de exemplos. Você deve resolver os exercícios dados no final de cada capítulo.
• Curso de Aprendizagem de Máquina por Andrew Ng — curso obrigatório para quem está tentando aprender machine learning. Definitivamente!
• Introduction to Machine Learning — Curso interativo no Kaggle.
• Intro to Game AI and Reinforcement Learning — outro curso interativo no Kaggle sobre aprendizagem por reforço.

Especialização em Deep Learning na deeplearning.ai

Para aqueles que estão interessados em mergulhar ainda mais em Deep Learning, você pode começar concluindo esta especialização oferecida pela deeplearning.ai e o livro Hands-On. Isso não é tão importante do ponto de vista da ciência de dados, a menos que você esteja planejando resolver um problema de visão computacional ou NLP (do inglês Natural Language Processing - processamento de linguagens naturais).

Deep Learning merece um roteiro dedicado. Vou criar um com todos os conceitos fundamentais em breve.

Acompanhe seu progresso de aprendizagem

Também criei uma página no Notion onde você poderá acompanhar sua aprendizagem. Você pode personalizá-la de acordo com suas necessidades e usá-la para acompanhar seu progresso, ter acesso fácil a todos os recursos e seus projetos.

Aqui está o link.

Além disso, aqui está a versão em vídeo deste artigo:

Ciência de dados com Harshit

Esta é apenas uma visão geral de alto nível do amplo espectro da ciência de dados. Você pode querer se aprofundar em cada um desses tópicos e criar um plano de menor rigor baseado em conceitos para cada uma das categorias.

Se este tutorial foi útil para você, confira os cursos do autor sobre Ciência de Dados e Aprendizagem de Máquina na Wiplane Academy. Eles são abrangentes, mas compactos, e ajudam você a construir uma base sólida de trabalho para mostrar.

Python e SQL são duas das linguagens mais importantes para analistas de dados.

Neste artigo, mostrarei tudo que você precisa saber para conectar o Python e o SQL.

Você aprenderá a obter dados de bancos de dados relacionais diretamente de seus pipelines de aprendizado de máquina, armazenar dados de suas aplicações em Python em um banco de dados próprio ou qualquer outro caso de uso que possa surgir.

Juntos, vamos aprender:

• Por que aprender a usar Python e SQL juntos?
• Como configurar seu ambiente Python e MySQL Server
• Conectar ao MySQL Server usando Python
• Criar um novo banco de dados
• Criar tabelas e relacionamentos entre elas
• Preencher as tabelas com dados
• Ler dados
• Atualizar registros
• Apagar registros
• Criar registros a partir de listas do Python
• Criar funções reutilizáveis para fazer tudo isso por nós no futuro

São muitas coisas úteis e interessantes. Vamos começar!

Um breve comentário antes de começarmos: um Jupyter Notebook com todos os códigos usados neste tutorial está disponível neste repositório do GitHub. Reproduzir os códigos enquanto lê este artigo é altamente recomendado!

O banco de dados e os códigos SQL usados aqui são todos provenientes da minha série Introduction to SQL (Introdução ao SQL) publicada (em inglês) no site Towards Data Science (entre em contato se tiver algum problema para visualizar os artigos e eu enviarei um link para que eles possam ser acessados gratuitamente).

Se não está acostumado com SQL e com os conceitos subjacentes aos bancos de dados relacionais, eu indicaria essa série (além disso, é claro que há uma enorme quantidade de artigos excelentes disponíveis aqui no freeCodeCamp!)

Por que Python com SQL?

Para analistas de dados e cientistas de dados, o Python apresenta muitas vantagens. Uma enorme variedade de bibliotecas de código aberto o torna uma ferramenta incrivelmente útil para qualquer analista de dados.

Nós temos o pandas, o NumPy e o Vaex para análise de dados, o Matplotlib, o seaborn e o Bokeh para visualização, além do TensorFlow, do scikit-learn e do PyTorch para aprendizagem de máquina (além de muitas, muitas outras).

Com sua curva de aprendizagem (relativamente) fácil e versatilidade, não é de admirar que o Python seja uma das linguagens de programação que mais crescem.

Portanto, se optar por usar Python para análise de dados, vale a pena perguntar: de onde vêm todos esses dados?

Embora haja uma enorme variedade de fontes para conjuntos de dados, em muitos casos – particularmente, em empresas - os dados são armazenados em um banco de dados relacional. Os bancos de dados relacionais são uma maneira extremamente eficiente, poderosa e amplamente utilizada para criar, ler, atualizar e excluir dados de todos os tipos.

Os sistemas de gerenciamento de bancos de dados relacionais (SGBDR) mais utilizados - Oracle, MySQL, Microsoft SQL Server, PostgreSQL, IBM DB2 - usam a Linguagem de Consulta Estruturada (SQL, da sigla em inglês, Structured Query Language) para acessar e modificar os dados.

Observe que cada SGBDR usa um tipo um pouco diferente de SQL. Portanto, o código SQL escrito para um geralmente não funcionará com outro sem modificações (normalmente pequenas). No entanto, os conceitos, estruturas e operações são, em grande parte, idênticos.

Isso quer dizer que, para um analista de dados, uma sólida compreensão de SQL é de grande importância. Saber como usar Python e SQL juntos dará a você uma vantagem ainda maior na hora de trabalhar com os seus dados.

O restante deste artigo será dedicado a mostrar exatamente como podemos fazer isso.

Para começar

Requisitos e instalação

Para programar junto com este tutorial, você precisará do seu próprio ambiente Python configurado.

Eu uso a distribuição Anaconda, mas há muitas maneiras de fazer isso. Basta pesquisar no Google "como instalar o Python" se precisar de ajuda. Você também pode usar o Binder para programar usando um Jupyter Notebook associado.

Nós vamos usar o MySQL Community Server, que é gratuito e amplamente utilizado na indústria. Se estiver utilizando o Windows, este guia (em inglês) o ajudará na hora de configurar. Aqui estão os guias para os usuários de Mac e Linux  (embora as instruções possam variar de acordo com a distribuição Linux utilizada).

Depois de configurados, precisaremos fazer com que eles se comuniquem.

Para isso, precisaremos instalar a biblioteca MySQL Connector para o Python. Faça isso seguindo estas instruções, ou simplesmente use o pip:

pip install mysql-connector-python

Também utilizaremos a biblioteca pandas. Certifique-se de que ela também esteja instalada.

pip install pandas

Importando as bibliotecas

Como em todo projeto em Python, a primeira coisa que devemos fazer é importar nossas bibliotecas.

É uma boa prática importar todas as bibliotecas que vamos usar no início do projeto. Assim, as pessoas que lerão ou revisarão nosso código saberão, até certo ponto, o que está por vir, sem surpresas.

Para este tutorial, utilizaremos apenas duas bibliotecas - o MySQL Connector e o pandas.

import mysql.connector
from mysql.connector import Error
import pandas as pd

Importamos a função Error separadamente para que tenhamos acesso fácil a ela em nossas funções.

Conectando ao MySQL Server

A essa altura, já devemos ter o MySQL Community Server configurado em nosso sistema. Agora, precisamos escrever um código em Python que nos permita estabelecer uma conexão com este servidor.

def create_server_connection(host_name, user_name, user_password):
    connection = None
    try:
        connection = mysql.connector.connect(
            host=host_name,
            user=user_name,
            passwd=user_password
        )
        print("MySQL Database connection successful")
    except Error as err:
        print(f"Error: '{err}'")

    return connection

É uma boa prática a criação de uma função para tornar reutilizável um código como esse, permitindo que ele seja utilizado repetidas vezes com o mínimo de esforço. Uma vez criado, você poderá reutilizá-lo em todos os seus projetos futuros e o seu “eu do futuro” será grato!

Vamos revisar o código, linha por linha, para entendermos o que está acontecendo aqui:

Na primeira linha, damos um nome à função (create_server_connection) e aos seus argumentos (host_name, user_name e user_password).

Na linha seguinte, encerramos quaisquer conexões existentes para que o servidor não fique confuso com várias conexões abertas.

Em seguida, usamos um  bloco try-except (texto em inglês) do Python para lidar com possíveis erros. A primeira parte tenta criar uma conexão com o servidor usando o método mysql.connector.connect() (texto em inglês) e os detalhes especificados pelo usuário nos argumentos da função. Se isso funcionar, a função imprime uma pequena mensagem de sucesso.

O código referente ao bloco except imprime o erro que o MySQL Server retorna se, infelizmente, houver um erro.

Por fim, se a conexão for bem-sucedida, a função retornará um objeto de conexão (texto em inglês).

Na prática, atribuímos o resultado dessa função a uma variável, que então se torna o nosso objeto de conexão. Podemos, depois disso, aplicar outros métodos, como o cursor (texto em inglês), a ele e criar outros objetos úteis.

connection = create_server_connection("localhost", "root", pw)

O código abaixo deve resultar em uma mensagem de sucesso:

Criando um novo banco de dados

Agora que estabelecemos uma conexão, nosso próximo passo é criar um banco de dados em nosso servidor.

Neste tutorial, faremos isso uma única vez, mas, novamente, criaremos uma função reutilizável de modo que tenhamos um código que possamos reutilizar em projetos futuros.

def create_database(connection, query):
    cursor = connection.cursor()
    try:
        cursor.execute(query)
        print("Database created successfully")
    except Error as err:
        print(f"Error: '{err}'")

Essa função recebe dois argumentos, connection (nosso objeto de conexão) e query (um código SQL que escreveremos na próxima etapa). Ela executa a consulta no servidor através da conexão.

Usamos o método cursor do nosso objeto de conexão para criar um objeto do tipo cursor (o MySQL Connector usa o paradigma de programação orientado a objetos, portanto, há muitos objetos herdando propriedades de objetos pai).

Este objeto cursor possui métodos como execute, executemany (que usaremos neste tutorial - textos em inglês) assim como vários outros métodos úteis.

Se ajudar, podemos pensar que o objeto cursor dá acesso ao cursor que fica piscando em um terminal do MySQL Server.

Em seguida, definimos uma consulta para criar o banco de dados e executar a função:

Todos os códigos SQL deste tutorial estão explicados na minha série de tutoriais Introduction to SQL (Introdução ao SQL, em inglês), e o código completo está disponível em um Jupyter Notebook neste repositório do GitHub. Portanto, não explicarei o que o código SQL faz neste tutorial.

No entanto, esse é talvez o código SQL mais simples possível. Se você pode ler em inglês, provavelmente pode descobrir o que ele faz!

Executar a função create_database com os argumentos acima resulta na criação de um banco de dados chamado 'school' em nosso servidor.

Por que nosso banco de dados é chamado de 'school' (escola)? Talvez agora seja um bom momento para examinarmos em mais detalhes o que vamos implementar exatamente neste tutorial.

Nosso banco de dados

Seguindo o exemplo da minha série anterior, implementaremos o banco de dados para a International Language School (Escola Internacional de Idiomas) - uma escola fictícia de treinamento de idiomas que oferece aulas de idiomas profissionais para clientes corporativos.

O Diagrama Entidade Relacionamento (DER) (texto em inglês) apresenta as entidades (Teacher, Client, Course e Participant) e define as relações entre elas.

Todas as informações sobre o que é um DER e o que considerar ao criar um e projetar um banco de dados podem ser encontradas neste artigo (em inglês).

O código SQL, os requisitos do banco de dados e os dados para inclusão no banco de dados estão todos disponíveis neste repositório do GitHub, mas você também verá tudo à medida que avançarmos neste tutorial.

Conectando ao banco de dados

Agora que criamos um banco de dados no MySQL Server, podemos modificar nossa função create_server_connection para conectar diretamente a esse banco de dados.

Observe que é possível - comum, na verdade - ter vários bancos de dados em um servidor MySQL, então queremos nos conectar sempre e automaticamente ao banco de dados em que estamos interessados.

Podemos fazer da seguinte maneira:

def create_db_connection(host_name, user_name, user_password, db_name):
    connection = None
    try:
        connection = mysql.connector.connect(
            host=host_name,
            user=user_name,
            passwd=user_password,
            database=db_name
        )
        print("MySQL Database connection successful")
    except Error as err:
        print(f"Error: '{err}'")

    return connection

Essa é exatamente a mesma função, mas agora temos mais um argumento - o nome do banco de dados - que é passado para o método connect().

Criando uma função para execução de consultas

A última função que criaremos (por enquanto) é extremamente vital - uma função de execução de consulta. Ela pegará nossas consultas SQL, armazenadas como strings do Python, e as passará para que o método cursor.execute() as execute no servidor.

def execute_query(connection, query):
    cursor = connection.cursor()
    try:
        cursor.execute(query)
        connection.commit()
        print("Query successful")
    except Error as err:
        print(f"Error: '{err}'")

Essa função é idêntica à nossa função create_database, exceto por usar o método connection.commit() para garantir que os comandos detalhados em nossas consultas SQL sejam implementados.

Essa função será nosso carro-chefe, que usaremos (junto com create_db_connection) para criar tabelas, estabelecer relacionamentos entre essas tabelas, preencher as tabelas com dados e atualizar e excluir registros em nosso banco de dados.

Se você for um especialista em SQL, essa função permitirá que você execute todos e quaisquer comandos e consultas complexas que você possa ter, diretamente de um script em Python. Ela pode ser uma ferramenta muito poderosa para gerenciar seus dados.

Criando tabelas

Agora estamos prontos para começar a executar comandos SQL em nosso servidor e começar a construir nosso banco de dados. A primeira coisa que queremos fazer é criar as tabelas necessárias.

Vamos começar com a tabela Teacher (professor, em inglês):

create_teacher_table = """
CREATE TABLE teacher (
  teacher_id INT PRIMARY KEY,
  first_name VARCHAR(40) NOT NULL,
  last_name VARCHAR(40) NOT NULL,
  language_1 VARCHAR(3) NOT NULL,
  language_2 VARCHAR(3),
  dob DATE,
  tax_id INT UNIQUE,
  phone_no VARCHAR(20)
  );
 """

connection = create_db_connection("localhost", "root", pw, db) # Connect to the Database
execute_query(connection, create_teacher_table) # Execute our defined query

Primeiro, atribuímos nosso comando SQL (explicado em detalhes aqui) a uma variável com um nome apropriado.

Neste caso, usamos a notação de aspas triplas do Python para definir strings que se estendem por múltiplas linhas (texto em inglês) para armazenar nossa consulta SQL. Então, nós a passamos para a função execute_query que a executará.

Observe que essa formatação de várias linhas é puramente para facilitar a leitura do código por humanos. Nem SQL nem Python 'se importam' se o comando SQL estiver distribuído dessa maneira. Desde que a sintaxe esteja correta, ambas as linguagens a aceitarão.

Para o bem dos humanos que lerão seu código (mesmo que seja apenas o você do futuro!), é muito útil empregar essa formatação para tornar o código mais legível e compreensível.

O mesmo vale para o uso de expressões do SQL em LETRAS MAIÚSCULAS. Esta é uma convenção amplamente usada e que é fortemente recomendada, mas o software real que executa o código não diferencia maiúsculas de minúsculas e tratará 'CREATE TABLE teacher' e 'create table teacher' como comandos idênticos.

A execução deste código retorna nossas mensagens de sucesso. Também podemos verificar isso no client na linha de comando do MySQL Server:

Excelente! Agora vamos criar as tabelas restantes.

create_client_table = """
CREATE TABLE client (
  client_id INT PRIMARY KEY,
  client_name VARCHAR(40) NOT NULL,
  address VARCHAR(60) NOT NULL,
  industry VARCHAR(20)
);
 """

create_participant_table = """
CREATE TABLE participant (
  participant_id INT PRIMARY KEY,
  first_name VARCHAR(40) NOT NULL,
  last_name VARCHAR(40) NOT NULL,
  phone_no VARCHAR(20),
  client INT
);
"""

create_course_table = """
CREATE TABLE course (
  course_id INT PRIMARY KEY,
  course_name VARCHAR(40) NOT NULL,
  language VARCHAR(3) NOT NULL,
  level VARCHAR(2),
  course_length_weeks INT,
  start_date DATE,
  in_school BOOLEAN,
  teacher INT,
  client INT
);
"""


connection = create_db_connection("localhost", "root", pw, db)
execute_query(connection, create_client_table)
execute_query(connection, create_participant_table)
execute_query(connection, create_course_table)

Esses comandos criarão as quatro tabelas necessárias para nossas quatro entidades.

Agora, vamos definir os relacionamentos entre elas e criar mais uma tabela para lidar com o relacionamento muitos-para-muitos entre as tabelas participant e course (participante e curso, em inglês, respectivamente). Veja mais detalhes aqui (texto em inglês).

Fazemos exatamente da mesma forma:

alter_participant = """
ALTER TABLE participant
ADD FOREIGN KEY(client)
REFERENCES client(client_id)
ON DELETE SET NULL;
"""

alter_course = """
ALTER TABLE course
ADD FOREIGN KEY(teacher)
REFERENCES teacher(teacher_id)
ON DELETE SET NULL;
"""

alter_course_again = """
ALTER TABLE course
ADD FOREIGN KEY(client)
REFERENCES client(client_id)
ON DELETE SET NULL;
"""

create_takescourse_table = """
CREATE TABLE takes_course (
  participant_id INT,
  course_id INT,
  PRIMARY KEY(participant_id, course_id),
  FOREIGN KEY(participant_id) REFERENCES participant(participant_id) ON DELETE CASCADE,
  FOREIGN KEY(course_id) REFERENCES course(course_id) ON DELETE CASCADE
);
"""

connection = create_db_connection("localhost", "root", pw, db)
execute_query(connection, alter_participant)
execute_query(connection, alter_course)
execute_query(connection, alter_course_again)
execute_query(connection, create_takescourse_table)

Agora, nossas tabelas foram criadas, juntamente com as restrições apropriadas e as relações entre chaves primárias e chaves estrangeiras.

Preenchendo as tabelas

A próxima etapa é adicionar alguns registros às tabelas. Novamente, usaremos a função execute_query para enviar nossos comandos SQL existentes ao servidor. Vamos começar mais uma vez com a tabela Teacher.

pop_teacher = """
INSERT INTO teacher VALUES
(1,  'James', 'Smith', 'ENG', NULL, '1985-04-20', 12345, '+491774553676'),
(2, 'Stefanie',  'Martin',  'FRA', NULL,  '1970-02-17', 23456, '+491234567890'), 
(3, 'Steve', 'Wang',  'MAN', 'ENG', '1990-11-12', 34567, '+447840921333'),
(4, 'Friederike',  'Müller-Rossi', 'DEU', 'ITA', '1987-07-07',  45678, '+492345678901'),
(5, 'Isobel', 'Ivanova', 'RUS', 'ENG', '1963-05-30',  56789, '+491772635467'),
(6, 'Niamh', 'Murphy', 'ENG', 'IRI', '1995-09-08',  67890, '+491231231232');
"""

connection = create_db_connection("localhost", "root", pw, db)
execute_query(connection, pop_teacher)

Funcionou? Podemos verificar no cliente de linha de comando do MySQL:

Agora, vamos preencher as tabelas restantes.

pop_client = """
INSERT INTO client VALUES
(101, 'Big Business Federation', '123 Falschungstraße, 10999 Berlin', 'NGO'),
(102, 'eCommerce GmbH', '27 Ersatz Allee, 10317 Berlin', 'Retail'),
(103, 'AutoMaker AG',  '20 Künstlichstraße, 10023 Berlin', 'Auto'),
(104, 'Banko Bank',  '12 Betrugstraße, 12345 Berlin', 'Banking'),
(105, 'WeMoveIt GmbH', '138 Arglistweg, 10065 Berlin', 'Logistics');
"""

pop_participant = """
INSERT INTO participant VALUES
(101, 'Marina', 'Berg','491635558182', 101),
(102, 'Andrea', 'Duerr', '49159555740', 101),
(103, 'Philipp', 'Probst',  '49155555692', 102),
(104, 'René',  'Brandt',  '4916355546',  102),
(105, 'Susanne', 'Shuster', '49155555779', 102),
(106, 'Christian', 'Schreiner', '49162555375', 101),
(107, 'Harry', 'Kim', '49177555633', 101),
(108, 'Jan', 'Nowak', '49151555824', 101),
(109, 'Pablo', 'Garcia',  '49162555176', 101),
(110, 'Melanie', 'Dreschler', '49151555527', 103),
(111, 'Dieter', 'Durr',  '49178555311', 103),
(112, 'Max', 'Mustermann', '49152555195', 104),
(113, 'Maxine', 'Mustermann', '49177555355', 104),
(114, 'Heiko', 'Fleischer', '49155555581', 105);
"""

pop_course = """
INSERT INTO course VALUES
(12, 'English for Logistics', 'ENG', 'A1', 10, '2020-02-01', TRUE,  1, 105),
(13, 'Beginner English', 'ENG', 'A2', 40, '2019-11-12',  FALSE, 6, 101),
(14, 'Intermediate English', 'ENG', 'B2', 40, '2019-11-12', FALSE, 6, 101),
(15, 'Advanced English', 'ENG', 'C1', 40, '2019-11-12', FALSE, 6, 101),
(16, 'Mandarin für Autoindustrie', 'MAN', 'B1', 15, '2020-01-15', TRUE, 3, 103),
(17, 'Français intermédiaire', 'FRA', 'B1',  18, '2020-04-03', FALSE, 2, 101),
(18, 'Deutsch für Anfänger', 'DEU', 'A2', 8, '2020-02-14', TRUE, 4, 102),
(19, 'Intermediate English', 'ENG', 'B2', 10, '2020-03-29', FALSE, 1, 104),
(20, 'Fortgeschrittenes Russisch', 'RUS', 'C1',  4, '2020-04-08',  FALSE, 5, 103);
"""

pop_takescourse = """
INSERT INTO takes_course VALUES
(101, 15),
(101, 17),
(102, 17),
(103, 18),
(104, 18),
(105, 18),
(106, 13),
(107, 13),
(108, 13),
(109, 14),
(109, 15),
(110, 16),
(110, 20),
(111, 16),
(114, 12),
(112, 19),
(113, 19);
"""

connection = create_db_connection("localhost", "root", pw, db)
execute_query(connection, pop_client)
execute_query(connection, pop_participant)
execute_query(connection, pop_course)
execute_query(connection, pop_takescourse)

Surpreendente! Acabamos de criar um banco de dados completo com relações, restrições e registros no MySQL, usando apenas comandos em Python.

Fizemos isso passo a passo para que o processo fosse compreensível. Mas a esta altura você já deve ter percebido que todos esses comandos podem facilmente ser incluídos em um script em Python e executados em um único comando no terminal.

Lendo os dados

Agora, temos um banco de dados funcional com o qual podemos trabalhar. Como analista de dados, é provável que você entre em contato com bancos de dados existentes nas organizações em que trabalha. Será muito útil saber como extrair dados desses bancos de dados para que possam ser alimentados em seu pipeline de dados em Python. É nisso que vamos trabalhar a seguir.

Para isso, precisaremos de mais uma função, desta vez, usando cursor.fetchall() em vez de cursor.commit() (textos das duas funções em inglês). Com esta função, leremos dados do banco de dados sem fazer nenhuma alteração.

def read_query(connection, query):
    cursor = connection.cursor()
    result = None
    try:
        cursor.execute(query)
        result = cursor.fetchall()
        return result
    except Error as err:
        print(f"Error: '{err}'")

Novamente, vamos implementar isso de uma maneira muito semelhante ao execute_query. Vamos testar com uma consulta simples para ver como funciona.

q1 = """
SELECT *
FROM teacher;
"""

connection = create_db_connection("localhost", "root", pw, db)
results = read_query(connection, q1)

for result in results:
  print(result)

Exatamente o que estávamos esperando. A função também funciona com consultas mais complexas, como esta envolvendo um JOIN entre as tabelas de course e client (curso e cliente, em inglês, respectivamente).

q5 = """
SELECT course.course_id, course.course_name, course.language, client.client_name, client.address
FROM course
JOIN client
ON course.client = client.client_id
WHERE course.in_school = FALSE;
"""

connection = create_db_connection("localhost", "root", pw, db)
results = read_query(connection, q5)

for result in results:
  print(result)

Muito bom.

Para nossos pipelines de dados e fluxos de trabalho em Python, podemos querer obter esses resultados em formatos diferentes para torná-los mais úteis ou prontos para manipulação.

Vamos ver alguns exemplos para entender como podemos fazer isso.

Formatando os resultados em uma lista

#Inicializa uma lista vazia 
from_db = []

# Percorrer os resultados e inseri-los à lista

# Retorna uma lista de tuplas
for result in results:
  result = result
  from_db.append(result)

Formatando o resultado em uma lista de listas

# Retorna uma lista de listas
from_db = []

for result in results:
  result = list(result)
  from_db.append(result)

Formatando o resultado em um DataFrame do Pandas

Para os analistas de dados usando Python, o pandas (texto em inglês) é o nosso velho amigo, belo e confiável. É muito simples converter a saída do nosso banco de dados em um DataFrame. A partir daí, as possibilidades são infinitas!

# Retorna uma lista de listas e cria um DataFrame do Pandas
from_db = []

for result in results:
  result = list(result)
  from_db.append(result)


columns = ["course_id", "course_name", "language", "client_name", "address"]
df = pd.DataFrame(from_db, columns=columns)

Espero que possa ver as possibilidades se desdobrando diante de você. Com apenas algumas linhas de código, podemos extrair facilmente todos os dados que podemos manipular dos bancos de dados relacionais em que eles residem e trazê-los para nossos pipelines de análise de dados de última geração. Isso é algo realmente útil.

Atualizando registros

Quando mantemos um banco de dados, às vezes precisaremos fazer alterações nos registros existentes. Nesta seção, veremos como fazer isso.

Digamos que a ILS seja notificada de que um de seus clientes existentes, a Big Business Federation, está mudando de escritório para 23 Fingiertweg, 14534 Berlin. Nesse caso, o administrador do banco de dados (nós!) precisará fazer algumas alterações.

Felizmente, podemos fazer isso com nossa função execute_query junto com a instrução UPDATE (texto em inglês) do SQL.

update = """
UPDATE client 
SET address = '23 Fingiertweg, 14534 Berlin' 
WHERE client_id = 101;
"""

connection = create_db_connection("localhost", "root", pw, db)
execute_query(connection, update)

Note que a cláusula WHERE é muito importante. Se executarmos esse comando sem a cláusula WHERE, todos os endereços de todos os registros em nossa tabela Client serão atualizados para 23 Fingiertweg. Não é exatamente isso que queremos fazer.

Observe também que usamos "WHERE client_id = 101" na consulta UPDATE. Também seria possível usar "WHERE client_name = 'Big Business Federation'" ou "WHERE address = '123 Falschungstraße, 10999 Berlin'" ou mesmo "WHERE address LIKE '%Falschung%'".

O importante é que a cláusula WHERE nos permite identificar exclusivamente o registro (ou registros) que queremos atualizar.

Apagando registros

Também é possível usar nossa função execute_query para excluir registros, usando DELETE (texto em inglês).

Ao usar SQL com bancos de dados relacionais, precisamos ter cuidado ao usar o operador DELETE. Este não é o Windows. Não há um alerta dizendo "Tem certeza de que deseja excluir isso?" em uma janela de pop-up e não há uma lixeira para a reciclagem. Uma vez que excluímos algo, esse algo realmente se foi.

Dito isso, nós às vezes realmente precisamos apagar coisas. Então, vamos ver isso na prática, apagando um curso da nossa tabela Course.

Antes de mais nada, vamos nos lembrar dos cursos que temos.

Digamos que o curso 20, 'Fortgeschrittenes Russisch' (que é 'Russo avançado' para você e para mim), está chegando ao fim. Então, precisamos removê-lo do nosso banco de dados.

A essa altura, você não ficará surpreso com a forma como fazemos isso - salve o comando SQL como uma string e, em seguida, passe-o para a nossa função execute_query.

delete_course = """
DELETE FROM course 
WHERE course_id = 20;
"""

connection = create_db_connection("localhost", "root", pw, db)
execute_query(connection, delete_course)

Vamos verificar para confirmar que obtivemos o resultado pretendido:

'Russo avançado' se foi, como esperávamos.

Esse comando também funciona para apagar colunas inteiras, usando DROP COLUMN e tabelas inteiras, usando DROP TABLE (ambos os textos de referência em inglês), mas não abordaremos esses comandos neste tutorial.

No entanto, vá em frente e experimente-os - não importa se você excluir uma coluna ou tabela de um banco de dados para uma escola fictícia. É uma boa ideia se familiarizar com esses comandos antes de passar para um ambiente de produção.

E o CRUD?

A essa altura, já podemos concluir as quatro operações principais para o armazenamento de dados persistentes.

Aprendemos a:

• Create (Criar) - bancos de dados, tabelas e registros inteiramente novos
• Read (Ler) - extrair dados de um banco de dados e armazenar em diversos formatos
• Update (Atualizar) - fazer alterações nos registros existentes no banco de dados
• Delete (Apagar) - remover registros que não são mais necessários

Poder fazer essas coisas é incrivelmente útil.

Antes de concluirmos, temos mais uma habilidade muito importante para aprender.

Criando registros a partir de listas

Vimos, ao preencher nossas tabelas, que podemos utilizar o comando SQL INSERT em nossa função execute_query para inserir registros em nosso banco de dados.

Dado que estamos usando Python para manipular nosso banco de dados SQL, seria útil poder obter uma estrutura de dados do Python, tal como uma lista (texto em inglês), e inseri-la diretamente em nosso banco de dados.

Isso pode ser útil quando queremos armazenar logs de atividade do usuário em um aplicativo de mídia social que escrevemos em Python ou entradas de usuários em uma página Wiki que criamos, por exemplo. Existem tantos usos possíveis para isso quantos você possa imaginar.

Esse método também é mais seguro se nosso banco de dados estiver aberto para nossos usuários a qualquer momento, pois ajuda a prevenir ataques de injeção de SQL, que podem danificar ou até destruir (texto em inglês) todo o nosso banco de dados.

Para fazer isso, escreveremos uma função usando o método executemany(), em vez do método execute() (textos de referência em inglês), mais simples, que usamos até agora.

def execute_list_query(connection, sql, val):
    cursor = connection.cursor()
    try:
        cursor.executemany(sql, val)
        connection.commit()
        print("Query successful")
    except Error as err:
        print(f"Error: '{err}'")

Agora temos a função, precisamos definir um comando SQL ('sql') e uma lista contendo os valores que desejamos inserir no banco de dados ('val'). Os valores devem ser armazenados em uma lista de tuplas (textos de referência em inglês), que é uma maneira bastante comum de armazenar dados em Python.

Para adicionar dois novos professores ao banco de dados, podemos escrever um código como este:

sql = '''
    INSERT INTO teacher (teacher_id, first_name, last_name, language_1, language_2, dob, tax_id, phone_no) 
    VALUES (%s, %s, %s, %s, %s, %s, %s, %s)
    '''
    
val = [
    (7, 'Hank', 'Dodson', 'ENG', None, '1991-12-23', 11111, '+491772345678'), 
    (8, 'Sue', 'Perkins', 'MAN', 'ENG', '1976-02-02', 22222, '+491443456432')
]

Observe aqui que no código 'sql' usamos o '%s' como um espaço reservado para nosso valor. A semelhança com o '%s' para uma string em Python é apenas coincidência (e francamente, muito confusa), pois devemos usar '%s' para todos os tipos de dados (strings, inteiros, datas etc) com o MySQL Python Conector.

Você pode ver vários casos no Stackoverflow em que alguém ficou confuso e tentou usar '%d' para inteiros porque estava acostumado a fazer isso em Python. Isso não funcionará aqui - precisamos usar um '%s' para cada coluna para qual queremos adicionar um valor.

A função executemany, então, pega cada tupla em nossa lista 'val' e insere o valor relevante para aquela coluna no lugar do espaço reservado e executa o comando SQL para cada tupla contida na lista.

Isso pode ser feito para várias linhas de dados, desde que sejam formatadas corretamente. Em nosso exemplo, adicionaremos apenas dois novos professores, para fins ilustrativos, mas em princípio podemos adicionar quantos quisermos.

Vamos executar este comando e adicionar os professores ao nosso banco de dados.

connection = create_db_connection("localhost", "root", pw, db)
execute_list_query(connection, sql, val)

Boas-vindas à ILS, Hank e Sue!

Esta é mais uma função muito útil, permitindo-nos pegar dados gerados em nossos scripts e aplicativos Python e inseri-los diretamente em nosso banco de dados.

Conclusão

Abordamos muitas coisas neste tutorial.

Aprendemos como usar o Python e o MySQL Connector para criar um banco de dados totalmente novo no MySQL Server, criar tabelas dentro desse banco de dados, definir as relações entre elas e preenchê-las com dados.

Abordamos como Criar, Ler, Atualizar e Apagar dados em nosso banco de dados.

Vimos como extrair dados de bancos de dados existentes e carregá-los em pandas DataFrames, prontos para análise e trabalho adicional, aproveitando todas as possibilidades oferecidas pela stack PyData (texto em inglês).

Indo na outra direção, também aprendemos como pegar dados gerados por nossos scripts e aplicativos Python e gravá-los em um banco de dados onde eles podem ser armazenados com segurança para recuperação e manipulação posteriores.

Espero que este tutorial tenha ajudado você a ver como podemos usar Python e SQL juntos para poder manipular dados de forma ainda mais eficaz!

Se você quiser ver mais sobre os projetos e trabalhos do autor, visite o site do autor em craigdoesdata.de. Se você tiver algum feedback sobre este tutorial, entre em contato com ele - todos os comentários serão bem recebidos!