Curso Livre de Estruturas de Dados/Métodos de Ordenação

Um método de ordenação no meio da informática, é um algoritmo que é capaz se colocar todos os elementos em uma sequência predefinida de informação. Para tal, esses algoritmos fazem uso de uma função de comparação entre dois elementos que determina qual deles vem primeiro na ordem, para então realizar as operações de ordenação dos elementos. Em geral, se utiliza a ordem numérica crescente (a > b) para dados simples numéricos, e a ordem lexicográfica (popularmente, ordem alfabética) para cadeias de caracteres. A função de ordenação possui grande importância ao lidar com dados compostos, pois ela determina o tipo de ordenação que resultará da aplicação do método, e ela não se limita a comparar dados simples de estruturas compostas (por exemplo, uma função de ordenação pode aplicar funções sobre os dados, ou compará-los com elementos externos).

Algoritmos

Insertion Sort

Visualização gráfica do algoritmo de insertion sort em execução

A ideia do algoritmo é percorrer cada elemento e a cada iteração comparar com os elementos a esquerda (valores já ordenados previamente) enquanto seu valor for valor maior que o atual, caso seu valor for menor o item está ordenado e assim segue para o proximo item, repetindo o processo ate o final.

Complexidade de tempo

Média: O(n²).

Pior Caso: O(n²).

Melhor Caso: O(n).

Implementação

C:

void insertionSort(int array[], int size) {
  for (int i = 1; i < size; i++) {
    int value = array[i];
    int j = i - 1;
    
    while (j >= 0 && array[j] > value) {
      array[j + 1] = array[j];
      j--;
    }
    
    array[j + 1] = value;
  }
}

Java:

public static void insertSort(int[] A){
  for(int i = 1; i < A.length; i++){
    int value = A[i];
    int j = i - 1;
    while(j >= 0 && A[j] > value){
      A[j + 1] = A[j];
      j = j - 1;
    }
    A[j + 1] = value;
  }
}

Python:

def insertion_sort(L):
    for i in xrange(1, len(L)):
        j = i-1 
        key = L[i]
        while j >= 0 and L[j] > key:
           L[j+1] = L[j]
           j -= 1
        L[j+1] = key

PHP:

function insertionSort(&$arr){
	for($i=0;$i<count($arr);$i++){
		$val = $arr[$i];
		$j = $i-1;
		while($j>=0 && $arr[$j] > $val){
			$arr[$j+1] = $arr[$j];
			$j--;
		}
		$arr[$j+1] = $val;
	}
}
 
$arr = array(4,2,1,6,9,3,8,7);
insertionSort($arr);
echo implode(',',$arr);

Bubble Sort

Este algoritmo de ordenação pode-se considerar um dos mais simples e por conta disso, pode-se também considerar um dos métodos mais lerdos, tendo uma complexidade de ordem quadrática, tendo assim O(n²) comparações, no qual n é o número de elementos.

A ideia deste algoritmo consiste-se na ideia de percorrer todos os elementos, onde é feito a comparação das informações de dois em dois, ao encontrar um dos elementos que deve ser trocado, ele faz a troca da posição de um pelo outro e continua a percorrer o vetor caso ainda não tenha chegado ao final.

Complexidade de tempo

Média: O(n²).

Pior Caso: O(n²).

Melhor Caso: O(n).

Implementação

C:

void bubble_sort (int vetor[], int n) {
    int k, j;
    //serve para armazenar temporariamente um dos valores
    int aux;

    //percorre todo o vetor
    for (k = 1; k < n; k++) {
    
        for (j = 0; j < n - 1; j++) {
        
            //verifica se a posição atual é maior que a próxima posição
            if (vetor[j] > vetor[j + 1]) {
            
                //caso seja, deve-se substituir o valor de um pelo outro
                aux          = vetor[j];
                vetor[j]     = vetor[j + 1];
                vetor[j + 1] = aux;
            }
        }
    }
}

Java:

public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
    boolean changed = false;
    do {
        changed = false;
        for (int a = 0; a < comparable.length - 1; a++) {
            if (comparable[a].compareTo(comparable[a + 1]) > 0) {
                E tmp = comparable[a];
                comparable[a] = comparable[a + 1];
                comparable[a + 1] = tmp;
                changed = true;
            }
        }
    } while (changed);
}

Python:

def bubble_sort(seq):
    """Inefficiently sort the mutable sequence (list) in place.
       seq MUST BE A MUTABLE SEQUENCE.
 
       As with list.sort() and random.shuffle this does NOT return 
    """
    changed = True
    while changed:
        changed = False
        for i in xrange(len(seq) - 1):
            if seq[i] > seq[i+1]:
                seq[i], seq[i+1] = seq[i+1], seq[i]
                changed = True
    return seq
 
if __name__ == "__main__":
   """Sample usage and simple test suite"""
 
   from random import shuffle
 
   testset = range(100)
   testcase = testset[:] # make a copy
   shuffle(testcase)
   assert testcase != testset  # we've shuffled it
   bubble_sort(testcase)
   assert testcase == testset  # we've unshuffled it back into a copy

PHP:

function bubbleSort(array $array){
    foreach($array as $i => &$val){
        foreach($array as $k => &$val2){
            if($k <= $i)
                continue;
            if($val > $val2) {
                list($val, $val2) = [$val2, $val];
                break;
            }
        }
    }
    return $array;
}

