Programação Básica 05 - Ordenação

Aula de Rogério Júnior

Imagine o seguinte problema, de enunciado muito simples: Dado um vetor de n inteiros, todos menores que $10^6$, imprima todos os seus elementos em ordem crescente. A entrada consistirá de duas linhas: a primeira terá um único inteiro: o valor de n, e a segunda terá os n elementos do vetor. Uma primeira ideia, que resolveria o problema seria fazer uma lista dos índices dos números que já imprimimos, depois, percorremos o vetor procurando o menor número que ainda não foi impresso e o imprimimos, repetindo o processo n vezes, até imprimirmos todos os números. Tal ideia é uma adaptação de um algoritmo de ordenação conhecido como Selection Sort. Implementar essa ideia usa apenas comandos que já conhecemos. Para fazermos uma lista eficiente, basta criarmos um vetor de inteiros de nome $lista$. No começo, todos os valores nele salvo serão 0. Toda vez que imprimimos um número salvo na posição $i$ do vetor, fazemos com que $lista[i]$ receba 1. Para isso, é bom saber que toda variável global (declarada fora da main), se não receber um valor logo na declaração, é inicializada com o valor 0, assim como um vetor global será inicializado com todos os seus valores iguais a 0. Assim, verificar se um número $i$ está na lista é verificar se "(lista[i]==1)". Para identificar o menor número do vetor usaremos as variáveis $menor$ e $ind$_$menor$. A primeira começará com um valor muito grande (maior que o valor máximo de um elemento do vetor) e percorreremos todo o vetor, verificando, para cada um de seus elementos, se ele é menor que o número salvo em $menor$ e se seu índice não está na lista dos já impressos. Se for, faremos $menor$ receber seu valor e $ind$_$menor$ receber seu índice, e após percorrermos todos o vetor, imprimiremos o valor salvo em $menor$ e adicionaremos $ind$_$menor$ à lista dos já impressos. Segue a implementação da ideia, para n $\leq$ 1000. Ela usará o comando $define$. Ele tem a gramática: "#define a b", e não precisa de ";". Tal comando iria simplesmente procurar no código, a partir da linha em que foi escrito, todas as vezes que escrevi "a" e trocaria por "b". No código usarei, por exemplo, "#define MAXN 1010" e o programa substituirá todos os "MAXN"que aparecerem pelo número 1010, antes de compilar o programa. É uma questão de estética e facilidade de escrita.

Outra ideia que também geralmente ocorre quando estamos começando a programar e nos deparamos com esse problema é a de ir trocando os números do vetor de lugar à medida em que encontramos um número no vetor que é maior que o que lhe sucede. Tal ideia é um algoritmo conhecido como Bubble Sort. Ou seja, salvaríamos os números da entrada em um vetor de inteiros de nome $vetor$, percorreríamos ele por completo e, toda vez que encontrássemos um índice $i$ tal que $vetor[i]<vetor[i+1]$, trocaríamos os valores de $vetor[i]$ e $vetor[i+1]$, repetindo esse processo até que todo o vetor estivesse ordenado. Feito isso, imprimiríamos seus valores um a um. Para descobrir quando o vetor está ordenado, declaramos um inteiro $ordenado$, que começará com o valor 0. Toda vez que recomeçamos o processo de procurar "elementos invertidos" no vetor, supomos que ele está ordenado e fazemos $ordenado$ receber 1. Se encontramos alguma inversão, além de trocar os elementos, fazemos $ordenado$ receber 0, indicando que ainda há desordenações no vetor. Logo, devemos repetir o processo enquanto $ordenado$ for 0, pois quando tudo estiver em ordem, ele receberá 1 no começo do loop e, como não haverá inversões, manterá este valor até o final. Segue o código:

