Algoritmos de Ordenação e pesquisa

Pesquisa binária

#include <stdio.h>

#define TAMANHO 10

int main () { int vetor[TAMANHO] = {0,1,2,3,4,5,6,7,8,9}; int valor = 8; int encontrado;

int direita, esquerda, meio;

encontrado = 0; /*Falso*/

esquerda = 0; direita = TAMANHO - 1;

while (esquerda <= direita && !encontrado) { meio = (direita + esquerda) / 2; if (vetor[meio] == valor) encontrado = 1; /*Verdadeiro*/ else if (valor < vetor[meio]) direita = meio - 1; else esquerda = meio + 1; }

if (encontrado) { printf ("Valor %d encontrado na posicao %d\n", vetor[meio], meio); } else { printf ("Valor %d não encontrado\n", valor); }

return 0;
}
Algoritmos de Ordenação
Algoritmo de ordenação, em ciência da computação, é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem. Em outras palavras efetua sua ordenação completa ou parcial. O objetivo da ordenação é facilitar a recuperação dos dados de uma lista.
Para este artigo foram escolhidos alguns algoritmos de ordenação para serem estudados que são: Bubble Sort, Selection Sort, Quick Sort e Insertion Sort.
Bubble Sort
Bubble sort é o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.

Figura 2: Esquema de funcionamento do Buble Sort
É verificado se o 3 é maior que 5, por essa condição ser falsa, não há troca.
É verificado se o 5 é maior que 1, por essa condição ser verdadeira, há uma troca.
É verificado se o 5 é maior que 2, por essa condição ser verdadeira, há uma troca.
É verificado se o 5 é maior que 4, por essa condição ser