(Cocktail) Shaker Sort

Cocktail ou Shaker Sort é um algoritmo partindo da variação do Bubble Sort. Ao passo que o Bubble Sort percorre e troca os elementos da estrutura em uma direção por iteração, o Shaker Sort percorre e troca os elementos nas duas direções por iteração.

Complexidade de tempo

Média: O(n²)

Pior Caso: O(n²), ocorre quando a estrutura está ordenada de maneira inversa ao critério utilizado.

Melhor Caso: O(n), ocorre quando a estrutura já está ordenada.

Implementação

// Exemplo de implementação do ShakerSort em arrays de inteiros em C
#include <stdio.h>
#include <stdlib.h>

// função de comparação
int cmp(int a, int b);

// função de troca
void swp(int *a, int *b);

// implementação iterativa do ShakerSort
void sksort(int *arr, int n);

// implementação recursiva do ShakerSort
void sksort_rec(int *arr, int low, int high);

// printa um array de tamanho n
void arrayPrint(int *array, int n);

// lê um array de tamanho n
void arrayScan(int *array, int n);

int main() {
  int *array, n;

  scanf("%d", &n);
  array = (int *)malloc(n * sizeof(array));

  arrayScan(array, n);
  printf("\nNormal:\n");
  arrayPrint(array, n);

  // sksort(array,n);
  sksort_rec(array, 0, n - 1);
  printf("\nOrdenado:\n");
  arrayPrint(array, n);
}

void sksort(int *arr, int n) {
  // flag 'booleana' para marcar se houve alguma troca em uma iteração
  int sort = 1;

  // caso sort continuar como zero o loop quebra, logo o array está ordenado
  for (int i = 0; (i < n - 1 && sort); i++) {
    sort = 0;

    // primeira iteração, da esquerda para a direita,os primeiros e últimos 'i'
    // elementos já estão ordenados
    for (int j = (0 + i); j < (n - 1 - i); j++)
      if (cmp(arr[j + 1], arr[j])) {
        swp(&arr[j], &arr[j + 1]);
        sort = 1;
      }

    // Caso não houve nenhuma troca na primeira iteração, o array está ordenado
    if (!sort)
      break;

    // segunda iteração, da direita para a esqueda,os primeiros e últimos 'i'
    // elementos já estão ordenados
    for (int k = (n - 1 - i); k > (0 + i); k--)
      if (cmp(arr[k], arr[k - 1])) {
        swp(&arr[k], re quando a estrutura já está ordenada.&arr[k - 1]);
        sort = 1;
      }
  }
}

void sksort_rec(int *arr, int low, int high) {
  // Caso base , o array está ordenado
  if (high < low)
    return;

  // flag 'booleana' para marcar se houve alguma troca em uma iteração
  int sort = 0;

  // primeira iteração, da esquerda para a direita
  for (int i = low; i <= high - 1; i++)
    if (cmp(arr[i + 1], arr[i])) {
      swp(&arr[i], &arr[i + 1]);
      sort = 1;
    }

  // Caso não houve nenhuma troca na primeira iteração, o array está ordenado
  if (!sort)
    return;

  // segunda iteração, da direita para a esqueda
  for (int j = high; j >= low + 1; j--)
    if (cmp(arr[j], arr[j - 1])) {
      swp(&arr[j], &arr[j - 1]);
      sort = 1;
    }

  // o último e primeiro elemento estão nos locais corretos
  return (sksort_rec(arr, low + 1, high - 1));
}

int cmp(int a, int b) {
  // critério de comparação
  return (a < b) ? 1 : 0;
}