Os dois algoritmos acima são bons, se o número de elementos a serem ordenados for pequeno. Até agora, vimos apenas como resolver problemas, mas não nos preocupamos com a eficiência dos algoritmos usados, ou seja, quão rápido eles resolvem o problema. A complexidade de um algoritmo é quantas operações ele vai fazer, ou, do que depende, proporcionalmente, essa quantidade de operações. Se o programa tiver uma complexidade muito grande, ele levará Time Limit Exceeded, que significa que o seu programa levou tempo demais para resolver o problema e por isso não foi aceito. Veja, que no primeiro código, do Selection Sort, vamos percorrer o vetor várias vezes. Se o vetor tem n posições, então percorrê-lo todo usa mais ou menos n operações, pois devemos olhar cada casa do vetor. Mais ou menos n significa que este número de operações dependerá unicamente de n, e não mais de nenhuma outra variável, e crescerá proporcionalmente a n. Além disso, o programa não o percorre só uma vez: para cada número que vou imprimir, o programa percorre o vetor inteiro procurando o menor. Assim, vou percorrer o vetor n vezes, ou seja, farei n operações n vezes, logo o programa fará mais ou menos  n² operações. Isso significa que a complexidade do problema é quadrática, ou seja, o número de cálculos que ele fará é proporcional ao quadrado de uma variável. Para representar isso, usamos a notação "O(complexidade)", significando que o número de operações é proporcional à complexidade. No, caso, a complexidade do programa é O(n²).

Vamos agora analisar o segundo código, do Bubble Sort. Repare que, novamente, vou percorrer o todo o vetor e isso tem complexidade O(n). Porém vou repetir essa operação várias vezes, até que cada elemento esteja na sua posição certa de ordenação. Como os elementos "andam" uma posição por repetição e a distância máxima entre eles e a suas posições finais é no máximo n posições, o tamanho do vetor, posso ter que repetir o comando de percorrer o vetor cerca n vezes. Novamente, executo um comando de complexidade O(n) (percorrer todo o vetor) n vezes, o que gera uma complexidade de O(n²).

Para a OBI, devemos considerar, por boa prática, que o computador faz cerca de 1 milhão de operações por segundo e que o tempo limite de execução é  1 segundo. Em outras palavras bem mais simples (e até formalmente erradas mas que facilitam a compreensão), nosso código deve ter complexidade de, no máximo, O($10^6$) . Se o valor de n, for menor que 1000, então nossos algoritmos que rodam em O(n²) irão se encaixar n0 limite. Mas, e se o valor de n for até $10^5$? Precisaremos de um algoritmo mais eficiente.

Existe uma ideia muito importante e imprescindível para qualquer um que queira participar de uma competição de informática: a de dividir para conquistar. A ideia é que para resolver um problema, pode ser mais fácil dividí-lo em casos menores, mais fáceis e resolvê-los um a um, e depois juntá-los para resolver o caso maior, na maioria das vezes com recursão. No caso de ordenação, pense: se eu tiver dois vetores ordenados e decidir juntá-los para fazer um vetor maior, também ordenado, não é bem mais simples? Essa é a ideia de um algoritmo conhecido chamado Merge Sort. Veja: se tenho o $vetor1$ ordenado e o $vetor2$, também ordenado, e quero juntá-los para formar o $vetorzao$, também ordenado, basta que eu percorra os dois vetores, sempre olhando para o começo deles e inserindo em $vetorzao$ o menor dentre o primeiro elemento ainda não inserido de $vetor1$ e de $vetor2$. Segue uma figura que explica como juntar os vetores ordenados {1, 3, 5} e {2, 3, 4} para criarmos um vetor com os 6 elementos ordenados:

 

 

Vamos implementar a ideia! Basta usar um for para percorrer o primeiro vetor e, dentro dele, um while, que irá até o último elemento de $vetor2$ que é menor que o elemento de $vetor1$ que estou olhando, para que, em cada posição do $vetor1$ eu antes adicione todos os elementos de $vetor2$ que são menores que ele, para só então adicioná-lo a $vetorzao$. Feito isso, basta adicionarmos todos os elementos que faltam de $vetor2$. Segue a implementação de um programa que dado o tamanho de um vetor seguido de seus elementos ordenados e o tamanho de outro vetor, também seguido de seus elementos ordenados, imprime o $vetorzao$, que é a junção ordenada dos dois vetores.

Note que a função apenas percorre dois vetores que juntos têm tamanho n, logo a complexidade dela é O(n).

