Estrutura de dados e o Selection Sort | Nerds Attack!

sábado, 29 de setembro de 2012

Estrutura de dados e o Selection Sort

Selection Sort. Técnica de organização de vetores. Apenas uma pequena amostra do que a estrutura de dados é capaz!

Exemplo Selection Sort
Exemplo de como funciona o Selection Sort.

   Olá nerds e, é claro, programadores e desenvolvedores!
   Como descrito na biografia do autor, estou terminando minha formação em ciências da computação. Como trabalho com programação e sei o quanto é difícil as vezes resolvermos alguns problemas que grande parte das vezes, é apenas um pequeno detalhe que nos falta. Aqui no blog postarei assuntos relacionados a programação e desenvolvimento.
Pensando nisso e também pensando em como alguns conceitos e técnicas muito importantes estão muitas vezes sendo esquecidas quando programamos, vou explicar e exemplificar algumas usabilidades que as vezes nos poupam muito tempo e que deixam menos lacunas para gambiarras, muitas vezes, necessárias (atire a primeira pedra quem não as usa!).
   Assim sendo, como já informado no título do post, começarei falando do Selection Sort, que é uma técnica de organização de vetor usado em vetores uni dimensionais. Surge então a pergunta: Como funciona o Selection Sort?!
   O Selection Sort, conforme vocês poderão ver no código comentado, utilizando a linguagem de programação C, irá comparar o primeiro valor do vetor com todos os outros valores. Se for encontrado um valor menor do que o primeiro, é feita a troca da posição dos dois elementos e continua-se varrendo o vetor a partir daquela troca. Se for encontrado outro valor menor do que o já encontrado, é feita outra substituição para a primeira posição e assim sucessivamente, até o fim da primeira varredura do vetor. Para o próximo loop, o segundo valor do vetor será considerado o menor, já que o primeiro valor já foi encontrado e ordenado para sua posição e, esse segundo valor do vetor, passará por todo o processo descrito anteriormente, até que todos os valores tenham sido ordenados. Assim sendo, para resumir, será passado o menor valor do vetor para a primeira posição, após isso, o de segundo menor valor para a segunda posição, e assim é feito sucessivamente até os últimos dois elementos. Esse algoritmo tem complexidade O(n²). Para quem não sabe o que significa isso, falarei em artigos subsequentes.
   Abaixo o código, ordenando um vetor de 10 valores aleatórios.

#include;
#include;

#define MAX 10

main(){
    int i;
    int j;
    int aux;
    int vet[MAX] = {8, 5, 6, 3, 54, 65, 3, 5, 765, 1};

    /*loop para percorrer todos os valores do vetor
    esse loop rodara n-1 vezes ja que o ultimo valor do vetor sera
    comparado na interacao de i na nona posicao do vetor*/
    for(i = 0; i < MAX; i++){

        //variavel auxiliar guardando valor de i comecando do primeiro
        aux = vet[i];

        /*loop para comparacao dos valores considerando sempre
        o valor da variavel i para aux*/
        for(j = i + 1; j <= MAX; j++){

            /*comparacao do valor atual da interacao
            com o menor valor atual*/
            if(vet[j] < aux){

                /*se a comparacao for verdadeira, a menor posicao
                do vetor que esta sendo considerada recebera
                o valor da posicao atual do vetor e o aux recebera
                tambem este valor, para continuar o loop atual de
                interacao de j, fazendo assim que vet[i] sempre
                tenha o menor valor encontrado ate o momento*/
                vet[i] = vet[j];
                vet[j] = aux;
                aux = vet[i];
            }
        }
    }
}

   Bom nerds, e desenvolvedores, aqui termino então meu primeiro post sobre desenvolvimento. Sei que isso é um assunto básico para quem estuda computação. Mas como temos programadores de Google (muito bons por sinal) e também pessoas que as vezes não entendem muito bem o funcionamento dos mesmos, bem como quem está estudando, espero que tenha sido de alguma ajuda. Qualquer dúvida ou sugestão, bem como críticas, que serão muito bem vindas, poderão fazê-las comentando aqui no blog como também no Google Plus.

   Espero vocês na próxima matéria!

Nenhum comentário:

Postar um comentário