Artigo original: Sorting Algorithms Explained with Examples in JavaScript, Python, Java, and C++
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:
- 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.
- 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 eO(n^2)comparações no pior caso para a maioria das saídas. - 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, comoSelection Sort(ordenação por seleção) ouInsertion Sort(ordenação por inserção), usam técnicas não recursivas. Por fim, alguns algoritmos de ordenação, comoMerge Sort(ordenação por intercalação), usam tanto técnicas recursivas como não recursivas para ordenar uma entrada. - Baseado na estabilidade: Algoritmos de ordenação são considerados
estáveisse 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, os2– usaremos2ae2b, tornando o array[1, 2a, 3, 2b, 4].
Algoritmos de ordenação estáveis manterão a ordem de2ae2b. 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 SorteBubble Sortsão estáveis, enquantoHeap SorteQuick Sortnão são. - 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 locoe ele requer um espaço adicionalO(1)constante para a ordenação. Quando os algoritmos não sãoin loco, uma outra lista é criada durante a ordenação.Insertion sorteQuick sortrealizam a ordenaçãoin 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.
NoMerge 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 :
![[ 3 8 5 1 4 2 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/2.png?raw=true)
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 :
![[ 3 5 8 1 4 2 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/3.png?raw=true)
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 :
![[ 1 3 5 8 4 2 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/4.png?raw=true)
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 :
![[ 1 3 4 5 8 2 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/5.png?raw=true)
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]
![[ 1 2 3 4 5 8 ]](https://github.com/blulion/freecodecamp-resource/blob/master/insertion_sort/6.png?raw=true)
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:
- Encontre o menor elemento no array e troque-o de lugar com o primeiro elemento.
- Encontre o segundo menor elemento e troque com o segundo elemento no array.
- Encontre o terceiro menor elemento e troque com o terceiro elemento no array.
- 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]+" ");
}
}