Agora vamos usar a ideia de dividir para conquistar. Se sempre formos separando o vetor ao meio, ordenando as duas metades e depois juntarmos as duas com uma função semelhante à merge, ficará mais fácil pois eventualmente chegaremos a vetores de uma única posição, que já estarão ordenados! Assim, basta fazermos a função recursiva void merge_sort(int ini, int fim){} recursiva que recebe o começo e o fim do intervalo que irá ordenar (inclusive). No seu começo, ela checa se o começo é igual ao fim (intervalo de um único elemento), se for, ela simplesmente retorna, pois o intervalo já estará ordenado. Se não, ela divide o vetor mais ou menos no meio e chama a si mesma para esses novos dois intervalos com o comando "merge_sort(ini, (ini+fim)/2); merge_sort((ini+fim)/2+1, fim);". Feito isso, o vetor em questão estará dividido ao meio em dois vetores ordenados, e realizaremos os comandos da merge para criarmos um novo vetor $aux$ que será a junção dos dois intervalos. Feito isso, faremos o intervalo antigo receber o vetor $aux$. Note que o caso base da recursão são os intervalos de um único elemento, onde a função retorna sem chamar a recursão, e que a árvore recursiva caminha para este caso base, pois sempre vamos dividindo o intervalo ao meio e, criando intervalos cada vez menores, eles eventualmente terão tamanho 1. Segue o código de um problema que recebe um vetor e imprime seus elementos ordenadamente através da função merge_sort.

Para fixar ainda mais a ideia, segue uma animação da Wikipédia que simula o Merge Sort no vetor {6, 5, 3, 1 , 8, 7 , 3, 4}:

 

Vamos analisar, agora, a complexidade da função merge_sort. Observe a seguinte ilustração da chamada do Merge Sort no vetor usado de exemplo acima:

 

Observe que na linha $i$ da árvore de recursão (começando da linha 0) temos que unir $2^i$ vetores ordenados de tamanho $\frac{n}{2^i}$. Como já vimos que juntar dois vetores ordenados tem complexidade O(n) (onde n é o tamanho do vetor final), estaremos repetindo, em cada linha, $2^i$ vezes uma operação de complexidade O($\frac{n}{2^i}$), o que gera, em cada linha uma complexidade igual a O($2^i\cdot\frac{n}{2^i}$) = O(n). Mas quantas linhas a função chamará? Repare que dividiremos o vetor ao meio até que só reste 1 elemento em cada intervalo, logo, sendo m a quantidade de linhas, $\frac{n}{2^m}=1\Leftrightarrow n=2^m\Leftrightarrow\log_2n=\log_2 2^m=m\Leftrightarrow m=\log_2n$. Logo, como são $\log_2n$ linhas, repetiremos $\log_2n$ vezes uma operação de complexidade O(n), o que gera uma complexidade de $O(n\log n)$ (em informática, ao usarmos o termo $\log$, nos referimos a logaritmo na base 2, não na base 10). Agora, se n for $10^5$, a complexidade do programa será $O(10^5\log10^5)=O(10^5\cdot17)\approx O(10^6)$, o que passa no tempo do corretor da OBI.

 

Um pouco de C++

Até agora, no curso, usamos apenas funções da linguagem C. Agora vamos ver um pouco do que o C++ tem a nos oferecer em ordenação. Na biblioteca algorithm temos uma função chamada sort, que utiliza um algoritmo conhecido com Quick Sort com muitas otimizações em sua implementação. Enfim, o importante é saber que ela ordena um vetor qualquer com complexidade média $O(n\log n)$. A função $sort$ recebe três parâmetros: um ponteiro para o primeiro elemento a ser ordenado, um ponteiro para o primeiro elemento que não será ordenado e a função que o $sort$ usará para comparação. Em qualquer vetor, seu nome retorna um ponteiro para o elemento da posição 0 e, se somarmos algum inteiro n ao nome, teremos um ponteiro para o elemento da posição n do vetor. No caso, suponha um vetor de nome $vetor$, e que queremos ordenar os elementos que estão entre as posições 1 e n (de $vetor[1]$ a $vetor[n]$, inclusive). O ponteiro para o primeiro elemento a ser ordenado é "vetor+1" (que aponta para o elemento $vetor[1]$) e o ponteiro para o primeiro elemento que não será ordenado é "vetor+n+1" (que aponta para o elemento $vetor[n+1]$). O terceiro parâmetro da função $sort$ pode ser omitido e, se o for, ela irá comparar o elementos com os operadores "<" e ">". Logo, para ordenar $vetor$, da posição 1 à posição n, usamos o comando "sort(vetor+1, vetor+1+n);". É importante ressaltar também que, como $algorithm$ é uma biblioteca do C++, após sua declaração, precisamos escrever o comando "using namespace std;", para indicar onde está tal biblioteca. Precisamos escrevê-lo antes de usar as funções da $algorithm$, portanto é bom que o façamos no começo do código, logo após as declarações de bibliotecas e $define$'s.

A função de comparação, quando declarada como parâmetro, deve ser do tipo bool (variável que só guarda 1 bit: true ou false) receber duas variáveis do tipo das que serão ordenadas e retornar true se elas estiverem em ordem (o primeiro parâmetro deve vir antes do segundo na ordenação), e false caso contrário (o primeiro parâmetro deve vir depois do segundo, na ordenação). Suponha, por exemplo, que você tem n empresas identificadas com números de 1 a n, e, no vetor $capital$ você guarda os fundos de cada uma. Agora você quer um vetor em que a posições de 1 a n guardem as identificações das empresas, ordenadas da mais rica para a mais pobre pelo valor do fundo de cada uma. A primeira coisa a se fazer é criar o vetor com as n empresas. Crie um vetor de nome $empr$ e use um for para preenchê-lo, da posição 1 à posição n com todos os números de 1 a n ("for(int i=1; i<=n; i++) empr[i]=i;"). Antes da main, crie a função bool compara(int x, int y){}. Ela receberá dois inteiros x e y e retornará true se x deve vir antes de y no vetor ordenado e false, caso contrário. Como as empresas mais ricas devem vir antes, x deverá anteceder y se $capital[x] \geq capital[y]$. Feito tudo isso, para ordenar o vetor $empr$, basta executarmos o comando "sort(empr+1, empr+n+1, compara);". A entrada consistirá de duas linha: a primeira terá um inteiro n, o número de empresas, e a segunda n inteiros: o capital de cada empresa ordenadamente, ou seja, nessa linha, o $i$-ésimo inteiro representa o capital da empresa $i$. A saída deve gerar uma única linha com n inteiros: os índices das empresas em ordem decrescente de capital, separados entre si por um espaço em branco. Segue o código do programa:

Outro detalhe comum em problemas de ordenação é o desempate. Imagine por exemplo um problema que lhe dá n, $1 \leq n \leq 10^5$, o número de alunos que participaram de uma prova e, nas próximas n linhas lhe dá, em cada linha, o nome do aluno, de no máximo 20 caracteres (todos letras minúsculas), um espaço em branco e a sua nota em uma prova, que é um número decimal. A saída que o programa deve gerar terá n linhas, em cada uma o nome de um aluno, ordenados de cima para baixo em ordem decrescente de nota. Ainda mais: em caso de empate de nota, o programa deve imprimir os nomes dos alunos empatados em ordem alfabética.

Vamos definir MAXN como 100100 e MAXL como 30. A primeira coisa a ser feita é declarar um vetor double nota[MAXN], que guardará as notas dos alunos e um vetor de strings char nome[MAXN][MAXL] (uma matriz de char) para guardar os nomes dos alunos. Feito isso, vamos criar um vetor int aluno[MAXN], e colocar nele os números de 1 a n.  Agora basta lembrar da strcmp para criarmos nossa função de comparação. A função bool compara(int x, int y) receberá dois inteiros como parâmetros (os números dos alunos) e deve retornar true se o aluno x vem antes do y e false, caso contrário. A primeira coisa a ser verificada é a nota: deve vir antes o aluno de maior nota, o que faremos com os comandos: "if(nota[x]>nota[y]) return true; if(nota[y]>nota[x]) return false;". Se a função continuar, então não retornou em nenhum dos dois if's, logo nota[x] é igual a nota[y]. Então agora devemos comparar os nomes com a função strcmp.Lembre-se que ela retorna valor negativo se estiverem em ordem certa e positivo se estiverem em ordem errada. Basta olhar se estão na ordem certa, com o comando: "if(strcmp(nome[x], nome[y])<0) return true;", pois se a função passar desse comando e não retornar, então os alunos estão em ordem errada e basta darmos o comando "return false;". Agora podemos chamar o sort e ordenar o vetor $aluno$ e, depois, imprimir o nomes de seus elementos, que já estarão na ordem certa. Segue o código:

Sempre que você precisar ordenar um vetor, ou parte dele, e a complexidade $O(n\log n)$ passar no tempo, use o sort sem medo, ele é simples e eficiente. Isso não significa, entretanto, que você deva esquecer as funções de ordenação que resolveu hoje, pois mesmo que não as use diretamente para ordenar um vetor, as ideias que elas trazem são de extrema importância e ampla aplicação. Problemas de flutuação (troca de elementos consecutivos em uma sequência a fim de que atinjam uma ordem desejada) são geralmente resolvidos com a implementação do Bubble Sort, e a ideia de dividir para conquistar do Merge Sort é muito utilizada em vários problemas.

Um problema conhecido é o do número de inversões de um vetor. Contar o número de inversões em um vetor de tamanho n, indexado de 1 a n, é encontrar a quantidade de pares $(i, j)$, com $1 \leq i < j \leq n$, de modo que o elemento de índice $i$ do vetor é maior que o elemento de índice $j$ do vetor. Ou seja, para cada elemento, devemos contar quantos elementos do vetor são menores que ele e estão à sua frente, somar tudo e imprimir a resposta. Como nos problemas de ordenação, a resposta em O(n²) é trivial, basta que, para cada elemento, percorramos toda a parte do vetor que está à sua direita em busca de elementos menores que ele ou contemos quantas trocas o Bubble Sort leva para ordenar o vetor. Novamente, esta solução está certa mas é muito ineficiente, e podemos fazer esta conta em $O(n\log n)$. Você consegue ver qual das ideias vistas hoje melhor se aplica ao problema? Com certeza é a de dividir para conquistar. A função recursiva que resolve este problema difere em pouquíssimas linhas do Merge Sort. Tente resolver o problema. Se não conseguir, segue a resposta explicada, mas realmente tente fazê-lo sozinho antes de lê-la!

Para aplicar a ideia de dividir para conquistar, basta dividir um intervalo do vetor ao meio e notar que o número de inversões no intervalo todo é a soma do número de inversões em cada metade do intervalo somado ao número de inversões entre números de metades diferentes. Se ambas as metade estiverem ordenadas, o número de inversões entre elementos de intervalos diferentes fica fácil de ser calculada, bastando que vejamos, para cada índice $j$ da metade da direita, o primeiro índice $i$ da metade da esquerda que guarda um elemento maior que o elemento $j$, pois estando a metade ordenada, todos os números à direita de $i$ serão maiores ou iguais ao elemento $i$ e, por consequência, maiores que o elemento $j$.

Agora ficou fácil não? Basta fazermos um Merge Sort que retorna um inteiro: o número de inversões no intervalo a ser ordenado. Em um intervalo de um único elemento não há inversões, e a função retornará 0. Se o intervalo tiver mais que um elemento, declaramos a variável $invers$, que guardará o número de inversões no intervalo. Ela começará com o valor retornado pelo Merge Sort das duas metades do intervalo (soma das inversões em cada metade). Agora, basta somar a ela as inversões entre posições de metades diferentes. Para isso, quando percorrermos as metades, para juntá-las em um vetor maior, e encontramos um índice j da segunda metade com um elemento menor que um elemento de índice i da primeira metade, vamos adicionar a $invers$ o valor de $((ini+fim)/2-i+1)$, pois como a primeira metade vai até o índice $(ini+fim)/2$, esse será o número de elementos à direita do índice $i$ ($(ini+fim)/2-i$), que serão inversões, somando ainda a inversão com o próprio $i$ (por isso o +1). Segue o código para melhor entendimento:

Agora que você já sabe tudo isso, tente fazer os seguintes problemas. Alguns serão só de ordenação, outros usarão as demais ideias trabalhadas hoje. Se tiver alguma dúvida na aula ou dificuldade em algum problema, clique aqui para voltar à página inicial do curso e preencher o formulário para enviar sua dúvida.

Problema 1  - Ordenação por Tamanho

Problema 2 - Fila do Recreio

Problema 3 - Spurs Rocks

Problema 4 - Altura - obs* scanf e printf são métodos rápidos de entrada e saída

Problema 5 - O Elfo das Trevas

Problema 6 - Organizador de Vagões

Problema 7- Camisetas

Problema 8 - Olimpíadas (OBI P1 fase 2 - 2009)

Problema 9 - P-Networks

Problema 10 - Balé (OBI P1 fase 2 - 2011 - um dos problemas mais difíceis da história da P1, simples depois dessa aula!) - Solução alternativa com BIT aqui! (recomendo que vejam somente ao fim do curso, pois é realmente complicado! Uma dica para o começo é não tentar entender o BIT, mas apenas aprender as operações que ele faz).

---

As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.