Ordenar elementos de um Array em C++

Neste tutorial de nosso curso de C++, vamos aprender como ordenar os elementos de um Array.

Ordenar elementos (sorting)

Ordenar, isto é, colocar elementos (como números) em uma determinada ordem (como crescente ou decrescente, por exemplo), é um dos assuntos mais importantes e estudados em computação, devido sua importância.

Na sua escola ou universidade, a lista de alunos é ordenada em ordem alfabética.
As seções eleitorais onde você vai votar, também usam algum tipo de ordem.
As contas bancárias, também organizam tudo de acordo com números, bem como os números de uma cartela de loteria.

Quando você for um programador profissional em C++, sua empresa vai pedir para você organizar diversas coisas, em algum tipo de ordem, como nomes, salários, identificações, cargos, tamanho ou peso de produtos, etc etc.

Ou seja, é um assunto absurdamente usado, importante demais mesmo, que você vai usar muito mesmo, várias vezes, em sua carreira, e vamos introduzir agora neste tutorial, um pouco do assunto.

Como ordenar um Array em C++

Vamos usar o algoritmo Selection Sort, para ordenar os elementos do Array.
Primeiro, criamos a função gen(), que vai gerar números aleatórios entre 1 até 100.

Vamos criar um array de tamanho size=10 e nome 'num'.
Vamos preencher, em seguida, cada posição desse array com um número aleatório, e depois imprimimos esse array de valores aleatórios. Próximo passo agora é ordenar esse array,

A lógica é a seguinte: pegamos o primeiro elemento do array, e comparamos com todos os outros. Ou seja, comparamos o elemento 0 com o de índice 1, depois o 0 com o de índice 2...até chegar no 0 com o de índice 9.

Se esses outros elementos forem menores que o de índice 0, invertemos os valores desses dois elementos. Pronto, ao término dessa operação, o menor valor do array estará na posição 0.

Agora vamos colocar o segundo menor valor na posição de índice 1.
Para isso, vamos comparar o elemento 1 com o 2, depois o 3, depois o 4...até compararmos o elemento 1 com o elemento 9, o último. Novamente, se esse outro elemento for menor que o de índice 1, invertemos a posição deles.

Ao final desta etapa, o segundo menor valor estará na posição 1. Agora basta fazer isso para os elementos 2, 3,...7 e 8. Na última 'rodada' de comparações, comparamos o elemento 8 com o 9 para decidir qual é maior e qual é menor.

O primeiro looping, usando um laço for, é o que controla o primeiro elemento, e dentro dele vamos comparar com todos os outros índices.
Vamos usar a variável 'prev' para receber o primeiro índice. Ela vai de 0 até 'size-2' (de 0 até 8, ou seja: for(prev=0; prev < size -1 ; prev++) ).

O segundo looping, um laço for aninhado, vai comparar o índice 'prev' com todos os outros elementos do array.
O segundo índice vai ser armazenado na variável 'next', ele começa sempre do valor 'prev+1' (quando o primeiro elemento é 0, ela começa do 1...quando o primeiro elemento é o de índice 1, ele começa no índice 2, etc etc...até o primeiro elemento ser o de índice 8 e ela será o índice 9), até 'size-1' (ou seja, for (next=prev+1 ; next < size ; next++) ).

Dentro desse laço interno, usamos um teste condicional IF pra saber se o segundo elemento é menor que o primeiro, se for, invertemos os valores desses elementos.

Veja como fica nosso código:

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

int gen()
{
    std::random_device rd;
    std::mt19937 gen_numb(rd());
    std::uniform_int_distribution<> dis(1, 100);

    return dis(gen_numb);
}

int main()
{
    int size=10, prev, next, aux;
    int num[size];

    for(aux=0 ; aux<size ; aux++){
        num[aux] = gen();
    }

    cout<<"Array original: "<<endl;
    for(aux=0 ; aux<size ; aux++)
        cout<<num[aux]<<" ";
    cout<<endl;

    // Selection sort algorithm
    for(prev=0 ; prev<size-1 ; prev++)
        for(next=prev+1 ; next<size ; next++){
            aux=num[prev];

            if(num[next]<num[prev]){
                num[prev]=num[next];
                num[next] = aux;
            }
        }

    cout<<"Array Ordenado: "<<endl;
    for(aux=0 ; aux<size ; aux++)
        cout<<num[aux]<<" ";
    cout<<endl;

    return 0;
}

Exercícios de Arrays

01. Faça um algoritmo que ordena os elementos de um array do maior pro menor, ou seja, ordem decrescente.

02. Coloque o código anterior todo dentro de funções: função que preenche o array, função que inverte dois valores, função que faz o selection sort e função que exibe arrays. Use protótipos de função, pra deixar seu código bem profissional.

Solução na apostila