Funcionamento do método de ordenação Bolha. (bubble sort)

Ordenação: Parte I

Objetivo: Tornar mais simples, rápida e viável a recuperação de uma determinada informação, num  conjunto grande de informações.

Ordenação por troca: Ordenação por Troca

1.    Bolha (bubble sort)

2.    Quicksort

Bolha: Bubble Sort

Característica do método: algoritmo fácil, pouco eficiente

Idéia básica é percorrer o arquivo sequencialmente várias vezes. Cada passagem consiste em comparar cada elemento no arquivo e seu sucessor (x[i] com x[i+1]) e trocar os dois elementos se não estiverem na ordem certa.

#include "stdio.h"
#define MAX 10  
void bubbleSort(int *vet );
void getVet(int *vet );
void troca(int *a, int *b);
void printVet(int *vet);
int main () {
    int vet[MAX] = {25, 3, 9, 1, 90, 34, 19, 13, 44, 33};

    printf("Nao Ordenado\n");
    printVet(vet);
    bubbleSort(vet);

    printf("\nOrdenado\n");
    printVet(vet);

    return 0;
}

void bubbleSort( int *vet ) {
     int i, j;

     for( i = 0; i < MAX; i++ ) {
          for( j = 1; j < (MAX) - i ; j++ ) {
               if (vet[j-1] > vet[j]) {
                   troca(&vet[j-1], &vet[j]);
               }
          }
     }
}

void printVet( int *vet ) {
     int i;

     for( i = 0; i < MAX; i++ ) {
          printf("%d ", vet[i]);
     }
}

void troca(int *a, int *b){
    int aux;
    aux = *a;
    *a = *b;
    *b = aux;
}

Como o método de ordenação BubbleSort é baseado em troca criei um void chamado troca(int *a, int *b), justamente para demonstrar essa característica desse método de ordenação

Vamos analisar o void bubbleSort( int *vet ), este método é o mais simples

A Eficiência do método da bolha é:

 (n - 1) * (n - 1) = n2 - 2n + 1, que é O(n2)

O número de trocas não é maior que o número de comparações, mas gasta mais tempo na execução.

Para dar continuidade aos posts sobre linguagem C, escolha um dos links abaixo: