Imagine o seguinte problema: Dado um vetor com N números, imprima todos eles em ordem crescente, ou seja, do menor para o maior. Por exemplo, se a questão nos desse um vetor com os valores: {5, 3, 10, 2, 7}, a resposta correta do programa seria: 2, 3, 5, 7, 10.
Para resolvermos este problema, utilizaremos uma operação chamada de ordenação. Como você faria isso? Bom, a ideia mais comum e intuitiva é: Primeiro encontrar o menor número do vetor. Depois, encontrar o segundo menor número, e assim sucessivamente, até termos todos os valores ordenados do menor, para o maior.
Uma maneira de ensinar o computador a fazer isso, em c++, é a seguinte:
| #include <iostream> | |
| using namespace std; | |
| const inf = 1000000000, maxn = 10010; | |
| int N, vetor[maxn]; | |
| bool usado[maxn]; // nesse vetor, guardaremos se já usamos ou não cada número do vetor original | |
| int main() | |
| { | |
| cin >> N; // leio o N, ou seja, a quantidade de posições do vetor | |
| for(int i = 1 ; i <= N ; i++) | |
| { | |
| cin >> vetor[i]; // leio cada um dos N números | |
| } | |
| for(int i = 1 ; i <= N ; i++) // para cada número a ser encontrado | |
| { | |
| // declaramos que o menor número é infinito, ou seja, um número bem grande | |
| // veja a linha 6 | |
| int menor = inf; | |
| int id_menor; // posição no vetor do menor número | |
| for(int j = 1 ; j <= N ; j++) // percorro o vetor | |
| { | |
| if(usado[j] == 0 and vetor[j] < menor) // procurando o menor valor "disponÃvel" do vetor | |
| { | |
| menor = vetor[j]; // o menor valor agora é o valor da posição atual do vetor | |
| id_menor = j; // guardo que o Ãndice de tal número é o Ãndice do atual | |
| } | |
| } | |
| usado[id_menor] = 1; // guardo que já usei essa posição | |
| cout << menor << " "; // imprimo o menor valor encontrado | |
| } | |
| return 0; | |
| } |
Neste código, utilizamos dois loops começando em 1 e finalizando em N, um dentro do outro. Por esta razão, o código não é tão rápido. Existe uma função pronta do c++ chamada sort, que ordena os valores em ordem crescente, com uma velocidade ainda maior.
Para podermos utilizar a função, devemos informar a posição inicial que queremos ordenar do vetor, seguida pela primeira posição que não queremos ordenar. Por exemplo, suponha que quiséssemos ordenar da posição 3 até a posição 7 do vetor. Nesse caso, chamamos a função assim: sort(3,8), pois 3 é a primeira posição que queremos ordenar e 8 é a primeira que não queremos.
Para ordenar os valores de um vetor v basta chamar a função da seguinte maneira: sort(v+ini, v+fim), onde ini representa a primeira posição que queremos ordenar crescentemente e fim a primeira que não queremos. No caso da primeira posição ser 0, basta escrever: sort(v, v+fim).
Um código que utiliza a função sort para resolver o nosso problema, é o seguinte:
| #include <iostream> | |
| #include <algorithm> //Biblioteca do sort | |
| using namespace std; | |
| int N, vetor[10010]; | |
| int main() | |
| { | |
| cin >> N; // leio a quantidade de posições do vetor | |
| for(int i = 0 ; i < N ; i++) | |
| { | |
| cin >> vetor[i]; // recebo o valor de cada número | |
| } | |
| sort(vetor, vetor+N); | |
| // ordeno, do menor para o maior, todos os números do vetor | |
| // lembrando que a primeira posição do vetor é a 0 | |
| for(int i = 0 ; i < N ; i++) | |
| { | |
| cout << vetor[i] << " "; // por fim, imprimo cada valor do vetor já ordenado | |
| } | |
| return 0; | |
| } |