Ordenação por Seleção em Array Dinâmico em C++

Introdução

Neste laboratório, você aprenderá a realizar a ordenação por seleção (selection sort) para ordenar um array dinâmico não ordenado em C++ usando o algoritmo de ordenação por seleção.

Criar um novo arquivo C++

Primeiramente, crie um novo arquivo C++ chamado main.cpp no diretório ~/project.

touch ~/project/main.cpp

Implementar o Algoritmo de Ordenação por Seleção

O algoritmo de ordenação por seleção (selection sort) funciona selecionando o elemento mínimo e colocando-o no início do array, em seguida, selecionando o próximo elemento mínimo do restante do array e colocando-o no índice 1, e assim por diante, até que o array esteja totalmente ordenado. Veja como implementar o algoritmo de ordenação por seleção em C++:

#include <iostream>
using namespace std;

// função para trocar a posição de dois elementos
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// função para realizar o algoritmo de ordenação por seleção
void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // Para ordenar em ordem decrescente, mude > para < nesta linha.
      // Seleciona o elemento mínimo em cada loop.
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // coloca o mínimo na posição correta
    swap(&array[min_idx], &array[step]);
  }
}

Neste bloco de código, definimos uma função swap() para trocar a posição de dois elementos no array e uma função selectionSort() para realizar o algoritmo de ordenação por seleção no array.

Inserir o Array

Nesta etapa, você irá inserir o array dinâmico que precisa ser ordenado. Você pode fazer isso solicitando ao usuário que insira os elementos do array um por um:

// código do driver
int main() {
  int size;
  cout<<"Enter the size of the array: ";
  cin>>size; //insere o tamanho do array
  int* data = new int[size]; //Declara dinamicamente o array

  // Insere os elementos do array um por um
  for(int i = 0; i < size; i++) {
    cout<<"Enter element "<<i+1<<" : ";
    cin>>data[i];
  }

Executar a Ordenação por Seleção

Agora que temos o array não ordenado, podemos realizar o algoritmo de ordenação por seleção nele usando a função selectionSort() que definimos anteriormente. Veja como fazer isso:

  // Realiza a ordenação por seleção
  selectionSort(data, size);

Exibir o Array Ordenado

Finalmente, exibiremos o array ordenado no console usando um loop em uma função chamada printArray(). Veja como fazer isso:

  // Exibe o array ordenado
  cout << "\nSorted array: ";
  for (int i = 0; i < size; i++)
    cout << data[i] << " ";

  // Libera a memória usada pelo array dinâmico
  delete[] data;
  return 0;
}

Compilar e Executar o Código

Para compilar e executar o código, abra o terminal e navegue até a pasta onde o seu arquivo main.cpp está armazenado. Em seguida, execute os seguintes comandos:

g++ main.cpp -o main
./main

O array ordenado deve ser exibido no console.

Resumo

Neste laboratório, você aprendeu como usar o algoritmo de ordenação por seleção (selection sort) para ordenar um array dinâmico não ordenado em C++. Para fazer isso, você precisou inserir o array, implementar o algoritmo de ordenação por seleção, realizar a ordenação, exibir o array ordenado e, em seguida, compilar e executar o código no terminal. Com essas habilidades, você será capaz de ordenar arrays de qualquer tamanho usando a ordenação por seleção.