void swp(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void arrayPrint(int *array, int n) {
  for (int i = 0; i < n; i++)
    printf("%s%d%s", (i == 0) ? ("[") : (""), array[i],
           (i < n - 1) ? (",") : ("]\n"));
}

void arrayScan(int *array, int n) {
  for (int i = 0; i < n; i++)
    scanf("%d", &array[i]);
}

Radix Sort

O radix sort é um algoritmo de ordenação estável e rápido que pode ser usado para ordenar itens que estão identificados por chaves únicas. As chaves são uma cadeia de números ou caracteres, e este método de ordenação ordena estas chaves em qualquer ordem relacionada com a lexicografia.

Dentro da ciência da computação, este algoritmo de ordenação é responsável por ordenar inteiros processando dígitos individuais. Como os inteiros podem representar strings compostas de caracteres (como nomes ou datas) e pontos flutuantes especialmente formatados, o radix sort não é limitado somente a inteiros.

Funcionamento

Em geral as máquinas representam os dados internos como números binários, então, tendo isso em mente, é muito mais conveniente processar os dígitos na forma de inteiros em grupos representados por dígitos binários. O radix sort pode ser dividido em dois tipos de classificações, sendo estes:

• radix sort de dígito menos significativo (LSD);
• radix sort de dígito mais significativo (MSD).

O radix sort LSD começa do dígito menos significativo até o mais significativo, geralmente, ordenando da seguinte forma: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Assim coincide com a ordem normal de representação dos inteiros, como por exemplo a sequência "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Os valores processados pelo algoritmo de ordenação, como se pode perceber, são chamados de “chaves”, que podem existir por si próprias ou associadas a outros dados. As chaves podem ser strings de caracteres ou números.

Já o radix sort MSD funciona de maneira contrária, usando sempre a ordem lexicográfica, que é adequada para ordenação de strings, como palavras, ou representações de inteiros com tamanho fixo. Por exemplo, a sequência "b, c, d, e, f, g, h, i, j, ba" seria ordenada como "b, ba, c, d, e, f, g, h, i, j". Se essa ordenação for usada para ordenar representações de inteiros com tamanho variável, então a representação dos números inteiros de 1 a 10 terá a saída "1, 10, 2, 3, 4, 5, 6, 7, 8, 9".

Implementação

void radixsort(int vet[], int tam) {
    int i;
    int *b;
    int maior = vet[0];
    int exp = 1;

    b = (int *)calloc(tam, sizeof(int));

    for (i = 0; i < tam; i++) {
        if (vet[i] > maior)
    	    maior = vet[i];
    }

    while (maior/exp > 0) {
        int bucket[10] = { 0 };
    	for (i = 0; i < tam; i++)
    	    bucket[(vet[i] / exp) % 10]++;
    	for (i = 1; i < 10; i++)
    	    bucket[i] += bucket[i - 1];
    	for (i = tam - 1; i >= 0; i--)
    	    b[--bucket[(vetor[i] / exp) % 10]] = vet[i];
    	for (i = 0; i < tam; i++)
    	    vet[i] = b[i];
    	exp *= 10;
    }

    free(b);
}

Selection Sort

O Selection Sort Trabalha com a ideia de dois subarrays, um dos elementos já ordenados e outro de elementos desordenados. Dessa forma, itera-se o subarray do elementos desordenados (inicialmente o array inteiro) selecionando o menor elemento e trocando-o com o primeiro(ou último) desse subarray. A cada iteração o limite inferior do subarray dos elementos desordenados e o limite superior do subarray dos ordenados aumenta. Assim, quando o subarray dos elementos desordenados tiver tamanho 1, o array estará ordenado.

Complexidade de Tempo

Média: O(n²)

Pior Caso: O(n²), ocorre quando a estrutura está ordenada de maneira inversa ao critério utilizado.

Melhor Caso: O(n), ocorre quando a estrutura já está ordenada.

Implementação

A implementação pode ser feita dos seguintes modos:

C:

void sel_Sort(int *arr,int n)
{
	//guarda o index do valor mínimo do subarray
	int min_index;
	
	//aumenta o limite do arrays dos elementos ainda não ordenados
	for(int i=0;i<n-1;i++)
	{
		//seta o mínimo como o primeiro elemento do subarray dos desordenados
		min_index = i;
		
		//procura pelo menor valor no subarray
		for(int j=i;j<n;j++)
			if(!cmp(arr[j],arr[min_index]))
				min_index = j;
		
		//troca o menor elemento com o primeiro elemento do subarray dos desordenados	
		swp(&arr[i],&arr[min_index]);
	}
}

int cmp(int a,int b)
{
	//critério de comparação
	if(a>b)return 1;
	else return 0;
}

Java:

public static void sort(int[] nums){
	for(int currentPlace = 0;currentPlace<nums.length-1;currentPlace++){
		int smallest = Integer.MAX_VALUE;
		int smallestAt = currentPlace+1;
		for(int check = currentPlace; check<nums.length;check++){
			if(nums[check]<smallest){
				smallestAt = check;
				smallest = nums[check];
			}
		}
		int temp = nums[currentPlace];
		nums[currentPlace] = nums[smallestAt];
		nums[smallestAt] = temp;
	}
}

Python:

def selection_sort(lst):
    for i, e in enumerate(lst):
        mn = min(range(i,len(lst)), key=lst.__getitem__)
        lst[i], lst[mn] = lst[mn], e
    return lst

PHP:

Interativo:

function selection_sort(&$arr) {
    $n = count($arr);
    for($i = 0; $i < count($arr); $i++) {
        $min = $i;
        for($j = $i + 1; $j < $n; $j++){
            if($arr[$j] < $arr[$min]){
                $min = $j;
            }
        }
        list($arr[$i],$arr[$min]) = array($arr[$min],$arr[$i]);
    }
}

Recursivo:

function selectionsort($arr,$result=array()){
    if(count($arr) == 0){
        return $result;
    }
    $nresult = $result;
    $nresult[] = min($arr);
    unset($arr[array_search(min($arr),$arr)]);
    return selectionsort($arr,$nresult);	
}

Merge Sort

Merge sort exemplo

Descrição

Também conhecido como ordenação por mistura, é um método de ordenação eficiente, operando por divisão e conquista. O Merge Sort tem seu funcionamento baseado em dividir os problemas em várias partes menores, resolve-las de maneira recursiva para então juntar novamente o total resolvido.

Como por exemplo, sejam dois vetores 'a' e 'b', sua junção sendo 'v'. Se a[3] e b[2] o tamanho de 'v' deve ser a soma do tamanho de 'a' e 'b' v[5].

Implementação

A partir do pseudo código de verificação listado a baixo, é possível compreender a imagem de exemplo.

if(a[i]<=b[j]){
    v[k]=a[i];
    a++; v++;
}else{
    v[k]=b[j]
    b++; v++;
}

No caso deste exemplo da foto, a varredura de um vetor acaba antes do outro, pois os dois possuem tamanhos diferentes.

Nesta etapa, os elementos restantes do vetor 'a' serão todos incluídos em ' v', já que 'b' terminou de verificas seus elementos.

Complexidade de Tempo

Para grandes quantidades de informações o Merge pode ser considerado uma melhor opção em relação aos métodos de comparação e troca como bubble, insertion e selection.

Média: O(n Log₂ n).

Pior Caso: O(n Log₂ n).

Melhor Caso: O(n Log₂ n).

Exemplos:

C:

#include <stdio.h>
#include <stdlib.h>
 
void merge (int *a, int n, int m) {
    int i, j, k;
    int *x = malloc(n * sizeof (int));
    for (i = 0, j = m, k = 0; k < n; k++) {
        x[k] = j == n      ? a[i++]
             : i == m      ? a[j++]
             : a[j] < a[i] ? a[j++]
             :               a[i++];
    }
    for (i = 0; i < n; i++) {
        a[i] = x[i];
    }
    free(x);
}
 
void merge_sort (int *a, int n) {
    if (n < 2)
        return;
    int m = n / 2;
    merge_sort(a, m);
    merge_sort(a + m, n - m);
    merge(a, n, m);
}
 
int main () {
    int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
    int n = sizeof a / sizeof a[0];
    int i;
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
    merge_sort(a, n);
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
    return 0;
}

Java:

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
 
public class Merge{
    public static <E extends Comparable<? super E>> List<E> mergeSort(List<E> m){
        if(m.size() <= 1) return m;
 
        int middle = m.size() / 2;
        List<E> left = m.subList(0, middle);
        List<E> right = m.subList(middle, m.size());
 
        right = mergeSort(right);
        left = mergeSort(left);
        List<E> result = merge(left, right);
 
        return result;
    }
 
    public static <E extends Comparable<? super E>> List<E> merge(List<E> left, List<E> right){
        List<E> result = new ArrayList<E>();
        Iterator<E> it1 = left.iterator();
        Iterator<E> it2 = right.iterator();
 
	E x = it1.next();
	E y = it2.next();
        while (true){
            //change the direction of this comparison to change the direction of the sort
            if(x.compareTo(y) <= 0){
		result.add(x);
		if(it1.hasNext()){
		    x = it1.next();
		}else{
		    result.add(y);
		    while(it2.hasNext()){
			result.add(it2.next());
		    }
		    break;
		}
	    }else{
		result.add(y);
		if(it2.hasNext()){
		    y = it2.next();
		}else{
		    result.add(x);
		    while (it1.hasNext()){
			result.add(it1.next());
		    }
		    break;
		}
	    }
        }
        return result;
    }
}

Python:

def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0
    while left_idx < len(left) and right_idx < len(right):
        # change the direction of this comparison to change the direction of the sort
        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1
 
    if left_idx < len(left):
        result.extend(left[left_idx:])
    if right_idx < len(right):
        result.extend(right[right_idx:])
    return result
    
def merge_sort(m):
    if len(m) <= 1:
        return m
 
    middle = len(m) // 2
    left = m[:middle]
    right = m[middle:]
 
    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

PHP:

function mergesort($arr){
	if(count($arr) == 1 ) return $arr;
	$mid = count($arr) / 2;
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
	$left = mergesort($left);
	$right = mergesort($right);
	return merge($left, $right);
}
 
function merge($left, $right){
	$res = array();
	while (count($left) > 0 && count($right) > 0){
		if($left[0] > $right[0]){
			$res[] = $right[0];
			$right = array_slice($right , 1);
		}else{
			$res[] = $left[0];
			$left = array_slice($left, 1);
		}
	}
	while (count($left) > 0){
		$res[] = $left[0];
		$left = array_slice($left, 1);
	}
	while (count($right) > 0){
		$res[] = $right[0];
		$right = array_slice($right, 1);
	}
	return $res;
}
 
$arr = array( 1, 5, 2, 7, 3, 9, 4, 6, 8);
$arr = mergesort($arr);
echo implode(',',$arr);

Quick Sort

Descrição

Assim como o Merge sort, é um algoritmo do paradigma "Dividir e conquistar".No Quick sort, é escolhido elemento como pivô(1) e então o array é particionado(1) em volta dele, em seguida são feitas chamadas recursivas da função para os subarrays à esquerda e direita do pivô.Dessa forma, quando todas as chamadas recursivas encontram um subarray unitário o array está ordenado.

(1) O processo chave para o Quick sort é o processo de particionamento, que consiste em escolher um pivô e colocar todos os elementos menores que o pivô à sua esquerda e os maiores à sua direita.Existem diversos algoritmos de particionamento que escolhem um ou mais pivôs de maneira diferente, alguns são:

• Particionamento de Lomuto: Escolhe o último elemento como pivô, o algoritmo mantém o index i enquanto varre o array com um index j tal que no final os elementos [low, i) são menores que o pivô e os elemementos [i,j] são maiores ou iguais que o pivô.Usando esse esquema, a complexidade de tempo do Quick sort quando o array já está ordenado cai para O(n^2).
• Particionamento Orignal de C.A.R. Hoare: Escolhe o primeiro elemento como pivô, e usa dois índices - um que aponta para o começo do array e outro para o final - que se movem em direção um ao outro até que é detectada uma inversão de elementos, que então são trocados.Quando os índices se encontram, o algoritmo para e retorna o índice final.É mais eficiente que o partionamento de Lomuto, uma vez que faz e média 3 vezes menos trocas que ele, porém também decai para a complexidade de tempo O(n^2) se o array já está ordenado.
• Existem outros particionamentos - como a mediana-de-três, pivô randômico, etc- que produzem resultados melhores em alguns casos específicos.

Implementação

// Exemplo de implementação do Quick Sort em arrays de inteiros em C
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
// função a ser usada para partição
#define HOARE 1

// função de comparação
int cmp(int a, int b);

// função de troca
void swp(int *a, int *b);

// Escolhe um pivô no subarray e o coloca na posição correta
int HoarePartition(int *arr, int low, int high);
int LomutoPartition(int *arr, int low, int high);

/* implementação recursiva do Quick Sort, usando diferentes
 * Algoritmos de partição */
void quickSort(int *arr, int low, int high);

// printa um array de tamanho n
void arrayPrint(int *array, int n);

// lê um array de tamanho n
void arrayScan(int *array, int n);

int main() {
  int *array, n;

  scanf("%d", &n);
  array = (int *)malloc(n * sizeof(array));

  arrayScan(array, n);
  printf("\nNormal:\n");
  arrayPrint(array, n);

  quickSort(array, 0, n - 1);

  printf("\nOrdenado:\n");
  arrayPrint(array, n);
}

int HoarePartition(int *arr, int low, int high) {
  // Pivô como primeiro elemento
  int pivot = arr[low];
  int i = low - 1, j = high + 1;

  while (1) {
    do {
      i++;
    } while (!cmp(arr[i], pivot));

    do {
      j--;
    } while (cmp(arr[j], pivot));

    if (i >= j)
      return j;

    swp(&arr[i], &arr[j]);
  }
}

int LomutoPartition(int *arr, int low, int high) {
  // Pivô como último elemento
  int pivot = arr[high];
  // index do menor elemento
  int i = low - 1, j;

  for (j = low; j < high; j++) {
    if (!cmp(arr[j], pivot)) {
      i++;
      swp(&arr[i], &arr[j]);
    }
  }
  swp(&arr[i + 1], &arr[high]);

  return (i + 1);
}

void quickSort(int *arr, int low, int high) {
  if (low < high) {
#if HOARE
    // pivô como primeiro elementos(partição de Hoare)
    int pi = HoarePartition(arr, low, high);
    quickSort(arr, low, pi);
    quickSort(arr, pi + 1, high);
#else
    // pivô como último elementos(partição de Lomuto)
    int pi = LomutoPartition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
#endif
  }
}

int cmp(int a, int b) {
  // critério de comparação
  if (a >= b)
    return 1;
  else
    return 0;
}

void swp(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void arrayPrint(int *array, int n) {
  for (int i = 0; i < n; i++)
    printf("%s%d%s", (i == 0) ? ("[") : (""), array[i],
           (i < n - 1) ? (",") : ("]\n"));
}

void arrayScan(int *array, int n) {
  for (int i = 0; i < n; i++)
    scanf("%d", &array[i]);
}

Complexidade de tempo:

A complexidade de tempo do Quick Sort nos casos extremos depende da posição do pivô encontrado.

• Média: O(nlog(n))
• Melhor Caso: O(nlog(n)), ocorre quando os pivôs encontrados são os elementos médios dos subarrays.
• Piores Casos: O(n^2) ocorre quando os pivôs encontrados estão nas bordas dos subarray,ou seja, o array já está ordenado(ou quase ordenado), está ordenado de maneira inversa, ou contém muitos elementos repetidos.

Observações e Links úteis:

O Quick sort é preferido em contrapartida ao Merge sort para estruturas contíguas na memória, como arrays.

• A implementação vanilla usando a maioia dos algoritmos de particionamento(como o de Lomuto e o de Hoare) não é estável(não mantém a ordem dos elementos com chaves de ordenação iguais).
• Pode ser modificado a fim de se tornar estável.
• Pela sua natureza recursiva, o Quick sort necessita de espaço auxiliar apenas para chamadas recursivas.

Shell Sort

Descrição

Também chamado de “ordenação por incrementos diminutos”, aumenta o desempenho da ordenação por inserção ao quebrar a lista original em um número menor de sublistas, as quais são ordenadas usando a ordenação por inserção. A principal particularidade do shell sort é como essas sublistas são divididas.

A ideia principal do Shell Sort é a troca de elementos distantes, h-ordenando(1) o array para um valor grande de h, à medida que ele vai diminuindo na proporção definida. Assim, quando h=1, é realizado um Insertion Sort comum, porém necessitando de muito menos trocas.

(1) Um array é dito h-ordenado quando todas as sublistas de i + múltiplos de h está ordenada.

(2) O aspecto mais importante do Shell sort é o uso de diferentes proporções (ou lacunas) na h-ordenação do array. Alguns são:

• Incremento original de D.L. Shell: N/2^k (divisões consecutivas por 2).
• Incremento de Hibbard: 2^k-1 (potências de 2 menos um).
• Incremento de Knuth: (3^k-1)/2 (potências de 3 menos um sobre dois).
• Incremento de Sedgewick: {1, 5, 19, 41, 109, ...} (sequência definida experimentalmente).

Complexidade de tempo

A complexidade de tempo do Shell Sort depende do tipo de lacuna usada na h-ordenação do array, pode variar de O(n*log(n)) à O(n*log^2(n)),porém geramente é considerada perto de O(n) e menor que O(n^2).

Média: O(n^2)

Assim como o Insertion Sort, O Shell Sort é útil quando o conjunto de elementos está parcialmente ordenado.

Implementação

//Exemplo de implementação do Shell Sort em arrays de inteiros em C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//Número máximo de proporções 
#define MAX_GAP 100

//funções de incremento
#define SHELL(n, k) (n)/(int)pow(2.0, (k))
#define HIBBARD(k) (int)pow(2.0, (k)) - 1
#define KNUTH(k) ((int)pow(3.0, (k)) - 1)/2

//função de comparação
int cmp(int a,int b);

//função de troca
void swp(int *a,int *b);

//função de incremento
void gap(int n,int k);

//implementação iterativa do Insertion Sort
void shellsort(int *arr,int n);

//printa um array de tamanho n
void arrayPrint(int *array,int n);

//lê um array de tamanho n
void arrayScan(int *array,int n);

int main()
{
	int *array,n;
	
	scanf("%d",&n);
	array = (int *)	malloc(n*sizeof(array));

	arrayScan(array,n);
	printf("\nNormal:\n");
	arrayPrint(array,n);
	
	shellsort(array,n);
	
	printf("\nOrdenado:\n");
	arrayPrint(array,n);

}

void shellsort(int *arr,int n)
{
	//auxiliar para guardar o elemento a ser inserido
	int aux;
	int i, j, k, gaps[MAX_GAP];
	
	// Gera a sequência de incrementos
	for(i=0; HIBBARD(i+1)<=n; i++)
		gaps[i] = HIBBARD(i+1);
	
	// mostra os incrementos usados
	printf("Incrementos: ");
	for(j=i-1;j>=0;j--)
		printf("%d ", gaps[j]);
	printf("\n");
	
	// h-ordena o array
	for(i-=1; i>=0; i--)
	{
		for(j=gaps[i]; j<n; j++)
		{
			aux = arr[j];
			for(k=j; (k>=gaps[i])&&(!cmp(aux, arr[k-gaps[i]])); k-=gaps[i])
				arr[k] = arr[k-gaps[i]];

			arr[k] = aux;

		}
		arrayPrint(arr,n);
	}
}

int cmp(int a,int b)
{
	//critério de comparação
	if(a>b)return 1;
	else return 0;
}

void swp(int *a,int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void arrayPrint(int *array,int n)
{
	for(int i=0;i<n;i++)
		printf("%s%d%s",(i==0)?("["):(""),array[i],(i<n-1)?(","):("]\n"));
}

void arrayScan(int *array,int n)
{
	for(int i=0;i<n;i++)
		scanf("%d",&array[i]);
}

Heapsort

Descrição

Desenvolvido em 1964 por J.W.J Williams e Robert W. Floyd O Heapsort é um algoritmo de ordenação cujo princípio de funcionamento e o mesmo do algoritmo Selectionsort (Ordenação por Seleção). É caracterizado por utilizar uma heap para organizar informação durante a execução do algoritmo.

Funcionamento

No Heapsort, o primeiro passo é construir uma estrutura de dados chamada heap, o segundo passo é selecionar o maior elemento da heap e alterar pelo elemento que está na última posição do vetor, e em sequência reconstruir a heap com n-1, onde n é o tamanho do vetor. O segundo passo é repetido com n-1 itens restantes, e depois n-2, até que n seja igual a 1.

Complexidade de tempo:

A complexidade de tempo do heapsort nos casos extremos depende da posição do pivô encontrado.

• Média: O(nlog(n)).
• Melhor Caso: O(nlog(n)).
• Pior Caso: O(nlog(n)).

Implementação

C:

// Implementação em C do algoritmo Heapsort

void Heapsort(int x[], int n) {
   int i = n/2;
   int maior;
   int left, right;
   while(n>1) {
      if (i > 0) {
          i--;
          right = x[i];
      } else {
          n--;
          if (n <= 0) return;
          right = x[n];
          x[n] = x[0];
      }
     maior = i;
     left = 2*i+1;
      while (left < n) {
          if ((left + 1 < n)  &&  (x[left + 1] > x[left]))
              left++;
          if (x[left] > right) {
             x[maior] = x[left];
             maior = left;
             left = maior*2+1;
          } else {
             break;
          }
      }
      x[maior] = right;
   }
}

Java:

public static void heapSort(int[] a){
	int count = a.length;
 
	//first place a in max-heap order
	heapify(a, count);
 
	int end = count - 1;
	while(end > 0){
		//swap the root(maximum value) of the heap with the
		//last element of the heap
		int tmp = a[end];
		a[end] = a[0];
		a[0] = tmp;
		//put the heap back in max-heap order
		siftDown(a, 0, end - 1);
		//decrement the size of the heap so that the previous
		//max value will stay in its proper place
		end--;
	}
}
 
public static void heapify(int[] a, int count){
	//start is assigned the index in a of the last parent node
	int start = (count - 2) / 2; //binary heap
 
	while(start >= 0){
		//sift down the node at index start to the proper place
		//such that all nodes below the start index are in heap
		//order
		siftDown(a, start, count - 1);
		start--;
	}
	//after sifting down the root all nodes/elements are in heap order
}
 
public static void siftDown(int[] a, int start, int end){
	//end represents the limit of how far down the heap to sift
	int root = start;
 
	while((root * 2 + 1) <= end){      //While the root has at least one child
		int child = root * 2 + 1;           //root*2+1 points to the left child
		//if the child has a sibling and the child's value is less than its sibling's...
		if(child + 1 <= end && a[child] < a[child + 1])
			child = child + 1;           //... then point to the right child instead
		if(a[root] < a[child]){     //out of max-heap order
			int tmp = a[root];
			a[root] = a[child];
			a[child] = tmp;
			root = child;                //repeat to continue sifting down the child now
		}else
			return;
	}
}

Python:

def heapsort(lst):
  ''' Heapsort. Note: this function sorts in-place (it mutates the list). '''
 
  # in pseudo-code, heapify only called once, so inline it here
  for start in range((len(lst)-2)/2, -1, -1):
    siftdown(lst, start, len(lst)-1)
 
  for end in range(len(lst)-1, 0, -1):
    lst[end], lst[0] = lst[0], lst[end]
    siftdown(lst, 0, end - 1)
  return lst
 
def siftdown(lst, start, end):
  root = start
  while True:
    child = root * 2 + 1
    if child > end: break
    if child + 1 <= end and lst[child] < lst[child + 1]:
      child += 1
    if lst[root] < lst[child]:
      lst[root], lst[child] = lst[child], lst[root]
      root = child
    else:
      break

Javascript:

function heapSort(arr) {
    heapify(arr)
    end = arr.length - 1
    while (end > 0) {
        [arr[end], arr[0]] = [arr[0], arr[end]]
        end--
        siftDown(arr, 0, end)
    }
}
 
function heapify(arr) {
    start = Math.floor(arr.length/2) - 1
 
    while (start >= 0) {
        siftDown(arr, start, arr.length - 1)
        start--
    }
}
 
function siftDown(arr, startPos, endPos) {
    let rootPos = startPos
 
    while (rootPos * 2 + 1 <= endPos) {
        childPos = rootPos * 2 + 1
        if (childPos + 1 <= endPos && arr[childPos] < arr[childPos + 1]) {
            childPos++
        }
        if (arr[rootPos] < arr[childPos]) {
            [arr[rootPos], arr[childPos]] = [arr[childPos], arr[rootPos]]
            rootPos = childPos
        } else {
            return
        }
    }
}
test('rosettacode', () => {
    arr = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8,]
    heapSort(arr)
    expect(arr).toStrictEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
})

Gnome sort

Descrição:

O Gnome sort foi originalmente proposto pelo iraniano Hamid Sarbazi-Azad em 2000 e primeiramente conhecido como “stupid sort” por ser um algoritmo com uma lógica muito simplista. O alemão Dick Grune deu o nome para o aloritmo de Gnome Sort, em homenagem ao duende de jardim alemão.

Este método é baseado na técnica usada pelo duende de jardim alemão onde basicamente ele olha o vaso de flor próximo a ele e o anterior; se eles estão na ordem certa ele avança um vaso, caso contrário ele troca os jarros e volta um passo, com as seguintes condições de parada: se não tem um jarro anterior ao atual, ele avança um passo, se não tem um jarro após o atual, está tudo organizado.

Funcionamento:

É semelhante ao tipo de inserção, na medida em que funciona com um item de cada vez, mas leva o item para o lugar adequado por uma série de trocas, semelhante a um Tipo de bolha. É conceitualmente simples, não requerendo loops aninhados. O tempo médio de execução é O(n2), mas tende a O(n) se a lista estiver inicialmente quase classificada.

O algoritmo encontra o primeiro lugar onde dois elementos adjacentes estão na ordem errada e os troca. Ele tira vantagem do fato de que realizar uma troca pode introduzir um novo par adjacente fora de ordem próximo aos elementos trocados anteriormente. Ele não assume que os elementos à frente da posição atual são classificados, portanto, ele só precisa verificar a posição diretamente anterior aos elementos trocados.

Complexidade:

Pior caso: O(n^2);

Melhor caso: O(n);

Média: O(n^2);

Complexidade do espaço de pior caso: O(1) auxiliar.

Implementação:

C:

void gnome_sort(int *a, int n)
{
  int i=1, j=2, t;
# define swap(i, j) { t = a[i]; a[i] = a[j]; a[j] = t; } 
  while(i < n) {
    if (a[i - 1] > a[i]) {
      swap(i - 1, i);
      if (--i) continue;
    }
    i = j++;
  }
# undef swap
}

Java:

public static void gnomeSort(int[] a)
{
  int i=1;
  int j=2;
 
  while(i < a.length) {
    if ( a[i-1] <= a[i] ) {
      i = j; j++;
    } else {
      int tmp = a[i-1];
      a[i-1] = a[i];
      a[i--] = tmp;
      i = (i==0) ? j++ : i;
    }
  }
}

Python:

>>> def gnomesort(a):
	i,j,size = 1,2,len(a)
	while i < size:
		if a[i-1] <= a[i]:
			i,j = j, j+1
		else:
			a[i-1],a[i] = a[i],a[i-1]
			i -= 1
			if i == 0:
				i,j = j, j+1
	return a
 
>>> gnomesort([3,4,2,5,1,6])
[1, 2, 3, 4, 5, 6]
>>>

PHP:

function gnomeSort($arr){
	$i = 1;
	$j = 2;
	while($i < count($arr)){
		if ($arr[$i-1] <= $arr[$i]){
			$i = $j;
			$j++;
		}else{
			list($arr[$i],$arr[$i-1]) = array($arr[$i-1],$arr[$i]);
			$i--;
			if($i == 0){
				$i = $j;
				$j++;
			}
		}
	}
	return $arr;
}
$arr = array(3,1,6,2,9,4,7,8,5);
echo implode(',',gnomeSort($arr));

Stooge sort

Descrição:

O Stooge Sort é um algoritmo de classificação recursiva. É um algoritmo de classificação ineficiente, mas interessante. Ele divide a matriz em duas partes sobrepostas (2/3 cada). Em seguida, realiza a classificação na primeira parte 2/3 e, em seguida, realiza a classificação na última parte 2/3. Depois disso, a classificação é feita na primeira parte 2/3 para garantir que a matriz seja classificada. A ideia principal é que a classificação da parte sobreposta duas vezes troca os elementos entre as outras duas seções de acordo.

Funcionamento:

O algoritmo deste método se dá da seguinte forma:

1. Se o valor no início for maior do que o valor no final, troque-os.
2. Classifique recursivamente os primeiros 2/3 da matriz.
3. Classifique recursivamente os últimos 2/3 partes do array.
4. Novamente, classifique os primeiros 2/3 da matriz.
5. A matriz é finalmente classificada.

Exemplo:

Entrada: 2 4 5 3 1

Saída: 1 2 3 4 5

• Inicialmente, troque 2 e 1 seguindo a etapa 1 acima.
  • 1 4 5 3 2
• Agora, classifique recursivamente 2/3 dos elementos iniciais.
  • 1 4 5 3 2
  • 1 3 4 5 2
• Em seguida, classifique recursivamente os últimos 2/3 dos elementos.
  • 1 3 4 5 2
  • 1 2 3 4 5
• Novamente, classifique os 2/3 iniciais dos elementos para confirmar se os dados finais estão classificados.
  • 1 2 3 4 5

Complexidade:

Média: O (n ^ log (3) /log(1.5))

Melhor caso: O (n ^ log (3) /log(1.5))

Pior caso: O (n ^ log (3) /log(1.5))

Complexidade de espaço de pior caso: O (n)

Implementação:

C:

#include <stdio.h>
 
#define SWAP(r,s)  do{ t=r; r=s; s=t; } while(0)
 
void StoogeSort(int a[], int i, int j) 
{
   int t;
 
   if (a[j] < a[i]) SWAP(a[i], a[j]);
   if (j - i > 1)
   {
       t = (j - i + 1) / 3;
       StoogeSort(a, i, j - t);
       StoogeSort(a, i + t, j);
       StoogeSort(a, i, j - t);
   }
}
 
int main(int argc, char *argv[])
{
   int nums[] = {1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7};
   int i, n;
 
   n = sizeof(nums)/sizeof(int);
   StoogeSort(nums, 0, n-1);
 
   for(i = 0; i <= n-1; i++)
      printf("%5d", nums[i]);
 
   return 0;
}

Java:

import java.util.Arrays;
 
public class Stooge {
    public static void main(String[] args) {
        int[] nums = {1, 4, 5, 3, -6, 3, 7, 10, -2, -5};
        stoogeSort(nums);
        System.out.println(Arrays.toString(nums));
    }
 
    public static void stoogeSort(int[] L) {
        stoogeSort(L, 0, L.length - 1);
    }
 
    public static void stoogeSort(int[] L, int i, int j) {
        if (L[j] < L[i]) {
            int tmp = L[i];
            L[i] = L[j];
            L[j] = tmp;
        }
        if (j - i > 1) {
            int t = (j - i + 1) / 3;
            stoogeSort(L, i, j - t);
            stoogeSort(L, i + t, j);
            stoogeSort(L, i, j - t);
        }
    }
}

Python:

>>> data = [1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7]
>>> def stoogesort(L, i=0, j=None):
	if j is None:
		j = len(L) - 1
	if L[j] < L[i]:
		L[i], L[j] = L[j], L[i]
	if j - i > 1:
		t = (j - i + 1) // 3
		stoogesort(L, i  , j-t)
		stoogesort(L, i+t, j  )
		stoogesort(L, i  , j-t)
	return L
 
>>> stoogesort(data)
[-6, -5, -3, -2, 1, 3, 3, 4, 5, 5, 7, 7, 7, 9, 10]

PHP:

function stoogeSort(&$arr, $i, $j)
{
	if($arr[$j] < $arr[$i])
	{
		list($arr[$j],$arr[$i]) = array($arr[$i], $arr[$j]);
	}
	if(($j - $i) > 1)
	{
		$t = ($j - $i + 1) / 3;
		stoogesort($arr, $i, $j - $t);
		stoogesort($arr, $i + $t, $j);
		stoogesort($arr, $i, $j - $t);
	}
}