Elementos de Apoio Pesquisa e Ordenação 2011

Transcrição

ICC - Métodos de
Ordenação e Pesquisa
ISTEC 2011
PDF gerado usando o pacote de ferramentas em código aberto mwlib. Veja http://code.pediapress.com/ para mais informações.
PDF generated at: Mon, 28 Nov 2011 19:16:50 UTC
Conteúdo
Páginas
Algoritmo de ordenação
1
Bubble sort
2
Insertion sort
16
Selection sort
22
Shell sort
28
Quicksort
32
Algoritmo de busca
50
Busca linear
51
Pesquisa binária
54
Referências
Fontes e Editores da Página
61
Fontes, Licenças e Editores da Imagem
62
Licenças das páginas
Licença
63
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. As ordens mais
usadas são a numérica e a lexicográfica.
Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo
mais eficiente.
Métodos de ordenação de vetores
Métodos simples
•
•
•
•
Insertion sort
Selection sort
Bubble sort
Comb sort
Métodos sofisticados
•
•
•
•
•
•
•
•
•
•
Quick sort
Merge sort
Heapsort
Shell sort
Radix sort
Gnome sort
Count sort
Bucket sort
Cocktail sort
Timsort
Métodos de pesquisa
• Pesquisa binária
• Busca linear
• BogoBusca
Galeria
1
2
Insertion Sort
Selection Sort
Bubble Sort
Bubble sort
Bubble sort
classe
estrutura de dados
Array, Listas ligadas
complexidade pior caso
complexidade caso médio
complexidade melhor caso
complexidade de espaços pior
caso
auxiliar
Algoritmos
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais
simples. A ideia é percorrer o vector diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento
da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio
nível, e disso vem o nome do algoritmo.
No melhor caso, o algoritmo executa
No pior caso, são feitas
operações relevantes, onde n representa o número de elementos do vector.
operações. A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é
recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.
O algoritmo pode ser descrito em pseudo-código como segue abaixo. V é um VECTOR de elementos que podem ser
comparados e n é o tamanho desse vector.
• Abaixo há um algoritmo Bubble Sort onde a implementação é a mais simples possível, ou seja, é a versão original
do Bubble Sort sem o aprimoramento da variável "houve troca".
void bubblesort(int *v, int n, unsigned long long int *cont,unsigned long long int *cont2) { int i, j, aux;
for(i=0; i<n; i++){
for(j=0; j<n-1; j++){
if(v[j]>v[j+1]) {
aux=v[j];
v[j]=v[j+1];
v[j+1]=aux;
Bubble sort
3
}
}
}
}
• Observação: Neste algoritmo tanto o melhor caso, como o pior caso tem ordem "n²", porque em ambos os casos
os ciclos são sempre realizados até ao fim, mesmo quando os elementos já estão ordenados.
BUBBLESORT (V[], n)
1
houveTroca <- verdade
# uma variável de controle
2
enquanto houveTroca for verdade faça:
3
houveTroca <- falso
4
para i de 1 até n-1 faça:
5
se V[i] vem depois de V[i + 1]
6
então troque V[i] e V[i + 1] de lugar e
7
houveTroca <- verdade
Para j de 1 até (i - 1) Passo 1
Se a[j - 1] > a[j] Então
aux <- a[j]
a[j] <- a[j - 1]
a[j - 1] <- aux
FimSe
</source>
Assembly
/*void bubble_as2 (int *x, int n);*/
.globl bubble_as2
/* assembler utilizado gas (x86 - Linux) */
bubble_as2:
pushl %ebp
movl %esp, %ebp
movl 12(%ebp), %eax /* tamanho -> %eax */
movl 8(%ebp), %ecx /* início do vetor -> %ecx */
movl $4, %ebx
dec %eax
mul %ebx
addl %eax, %ecx /* %ecx aponta p/ o último do elemento do vetor */
pushl %ecx
_bubble_as2_l1:
movl $0, %edx
movl 8(%ebp), %ebx
movl %ebx, %eax
addl $4, %eax
_bubble_as2_l2:
cmp %eax, %ecx
Bubble sort
jl _bubble_as2_l1_end
movl (%ebx), %ecx
cmp (%eax), %ecx
jl _bubble_as2_l2_end
/* troca */
movl (%eax), %edx
movl %edx, (%ebx)
movl %ecx, (%eax)
movl $1, %edx
_bubble_as2_l2_end:
movl %eax, %ebx
addl $4, %eax
movl (%esp), %ecx
jmp _bubble_as2_l2
_bubble_as2_l1_end:
cmp $0, %edx
je _bubble_as2_fim
popl %ecx
subl $4, %ecx
pushl %ecx
jmp _bubble_as2_l1
_bubble_as2_fim:
leave
retts
C
#include <stdbool.h>
inline void troca(int* a, int* b)
{
int aux = *a;
*a = *b;
*b = aux;
}
void bubbleSort (int *primeiro, int *ultimo)
{
bool naoTrocou;
int *posAtual;
for (; ultimo > primeiro; --ultimo)
{
naoTrocou = true;
for (posAtual = primeiro; posAtual < ultimo; ++posAtual)
{
if (*posAtual > *(posAtual+1))
{
troca (posAtual, posAtual+1);
4
Bubble sort
5
naoTrocou = false;
}
}
if (naoTrocou) return;
}
}
Java
public static void bubbleSort (int [] vetor){
boolean houveTroca = true;
while (houveTroca == true) {
houveTroca = false;
for (int i = 0; i < (vetor.length)-1; i++){
if (vetor[i] > vetor[i+1]){
int variavelAuxiliar = vetor[i+1];
vetor[i+1] = vetor[i];
vetor[i] = variavelAuxiliar;
houveTroca = true;
}
}
}
}
ActionScript 3
function bubbleSort (v:Array):void
{
for (var i:int = v.length; i >= 1; i--)
{
for (var j:int = 1; j < i; j++)
{
if (v[j - 1] > v[j])
{
var aux:int = v[j];
v[j] = v[j - 1];
v[j - 1] = aux;
}
}
}
}
Bubble sort
6
C
Usando "do while".
void swapbubble( int v[], int i)
{
int aux=0;
aux=v[i];
v[i] = v[i+1];
v[i+1] = aux;
}
void bubble(int v[], int qtd)
{
int i;
int trocou;
do
{
qtd--;
trocou = 0;
for(i = 0; i < qtd; i++)
{
if(v[i] > v[i + 1])
{
swapbubble(v, i);
trocou = 1;
}
}
}while(trocou);
}
Método de ordenação Bolha com ordenação de strings.
void bubble(int v[], int qtd)
//UTILIZA BIBLIOTECA string.h
{
int i;
int trocou;
char aux;
do
{
qtd--;
trocou = 0;
Bubble sort
7
for(i = 0; i < qtd; i++)
if(strcasecmp(v[i],v[i + 1])>0)
{
/*o ideal seria fazer uma função troca aqui*/
strcpy(aux, v[i]);
strcpy(v[i], v[i + 1]);
strcpy(v[i + 1], aux);
trocou = 1;
}
}while(trocou==1);
}
C++
#include "Bubblesort.h"
void bubblesort(vetor &a, tamanho n)
{
for(int j= n-1; j>0; j--){
for(int i=0;i<j;i++){
if(a[i+1] < a[i]){
swap(a[i+1], a[i]);
}
}
}
}
for (int i = vetor.length - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (vetor[i] < vetor[j])
{
int swap
= vetor[i];
vetor[i]
= vetor[j];
vetor[j] = swap;
}
}
}
ML
http://pt.wikipedia.org/skins-1.5/common/images/button_hr.png
fun fix ( f,x) =
let val fx = f(x)
in
if x = fx then x
else fix(f,fx)
end;
Bubble sort
fun bubble ([]) = []
| bubble([a]) = [a]
| bubble(a::b::x) =
if a <= b then a::bubble(b::x)
else b::bubble(a::x);
fun bubblesort( lista ) = fix (bubble,lista);
Pascal
O código a seguir ilustra o algoritmo, para ordenar n números inteiros:
program ordenacao;
uses crt;
const
n = 20;
var
vet:array[1..n]of integer;
i,j,aux: integer;
begin
randomize;
{Preenche o array com valores aleatórios}
for i := 1 to n do
vet[i] := random(100);
{Ordena o array}
for i := n downto 2 do
for j := 1 to i-1 do
if vet[j] > vet[j+1] then
begin
aux := vet[j];
vet[j] := vet[j+1];
vet[j+1] := aux;
end;
end.
Implementação do Algoritmo Bolha com FLag
program BolhacomFLag;
uses wincrt;
const
n=10;
var
vet:array[1..n] of integer;
i,aux:integer;
houveTroca:boolean;
begin
i:=0;
houveTroca:=true;
randomize;
8
Bubble sort
for i:=1 to n do
vet[i]:=random(100);
for i:=1 to n do
writeln(vet[i]);
repeat
houveTroca:=false;
for i:=1 to n-1 do
if ( vet[i] > vet[i+1]) then
begin
aux := vet[i];
vet[i]:= vet[i+1];
vet[i+1]:= aux;
houveTroca:=true;
end;
until (houveTroca = false);
writeln('Escrevendo Vetor Ordenado');
for i:=1 to n do
writeln(vet[i]);
{by X}
end.
Método Bolha com StringList
var
a,b,ind: Integer;
aux: String;
sListaEx: TStringList;
begin
sListaEx.add(String);
for a := 0 to sListaEx.count -1 do
begin
for b := 0 to sListaEx.count -1 do
begin
if sListaEx[a] < sListaEx[b] then
begin
aux
:= sListaEx[a];
sListaEx[a] := sListaEx[b];
sListaEx[b] := aux;
end;
end;
end;
sListaEx := TStringList.Create;
end;
9
Bubble sort
Python
def bubblesort(l):
for passesLeft in range(len(l)-1, 0, -1):
for index in range(passesLeft):
if l[index] < l[index + 1]:
l[index], l[index + 1] = l[index + 1], l[index]
return l
def bubbleSort(L,n):
flag = True
while flag:
flag = False
for i in range(n-1):
if L[i] > L[i+1]:
L[i],L[i+1] = L[i+1],L[i]
flag = True
Ruby
def bubble_sort(list)
swapped = true
while swapped
swapped = false
(list.size - 1).times do |i|
if list[i] > list[i+1]
list[i], list[i+1] = list[i+1], list[i]
swapped = true
end
end
end
list
end
Perl
sub swap {
@_[0, 1] = @_[1, 0];
}
sub bubble_sort {
for ($i=$|; $i < $#_; ++$i) {
for ($j=$|; $j < $#_; ++$j) {
($_[$j] > $ _[$j+1]) and swap($_[$j], $_[$j+1]);
}
}
}
10
Bubble sort
11
C#
private void BubbleSort(int[] vetor)
{
//Ordem Decrescente
for (int i = vetor.Length - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (vetor[i] > vetor[j])
{
int swap
= vetor[i];
vetor[i]
= vetor[j];
vetor[j] = swap;
}
}
}
}
Console.WriteLine("O vetor está Ordenado");
PHP
<?php
/*
Esta função troca o valor de duas variáveis entre si.
Opcional. Pode ser embutido na bolha
*/
function swap(&$valor_1, &$valor_2) {
list($valor_1, $valor_2) = array($valor_2, $valor_1);
}
/* Array de teste */
$arrToSort = array(1, 4, 7, 3, 8, 9, 10);
$length = count($arrToSort);
/* a BOLHA! ;-) */
for ($i = 0; $i < $length; $i++) {
for ($j = $i; $j < count($arrToSort); $j++) {
if ($arrToSort[$i] > $arrToSort[$j]) {
swap($arrToSort[$i], $arrToSort[$j]);
}
}
}
/* Opcional. Exibe o array de um jeito que nós podemos entender! =D */
print_r($arrToSort);
?>
Bubble sort
12
<?php
function BubbleSort( &$items ) {
$temp = "";
$size = count( $items );
for( $i = 1; $i < $size; $i++ ) {
for( $j = 0; $j < $size - $i; $j++ ) {
if( $items[$j+1] < $items[$j] ) {
$temp = $items[$j];
$items[$j] = $items[$j+1];
$items[$j+1] = $temp;
}
}
}
}
$items = array(31, 41, 59, 26, 41, 58);
var_dump($items );//Imprimindo Array Atual
BubbleSort( $items );//Ordenando o Array
var_dump($items );//Imprimindo Array Ordenado
?>
Shell script
#! /bin/bash
vetor=( 2 1 3 4 5 )
bubble_sort(){
aux=0
for (( a = 0 ; a < ${#vetor[*]} ; a++ ))
do
for (( b = 0 ; b < ${#vetor[*]} ; b++ ))
do
[[ ${vetor[$b]} -lt ${vetor[$a]} ]] && { aux=${vetor[$b]} ; vetor[$b]=${vetor[$a]} ; vetor[$a]=$aux ; }
done
done
}
bubble_sort
echo "${vetor[*]}"
Bubble sort
13
Lua
function bubbleSort(v)
--Lembrando que vetores no lua começam no "1" e não no "0"
for i=#v, 1, -1 do
for j=1, i-1 do -- Lembrando que se o "passo" do loop for for 1 não precisa coloca-lo
if(v[j]>v[j+1])then
v[j],v[j+1] = v[j+1],v[j]
end
end
end
end
Matlab
for(i = 1:n-1)
for(j = 1:n-i)
if(x(j) > x(j + 1))
aux = x(j);
x(j) = x(j + 1);
x(j + 1) = aux;
end
end
end
R
bubblesort = function(x){
n = length(x)
for(i in 1:(n-1)){
for(j in 1:(n-i)){
if(x[j] > x[j+1]){
aux = x[j]
x[j] = x[j+1]
x[j+1] = aux
}
}
}
return(x)
}
ASP
<%
Dim links(5)
links(0) = 1
links(1) = 3
links(2) = 5
links(3) = 2
links(4) = 4
Bubble sort
'Esta função troca o valor de duas variáveis entre si.
'Opcional. Pode ser embutido na bolha
function swap(i, j)
valor_1_antigo = links(i)
valor_2_antigo = links(j)
links(i) = valor_2_antigo
links(j) = valor_1_antigo
end Function
'A BOLHA
for i = 0 to UBound(links)
for j = i+1 to UBound(links)
if (links(i) > links(j)) then
call swap(i, j) 'Passa o ponteiro para a funcao swap
end if
next
next
'Resultado
for i = 0 to UBound(links)
Response.write links(i) & " "
next
%>
JavaScript
<script>
var i=0;
var j=0;
var vetor=new Array(5,2,1,3,4);
for(i=vetor.length-1;i>=0;i--)
{
for(j=0;j<i;j++)
{
if(vetor[i]<vetor[j])
{
var troca=vetor[i];
vetor[i]=vetor[j];
vetor[j]=troca;
}
}
}
</script>
14
Bubble sort
15
Visual Basic
Private
Dim
Dim
Dim
Sub sbOrdena(aNumbers() As Integer)
iNumber1 As Integer
iNumber2 As Integer
iNumberAux As Integer
For iNumber1 = 0 To UBound(aNumbers)
For iNumber2 = 0 To UBound(aNumbers) - 1
If aNumbers(iNumber2) > aNumbers(iNumber2 + 1) Then
iNumberAux = aNumbers(iNumber2)
aNumbers(iNumber2) = aNumbers(iNumber2 + 1)
aNumbers(iNumber2 + 1) = iNumberAux
End If
Next iNumber2
Next iNumber1
End Sub
Fluxograma
Bubble sort
16
Ligações externas
•
•
•
•
•
•
•
•
•
C2.com [1]
CS [2]
Veja também um algoritmo bubble sort oscilante em C [3]
Bubble Código de classificação [4]
[5]
Simulador online do Bublesort [6]
Exemplo de Bubble-Sort com "Dança" [7]
Sou Computeiro [8]
[9]
Referências
[1]
[2]
[3]
[4]
[5]
[6]
http:/ / c2. com/ cgi/ wiki?BubbleSort
http:/ / www. cs. ubc. ca/ spider/ harrison/ Java/ sorting-demo. html
http:/ / leocapetta. blogspot. com/ 2010/ 09/ bubble-sort-em-c. html
http:/ / www. algorithm-code. com/ wiki/ Bubble_sort
http:/ / en. wikipedia. org/ wiki/ Sorting_algorithm#Insertion_sort
http:/ / wikipedia. artudi. org/ Bubble%20Sort. php
[7] http:/ / www. patternizando. com. br/ 2011/ 04/ algoritmo-bubble-sort-demonstrado-com-danca/
[8] http:/ / soucomputeiro. blogspot. com
[9] http:/ / www. dei. isep. ipp. pt/ ~i960231/ ei/ bubblesort. htm
Insertion sort
Insertion sort
classe
estrutura de dados
caso
estabilidade
total,
estável
Algoritmos
auxiliar
Insertion sort
17
Insertion sort, ou ordenação por inserção, é um simples algoritmo de
ordenação, eficiente quando aplicado a um pequeno número de
elementos. Em termos gerais, ele percorre um vetor de elementos da
esquerda para a direita e à medida que avança vai deixando os
elementos mais à esquerda ordenados. O algoritmo de inserção
funciona da mesma maneira com que muitas pessoas ordenam cartas
em um jogo de baralho como o pôquer.[1]
Características
• Menor número de trocas e comparações entre os algoritmos de
ordenação O(n) quando o vetor está ordenado.
Exemplo de funcionamento do insertion sort em
uma lista de inteiros aleatórios
• Pior caso O(n²)
Implementações
Pseudocódigo
Segue uma versão simples do pseudocódigo do algoritmo, com vetores começando em zero:
FUNCAO INSERTION_SORT (A[], tamanho)
VARIAVEIS
var i, j, elemento;
PARA j <- 0 ATÉ tamanho - 1 FAÇA
elemento <- A[j];
i <- j – 1;
ENQUANTO ((i >= 0) E (A[i] > elemento)) FAÇA
A[i+1] <- A[i]
A[i] <- elemento
i <- i–1
FIM_ENQUANTO
FIM_PARA
FIM
xHarbour
Function SortInsertion( aList )
Local nLoop1 := 0
Local nLoop2 := 0
Local nIndex := 0
For nLoop1 := 1 To Len( aList )
nLoop2 := nLoop1
Insertion sort
18
nIndex := aList[ nLoop1 ]
While nLoop2 > 1 .And. aList[ nLoop2 - 1 ] > nIndex
aList[ nLoop2 ] := aList[ nLoop2 - 1 ]
nLoop2 -EndDo
aList[ nLoop2 ] := nIndex
Next
Return NIL
Java
public static int[] insertionSort(int[] array)
{
for (int i = 1; i < array.length; i++)
{
int a = array[i];
int j;
for (j = i - 1; j >= 0 && array[j] > a; j--)
{
array[j + 1] = array[j];
array[j] = a;
}
}
return array;
}
Visual Basic
Private Sub Ordenacao(Numeros() As Integer)
Dim i As Long
Dim j As Long
Dim iMin As Long
Dim iMax As Long
Dim varSwap As Variant
iMin = LBound(Numeros) + 1
iMax = UBound(Numeros)
For i = iMin To iMax
varSwap = Numeros(i)
For j = i To iMin Step -1
If varSwap < Numeros(j - 1) Then Numeros(j) = Numeros(j - 1) Else Exit For
Next j
Numeros(j) = varSwap
Next i
End Sub
'Code By Kalandar
Insertion sort
19
C
void insertionSort(int v[], int tam)
{
int i, j;
for(i = 1; i < tam; i++){
j = i;
while(V[j] < V[j - 1]) {
int aux = V[j];
V[j] = V[j - 1];
V[j - 1] = aux;
j--;
if(j == 0)break;
}
}
return;
}
Pascal
procedure InsertionSort(var vet:array[1..20] of integer; n:integer; var
NC, NT: integer);
var j,o,aux:integer; {variaveis auxiliares}
begin
for j:=2 to n do
begin
o:=j-1;
while (a[j]<a[o]) and (i>1) do
begin
inc(NT);
aux:=a[j];
a[j]:=a[o];
a[o]:=aux;
j:=i-1;
o:=o-1;
inc(NC);
end;
end;
end;
Insertion sort
Python
def inssort(l):
for i in range(1, len(l)):
key = l[i]
j = i
while j > 0 and l[j - 1] > key:
l[j] = l[j - 1]
j -= 1
l[j] = key
Haskell
import Data.List (insert)
insertsort :: Ord a => [a] -> [a]
insertsort = foldr insert []
C#
static int[] ordernar(int[] A)
{
int i, j, index;
for (i = 1; i < A.Length; i++)
{
index = A[i];
j = i;
while ((j > 0) && (A[j - 1] > index))
{
A[j] = A[j - 1];
j = j - 1;
}
A[j] = index;
}
return A;
}
PHP
ini_set('max_execution_time','600');
function microtime_float()
{
list($usec, $sec) = explode(" ", microtime());
return ((float)$usec + (float)$sec);
}
for ($gera = 0; $gera <=20000; $gera++){
$array[$gera] = rand(0, 10000);
20
Insertion sort
}
$time_start = microtime_float();
for($i = 1; $i < count($array); $i++){
$copiado = $array[$i];
$j = $i;
while (($j > 0 ) && ($copiado < $array[$j-1])){
$array[$j] = $array[$j-1];
$j--;
}
$array[$j] = $copiado;
}
$time_end = microtime_float();
//Mostra o tempo que levou para ordenar
echo $time = $time_end - $time_start;
//Exibe a ordenação
print_r ($array);
C++
void Inserction(int n, int vetor[]){
int j,i,key;
for(j = 1; j < n; j++){
key = vetor[j];
i = j - 1;
while(i >= 0 && vetor[i] > key){
vetor[i + 1] = vetor[i];
i = i - 1;
}
vetor[i + 1] = key;
}
}
R
insertSort <- function(vec) {
for(i in 1:length(vec)) {
key <- vec[i]
j <- i
while(j > 1 && vec[j - 1] > key) {
vec[j] <- vec[j - 1]
j <- j - 1
}
vec[j] <- key
}
return(vec)
}
21
Insertion sort
22
Simulador Online
Para um melhor entendimento, recomendo utilizarem o Simulador Online
ordenação de números aleatórios pelo Insertion Sort.
[2]
para visualizarem exemplos de
Referências
• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition.
Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.1: Sorting by Insertion, pp. 80–105.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms,
Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 2.1: Insertion sort, pp. 15–21.
Ligações externas
• Uma animação em Java mostrando passo-a-passo a implementação do insertion sort. [3]
• Pesquisa e Ordenação [4]
Referências
[1] AZEREDO, Paulo A.. Métodos de Classificação de Dados e Análise de suas Complexidades. Rio de Janeiro: Campus, 1996. ISBN
85-352-0004-5
[2] http:/ / wikipedia. artudi. org/ Insertion%20Sort. php
[3] http:/ / web. engr. oregonstate. edu/ ~minoura/ cs162/ javaProgs/ sort/ InsertSort. html
[4] http:/ / soucomputeiro. blogspot. com/
Selection sort
Selection sort
classe
estrutura de dados
Selection sort
23
caso
total,
auxiliar
Algoritmos
O selection sort (do inglês, ordenação por seleção) é um algoritmo de ordenação
baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior
dependendo da ordem requerida), depois o de segundo menor valor para a segunda
posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos
dois elementos.
Complexidade
O algoritmo possui complexidade
enquanto que, por exemplo, os algoritmos
Heapsort e Mergesort possuem complexidades
.
Implementações
Animação do algoritmo
selection sort.
Código em Portugol
//exemplo de ordenação crescente de um vetor com dez posições:
INICIO
//declarar as variáveis:
Inteiro a[10] <- {12, 7, 4, 50, 8, 15, 30, 21, 18, 1}
Inteiro i, j, aux, menor
//ordenar o vetor:
Para i de 0 ate 8 passo 1
menor <- i
Para j De i+1 Até 9 passo 1
Se a[menor] > a[j] então
menor <- j
Fimse
Selection sort
Próximo
Se menor =/= i então
aux <- a[menor]
a[menor] <- a[i]
a[i] <- aux
Fimse
Próximo
//escrever o vetor ordenado:
Para i De 0 Até 9 Passo 1
Escrever a[i], " "
Próximo
FIM
~~~~
C
void selection_sort(int num[], int tam)
{
int i, j, min;
for (i = 0; i < (tam-1); i++)
{
min = i;
for (j = (i+1); j < tam; j++) {
if(num[j] < num[min]) {
min = j;
}
}
if (i != min) {
int swap = num[i];
num[i] = num[min];
num[min] = swap;
}
}
}
Código da ordenação SelectionSort com strings
void ordenar_selecao_nome() {
int i,j,n;
for(i=0; i<n-1; i++) {
for(j=i+1; j<n; j++) {
if(strcmpi(vetor[i], vetor[j])>0) {
strcpy(aux_char, vetor[i]);
strcpy(vetor[i], vetor[j]);
strcpy(vetor[j], aux_char);
}
}
}
24
Selection sort
25
Código em C++
template<class T>
void selection_sort( std::vector<T> &lista )
{
for( std::vector<T>::iterator it = lista.begin(); it != lista.end()-1;
++it )
{
std::iter_swap( it, std::min_element( it, lista.end() ) );
}
}
Código em C#
public void SelectionSort(int[] vetor)
{
int min, aux;
for (int i = 0; i < vetor.Length - 1; i++)
{
min = i;
for (int j = i + 1; j < vetor.Length; j++)
if (vetor[j] < vetor[min])
min = j;
if (min != i)
{
aux = vetor[min];
vetor[min] = vetor[i];
vetor[i] = aux;
}
}
}
Código em Pascal
Program selectionsort(input,output);
Var
i,tam,a,tmp,n
: integer;
v
: array[1..50] of integer;
trocou
: boolean;
Begin
tam:=n-1;
a:=1;
trocou:=true;
while (trocou) and (a<=n-1) do
Selection sort
Begin
trocou:=false;
for i:=1 to tam do
if v[i]>v[i+1] then
Begin
tmp:=v[i];
v[i]:=v[i+1];
v[i+1]:=tmp;
trocou:=true;
End;
tam:=tam-1;
a:=a+1;
End;
Readln;
End.
Código em Java
public static void SelectionSort(int[] v) {
int index_min,
aux;
for (int i = 0; i < v.length; i++) {
index_min = i;
for (int j = i + 1; j < v.length; j++) {
if (v[j] < v[index_min]) {
index_min = j;
}
}
if (index_min != i) {
aux = v[index_min];
v[index_min] = v[i];
v[i] = aux;
}
}
}
Código em Visual Basic
Public Function SelectionSort(Vetor(), tam)
Dim i, j
Dim min, aux
For i = 0 To tam
min = i
For j = i + 1 To tam
If Vetor(j) < Vetor(min) Then min = j
Next j
26
Selection sort
27
aux = Vetor(i)
Vetor(i) = Vetor(min)
Vetor(min) = aux
Next i
End Function
Código em Python
def selectsort (L):
n=len(L)
for i in range(n-1):
mini = i
for j in range(i+1,n):
if(L[j]<L[mini]):
mini=j
L[i],L[mini]=L[mini],L[i]
Código em PHP
function selection_sort(&$array) {
$len = count($array) -1;
for($i=0; $i<=$len ; $i++) {
$ini = $i;
for($j=$i+1; $j<=$len; $j++) {
if ($array[$j] < $array[$i]) {
$ini = $j;
}
}
if ($ini != $i) {
$troca = $array[$i];
$array[$i] = $array[$ini];
$array[$ini] = $troca;
}
}
}
Shell sort
28
Shell sort
Shell sort
classe
estrutura de dados
depende da sequência do gap. Melhor conhecida:
depende da sequência do gap
caso
Algoritmos
Criado por Donald Shell em 1959[1] , publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente
algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta.[2]
O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um
único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles.[3]
Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é
aplicado o método da ordenação por inserção.
Implementações do algoritmo
Código em Java
public static void shellSort(Integer[] nums) {
int n = nums.length;
int h = n / 2;
int c, j;
while (h > 0) {
for (int i = h; i < n; i++) {
c = nums[i];
j = i;
while (j >= h && nums[j - h] > c) {
nums[j] = nums[j - h];
j = j - h;
}
nums[j] = c;
}
h = h / 2;
}
}
Shell sort
29
Código em Python
def shellSort(nums):
n = len(nums)
h = int(n / 2)
while h > 0:
for i in range(h, n):
c = nums[i]
j = i
while j >= h and c < nums[j - h]:
nums[j] = nums[j - h]
j = j - h
nums[j] = c
h = int(h / 2.2)
void ShellSort( apvector <int> &num) {
int i, temp, flag = 1, numLength = num.length( );
int d = numLength;
while( flag || (d > 1))
// boolean flag (true when not equal to 0)
{
flag = 0;
// reset flag to 0 to check for future swaps
d = (d+1) / 2;
for (i = 0; i < (numLength - d); i++)
{
if (num[i + d] > num[i])
{
temp = num[i + d];
// swap positions i+d and i
num[i + d] = num[i];
num[i] = temp;
flag = 1;
// tells swap has occurred
}
}
}
return;
}
Código em C
void shellSort(int * vet, int size) {
int i , j , value;
int gap = 1;
do {
gap = 3*gap+1;
} while(gap < size);
do {
gap /= 3;
for(i = gap; i < size; i++) {
value =vet[i];
Shell sort
30
j = i - gap;
while (j >= 0 && value < vet[j]) {
vet [j + gap] =vet[j];
j -= gap;
}
vet [j + gap] = value;
}
} while ( gap > 1);
}
Código em PHP
function shellSort($arr_sort){
$pet=1;
do{
$pet = 3*$pet+1;
}while($pet <count($arr_sort));
do{
$pet /=3;
$pet = intval($pet);
for($i=$pet;$i<count($arr_sort);$i++)
{
$temp = $arr_sort[$i];
$j = $i - $pet;
while($j >=0 && $temp < $arr_sort[$j])
{
$arr_sort[$j + $pet] = $arr_sort[$j];
$j -= $pet;
}
$arr_sort[$j + $pet] = $temp;
}
}while($pet >1);
return $arr_sort;
}
Código em Ruby
def shellSort( array )
n = array.length
h = n/2
while h > 0
for i in (h...n)
c = array[i]
j = i
while j >= h and c < array[j-h]
array[j] = array[j-h]
j = j-h
array[j] = c
end
Shell sort
31
end
h = (h/2.2).to_i
end
end
Exemplo de execução
Execução:
Dado o vetor de entrada: 12, 43, 1, 6, 56, 23, 52, 9
12, 43, 1, 6, 56, 23, 52, 9
12, 43, 1, 6, 56, 23, 52, 9
1, 43, 12, 6, 56, 23, 52, 9
1, 6, 12, 23, 56, 43, 52, 9
1, 6, 12, 23, 52, 43, 56, 9
1, 6, 12, 23, 52, 9, 56, 43
1, 6, 12, 9, 52, 23, 56, 43
1, 6, 9, 12, 52, 23, 56, 43
1, 6, 9, 12, 23, 52, 56, 43
1, 6, 9, 12, 23, 52, 43, 56
1, 6, 9, 12, 23, 43, 52, 56
Em negrito estão os números trocados na atual iteração.
Após as seguintes trocas acima, obtemos o vetor ordenado: 1, 6, 9, 12, 23, 43, 52, 56.
Conclusão
A ordenação Shell utiliza a quebra sucessiva da sequência a ser ordenada e implementa a ordenação por inserção na
sequência obtida. Por ser um método de complexidade O(n^2 ) não é aconselhável a sua implementação para
sequências grandes, mas possui uma boa eficiência para as pequenas e medianas.
85-352-0004-5
[2] WIRTH, Niklaus. Algoritmos e Estruturas de Dados. Rio de Janeiro: Prentice-Hall do Brasil, 1989. 61-63 p. ISBN 85-7054-033-7
[3] Veloso, Paulo; SANTOS, Clesio dos; AZEREDO, Paulo; FURTADO, Antonio. Estruturas de Dados. 4ª ed. Rio de Janeiro: Campus,
1986. 184-185 p. ISBN 85-7001-352-3
Quicksort
32
Quicksort
Quicksort
classe
estrutura de dados
caso
otimo
Não
estabilidade
não-estável
Algoritmos
O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960[1]
, quando visitou a Universidade de Moscovo como estudante. Naquela época, Hoare trabalhou em um projeto de
tradução de máquina para o National Physical Laboratory. Ele criou o 'Quicksort ao tentar traduzir um dicionário de
inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que
possam ser resolvidos mais facil e rapidamente. Foi publicado em 1962 após uma série de refinamentos.[2]
O Quicksort é um algoritmo de ordenação por comparação não-estável.
Quicksort
O algoritmo
O Quicksort adota a estratégia de divisão e conquista. A estratégia consiste
em rearranjar as chaves de modo que as chaves "menores" precedam as
chaves "maiores". Em seguida o Quicksort ordena as duas sublistas de
chaves menores e maiores recursivamente até que a lista completa se
encontre ordenada. [3] Os passos são:
1. Escolha um elemento da lista, denominado pivô;
2. Rearranje a lista de forma que todos os elementos anteriores ao pivô
sejam menores que ele, e todos os elementos posteriores ao pivô sejam
maiores que ele. Ao fim do processo o pivô estará em sua posição final e
haverá duas sublistas não ordenadas. Essa operação é denominada
partição;
3. Recursivamente ordene a sublista dos elementos menores e a sublista dos
elementos maiores;
A base da recursão são as listas de tamanho zero ou um, que estão sempre
ordenadas. O processo é finito, pois a cada iteração pelo menos um
elemento é posto em sua posição final e não será mais manipulado na
iteração seguinte.
Complexidade
• Complexidade de tempo: θ(n lg2 n) no melhor caso e θ(n) no caso médio
e θ(n2) no pior caso;
Algumas etapas do algoritmo Quicksort.
• Complexidade de espaço: θ(lg2 n) no melhor caso e no caso médio e
θ(lg2 n) no pior caso. R. Sedgewick desenvolveu uma versão do
Quicksort com partição recursão de cauda que tem complexidade θ(n2) no pior caso.
Implementações
Pseudocódigo
procedimento QuickSort(X[], IniVet, FimVet)
var
i, j, pivo, aux
início
i <- IniVet
j <- FimVet
pivo <- X[(IniVet + FimVet) div 2]
enquanto(i < j)
|
enquanto (X[i] < pivo) faça
|
|
i <- i + 1
|
fimEnquanto
|
enquanto (X[j] > pivo) faça
|
|
j <- j - 1
|
fimEnquanto
|
se (i <= j) então
|
| aux <- X[i]
33
Quicksort
|
|
X[i] <- X[j]
|
|
X[j] <- aux
|
|
i <- i + 1
|
|
j <- j - 1
|
fimSe
fimEnquanto
se (j > IniVet) então
|
QuickSort(X, IniVet, j)
fimSe
se (i < FimVet) então
| QuickSort(X, i, FimVet)
fimse
fimprocedimento
PHP 5 - OO
class QuickSortUtil {
private static function partition(&$array, $f, $l, $property) {
$pivot = $array[$f]->$property;
while ($f < $l) {
while ($array[$f]->$property < $pivot) $l++;
while ($array[$l]->$property > $pivot) $f--;
$temp = $array[$f];
$array[$f] = $array[$l];
$array[$l] = $temp;
}
return $f;
}
public static function sort(&$array, $property, $f=null, $l=null) {
if(is_null($f)) $f = 0;
if(is_null($l)) $l = count($array)-1;
if ($f >= $l) return;
$pivot_index = self::partition($array, $f, $l, $property);
self::sort($array, $property, $f, $pivot_index);
self::sort($array, $property, $pivot_index+1, $l);
}
}
Delphi (Método Recursivo)
procedure QuickSort(var A: array of Integer);
procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
Lo, Hi, Mid, T: Integer;
begin
34
Quicksort
35
Lo := iLo;
Hi := iHi;
Mid := A[(Lo + Hi) div 2];
repeat
while A[Lo] < Mid do Inc(Lo);
while A[Hi] > Mid do Dec(Hi);
if Lo <= Hi then
begin
T := A[Lo];
A[Lo] := A[Hi];
A[Hi] := T;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then QuickSort(A, iLo, Hi);
if Lo < iHi then QuickSort(A, Lo, iHi);
end;
begin
QuickSort(A, Low(A), High(A));
end;
{Chamando em um evento de onClick}
procedure TForm1.Button1Click(Sender: TObject);
var
arr: array[0..100] of integer;
I: Integer;
begin
for I:=Low(arr) to High(arr) do
arr[I]:=Random(High(Integer));
Quick_Sort(arr);
end;
Visual Basic
Sub QuickSort(ByRef vetor() As Long, ByVal inicio As Long, ByVal final As Long, ByRef iteracoes As Long)
Dim pivo As Long
Dim i As Long
Dim j As Long
iteracoes = iteracoes + 1
If final > inicio Then
i = inicio
j = final
pivo = vetor(Fix((inicio + final) / 2))
While i <= j
While vetor(i) < pivo
Quicksort
36
i = i + 1
Wend
While pivo < vetor(j)
j = j - 1
Wend
If i <= j Then
Call Troca(vetor(i), vetor(j))
i = i + 1
j = j - 1
End If
Wend
Call QuickSort(vetor, inicio, j, iteracoes)
Call QuickSort(vetor, i, final, iteracoes)
End If
End Sub
Sub Troca(ByRef val1 As Long, ByRef val2 As Long)
Dim aux As Long
aux = val1
val1 = val2
val2 = aux
End Sub
Python
Versão simples
def quicksort(v):
if len(v) <= 1:
return v # uma lista vazia ou com 1 elemento ja esta ordenada
less, equal, greater = [], [], [] # cria as sublistas dos maiores,
menores e iguais ao pivo
pivot = v[0] # escolhe o pivo. neste caso, o primeiro elemento da
lista
for x in v:
# adiciona o elemento x a lista corespondeste
if x < pivot:
less.append(x)
elif x == pivot:
equal.append(x)
else:
greater.append(x)
return quicksort(less) + equal + quicksort(greater) # concatena e
retorna recursivamente
# .. as listas
ordenadas
Versão in-place
Quicksort
def partition(v, left, right):
i = left
for j in range(left + 1, right + 1):
if v[j] < v[left]: # Se um elemento j for menor que o pivo
i += 1 # .. incrementa-se i
v[i], v[j] = v[j], v[i] # .. e troca o elemento j de
posicao o elemento i
v[i], v[left] = v[left], v[i] # O pivo e' colocado em sua posicao
final
return i
def quicksort(v, left, right):
if right > left: # Verifica se a lista tem 2 ou mais itens
pivotIndex = partition(v, left, right) # Pega a posicao do pivo
quicksort(v, left, pivotIndex - 1) # Ordena recursivamente os
itens menores que o pivo
quicksort(v, pivotIndex + 1, right) # Ordena recursivamente os
itens maiores que o pivo
'''
Exemplo de uso
>>> a = [4, 2, 4, 6, 3, 2, 5, 1, 3]
>>> quicksort(a, 0, len(a)-1)
>>> print a
>>> [1, 2, 2, 3, 3, 4, 4, 5, 6]
'''
Assembly x86-gas-Linux
/*void quicksort_as (int *x, int n);*/
.globl quicksort_as
quicksort_as:
pushl %ebp
movl %esp, %ebp
/* 8(%ebp)= ponteiro do arranjo */
/* 12(%ebp)= num de elementos */
movl 12(%ebp), %eax
dec %eax
movl $4, %ebx
mul %ebx
pushl %eax
pushl $0
pushl 8(%ebp)
call quicksort_as_
leave
ret
quicksort_as_:
pushl %ebp
37
Quicksort
movl %esp, %ebp
/* 8(%ebp)= ponteiro do arranjo */
/* 12(%ebp)= esq */
/* 16(%ebp)= dir */
movl 12(%ebp), %ecx
movl %ecx, %edx
movl 8(%ebp), %eax
addl %ecx, %eax
movl 16(%ebp), %ecx
movl 8(%ebp), %ebx
addl %ecx, %ebx
/* agora %eax aponta p/ x[esq] e %ebx x[dir]*/
addl %edx, %ecx
/*%ecx eh esq + dir*/
pushl %eax
movl %ecx, %eax
movl $2, %ecx
cltd
idivl %ecx
/* div %eax por 2=%ecx*/
movl $4, %ecx
cltd
idivl %ecx
mul %ecx
movl 8(%ebp), %ecx
addl %eax, %ecx
movl (%ecx), %ecx
popl %eax
/*%ecx = compare(cmp)*/
quicksort_imj:
cmp %eax, %ebx
jle quicksort_fim
quicksort_inci:
cmp (%eax), %ecx
jle quicksort_incj
addl $4, %eax
jmp quicksort_inci
quicksort_incj:
cmp (%ebx), %ecx
jge quicksort_troca
subl $4, %ebx
jmp quicksort_incj
quicksort_troca:
cmp %eax, %ebx
jl quicksort_fim
movl (%ebx), %edx
pushl (%eax)
movl %edx, (%eax)
popl (%ebx)
38
Quicksort
addl $4, %eax
subl $4, %ebx
jmp quicksort_imj
quicksort_fim:
/*salvando registradores na pilha p/ fazer chamada de função*/
pushl %eax
pushl %ebx
/*passando parametros p/ chamada recursiva*/
subl 8(%ebp), %eax
cmp %eax, 16(%ebp)
jle quicksort_2a_rec
pushl 16(%ebp)
pushl %eax
pushl 8(%ebp)
call quicksort_as_
addl $12, %esp
quicksort_2a_rec:
/*recuperando registradores apos chamada de funcao*/
popl %ebx
popl %eax
subl 8(%ebp), %ebx
cmp %ebx, 12(%ebp)
jge quicksort_final
/*passando parametros p/ chamada recursiva*/
pushl %ebx
pushl 12(%ebp)
pushl 8(%ebp)
call quicksort_as_
quicksort_final:
leave
ret
Haskell
sort :: (Ord a)
=> [a] -> [a]
sort []
= []
sort (pivot:rest) = (sort [y | y <- rest, y < pivot])
++ [pivot] ++
(sort [y | y <- rest, y >=pivot])
Lisp
(defun partition (fun array)
(list (remove-if-not fun array) (remove-if fun array)))
(defun sort (array)
(if (null array) nil
(let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
(append (sort (car part)) (cons (car array) (sort (cadr part)))))))
39
Quicksort
40
Perl
Versões anteriores ao Perl 5.6 utilizavam o algoritmo quicksort para implementar a função sort [4][5] , então o código
em Perl pode resumir-se a:
my @ordenada = sort @lista;
Como a implementação do quicksort pode assumir tempos quadráticos para algumas entradas, o algoritmo foi
substituído na versão 5.8 pelo mais estável mergesort, cujo pior caso é θ(n lg2 n). Ainda assim, é possível forçar o
uso do quicksort através do pragma 'sort' [6]:
use sort '_quicksort';
my @ordenada = sort @lista;
Uma implementação em Perl puro (mais lenta que o 'sort' embutido) pode ser:
sub quicksort {
my @lista = @_;
my (@menores, @iguais, @maiores);
return @lista if @lista < 2;
foreach (@lista) {
if ($_ < $lista[0]) {
push @menores, $_;
}
elsif ($_ == $lista[0]) {
push @iguais, $_;
}
else {
push @maiores, $_;
}
}
return quicksort(@menores), @iguais, quicksort(@maiores);
}
Já uma versão menor (e certamente menos legível) poderia ser:
sub quicksort {
return @_ if @_ < 2;
my (@iguais, @maiores, @menores);
push @{ (\@iguais, \@menores, \@maiores)[ $_[0] <=> $_ ]}, $_ for @_;
quicksort(@menores), @iguais, quicksort(@maiores);
}
Ruby
def sort(array)
return array if array.size <= 1
pivot = array[0]
return sort(array.select { |y| y < pivot }) +
array.select { |y| y == pivot } +
sort(array.select { |y| y > pivot })
Quicksort
41
end
Groovy
def sort(list) {
if (list.isEmpty()) return list
anItem = list[0]
def smallerItems = list.findAll{it < anItem}
def equalItems = list.findAll{it = anItem}
def largerItems = list.findAll{it > anItem}
sort(smallerItems) + equalItems + sort(largerItems)
}
ML
fun filter nil elem cmp = nil
| filter (x::xl) elem cmp =
if (cmp(x, elem))
then x :: filter xl elem cmp
else filter xl elem cmp;
fun quicksort nil = nil
| quicksort (pivot::xl) =
let
val small = filter xl pivot (op <);
val medium = pivot :: filter xl pivot (op =);
val large = filter xl pivot (op >);
in
(quicksort small) @ medium @ (quicksort large)
end;
PHP
<?php
/*********************************************************************
*Obs.: a implementação usa parâmetros por referência, isto é, o vetor
*passado será modificado.
*********************************************************************/
function troca(&$v1, &$v2){
$vaux = $v1;
$v1 = $v2;
$v2 = $vaux;
}
//divide
function
$i =
$j =
o array em dois
divide(&$vet, $ini, $fim){
$ini;
$fim;
Quicksort
42
$dir = 1;
while ($i > $j){
if ($vet[$i] < $vet[$j]){
troca($vet[$i], $vet[$j]);
$dir = - $dir;
}
if ($dir = 1) {
$j--;
}else{
$i++;
}
}
return $i;
}
//ordena
function quicksort(&$vet, $ini, $fim){
if ($ini < $fim){
$k = divide($vet, $ini, $fim);
quicksort($vet, $ini, $k-1);
quicksort($vet, $k+1, $fim);
}
}
quicksort($vet,0,count($vet));
?>
C++
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;
template <typename T>
void sort(T begin, T end) {
if (begin != end) {
T middle = partition (begin, end, bind2nd(less<iterator_traits<T>::value_type>(),
*begin));
sort (begin, middle);
sort (max(begin + 1, middle), end);
}
}
ASP
<%
Response.Write("QuickSort Algorithm")& vbNewLine
Sub QuickSort(vec,loBound,hiBound)
Dim pivot,loSwap,hiSwap,temp
Quicksort
43
'== Two items to sort
if hiBound - loBound = 1 then
if vec(loBound) > vec(hiBound) then
temp=vec(loBound)
vec(loBound) = vec(hiBound)
vec(hiBound) = temp
End If
End If
'== Three or more items to sort
pivot = vec(int((loBound + hiBound) / 2))
vec(int((loBound + hiBound) / 2)) = vec(loBound)
vec(loBound) = pivot
loSwap = loBound + 1
hiSwap = hiBound
do
'== Find the right loSwap
while loSwap < hiSwap and vec(loSwap) <= pivot
loSwap = loSwap + 1
wend
'== Find the right hiSwap
while vec(hiSwap) > pivot
hiSwap = hiSwap - 1
wend
'== Swap values if loSwap is less then hiSwap
if loSwap < hiSwap then
temp = vec(loSwap)
vec(loSwap) = vec(hiSwap)
vec(hiSwap) = temp
End If
loop while loSwap < hiSwap
vec(loBound) = vec(hiSwap)
vec(hiSwap) = pivot
'== Recursively call function .. the beauty of Quicksort
'== 2 or more items in first section
if loBound < (hiSwap - 1) then Call QuickSort(vec,loBound,hiSwap-1)
'== 2 or more items in second section
if hiSwap + 1 < hibound then Call QuickSort(vec,hiSwap+1,hiBound)
End Sub
'QuickSort
Sub PrintArray(vec,lo,hi)
'== Simply print out an array from the lo bound to the hi bound.
Quicksort
Dim i
For i = lo to hi
Response.Write vec(i)
Next
End Sub 'PrintArray
Randomize
Dim x(9)
For z = 0 to 9
x(z) = int(Rnd*1000)
If (Rnd < 0.5) then x(z) = x(z)-1000
Next
Response.Write ("Here is a jumbled array:") & vbNewLine
Call PrintArray(x,0,9)
Call QuickSort(x,0,9)
Response.Write("Now the array is sorted!")& vbNewLine
Call PrintArray(x,0,9)
Response.Write(vbNewLine)
%>
C
void swap(int* a, int* b) {
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int vec[], int left, int right) {
int i, j;
i = left;
for (j = left + 1; j <= right; ++j) {
if (vec[j] < vec[left]) {
++i;
swap(&vec[i], &vec[j]);
}
}
swap(&vec[left], &vec[i]);
return i;
44
Quicksort
}
void quickSort(int vec[], int left, int right) {
int r;
if (right > left) {
r = partition(vec, left, right);
quickSort(vec, left, r - 1);
quickSort(vec, r + 1, right);
}
}
Implementaçao usando 'fat pivot':
void sort(int array[], int begin, int end) {
int pivot = array[begin];
int i = begin + 1, j = end, k = end;
int t;
while (i < j) {
if (array[i] < pivot) i++;
else if (array[i] > pivot) {
j--; k--;
t = array[i];
array[i] = array[j];
array[j] = array[k];
array[k] = t; }
else {
j--;
swap(array[i], array[j]);
} }
i--;
swap(array[begin], array[i]);
if (i - begin > 1)
sort(array, begin, i);
if (end - k
> 1)
sort(array, k, end);
}
Lembrando que quando você for chamar a função recursiva terá que chamar a mesma da seguinte forma
ordenar_quicksort_nome(0,n-1). O 0(zero) serve para o início receber a posição zero do vetor e o fim será o tamanho
do vetor -1.
void ordenar_quicksort_nome(int ini, int fim)
{
int i = ini, f = fim;
char pivo[50];
strcpy(pivo,vetor[(ini+fim)/2]);
if (i<=f)
45
Quicksort
46
{
while (strcmpi(vetor[i],pivo)<0) i++;
while (strcmpi(vetor[f],pivo)>0) f--;
if (i<=f)
{
strcpy (aux_char,vetor[i]);
strcpy (vetor[i],vetor[f]);
strcpy (vetor[f],aux_char);
i++; f--;
}
}
if (f>ini) ordenar_quicksort_nome(ini,f);
if (i<fim) ordenar_quicksort_nome(i,fim);
}
JAVA
public static void quick_sort(int []v,int ini, int fim){
int meio;
if(ini<fim){
meio = partition(v,ini,fim);
quick_sort(v,ini,meio);
quick_sort(v,meio+1,fim);
}
}
public static int partition(int []v, int ini, int fim){
int pivo, topo,i;
pivo = v[ini];
topo = ini;
for(i=ini+1;i<fim;i++){
if(v[i]<pivo){
v[topo]=v[i];
v[i]=v[topo+1];
topo++;
}
}
v[topo]=pivo;
return topo;
}
Quicksort
C#
static class QuickSort
{
public static void Ordenar(int[] vetor) {
Ordenar(vetor, 0, vetor.Length - 1);
}
private static void Ordenar(int[] vetor, int inicio, int fim) {
if (inicio < fim) {
int posicaoPivo = Separar(vetor, inicio, fim);
Ordenar(vetor, inicio, posicaoPivo - 1);
Ordenar(vetor, posicaoPivo + 1, fim);
}
}
private static int Separar(int[] vetor, int inicio, int fim) {
int pivo = vetor[inicio];
int i = inicio + 1, f = fim;
while (i <= f) {
if (vetor[i] <= pivo)
i++;
else if (pivo < vetor[f])
f--;
else {
int troca = vetor[i];
vetor[i] = vetor[f];
vetor[f] = troca;
i++;
f--;
}
}
vetor[inicio] = vetor[f];
vetor[f] = pivo;
return f;
}
}
Assembly x86
qsort:
@ Takes three parameters:
@
a:
Pointer to base of array a to be sorted (arrives in r0)
@
left: First of the range of indexes to sort (arrives in r1)
@
right: One past last of range of indexes to sort (arrives in r2)
@ This function destroys: r1, r2, r3, r4, r5, r7
stmfd
sp!, {r4, r6, lr}
@ Save r4 and r6 for caller
mov
r6, r2
@ r6 <- right
qsort_tailcall_entry:
sub
r7, r6, r1
@ If right - left <= 1 (already sorted),
47
Quicksort
48
cmp
r7, #1
ldmlefd sp!, {r1, r6, pc}
ldr
r7, [r0, r1, asl #2]
add
r2, r1, #1
mov
r4, r6
partition_loop:
ldr
r3, [r0, r2, asl #2]
cmp
r3, r7
addle
r2, r2, #1
ble
partition_test
sub
r4, r4, #1
ldr
r5, [r0, r4, asl #2]
str
r5, [r0, r2, asl #2]
str
r3, [r0, r4, asl #2]
partition_test:
cmp
r2, r4
blt
partition_loop
partition_finish:
sub
r2, r2, #1
ldr
r3, [r0, r2, asl #2]
str
r3, [r0, r1, asl #2]
str
r7, [r0, r2, asl #2]
bl
qsort
b
qsort_tailcall_entry
@
@
@
@
Return, moving r4->r1, restoring r6
r7 <- a[left], gets pivot element
l <- left + 1
r <- right
@
@
@
@
@
@
r3 <- a[l]
If a[l] <= pivot_element,
... increment l, and
... continue to next iteration.
Otherwise, decrement r,
... and swap a[l] and a[r].
@ If l < r,
@ ... continue iterating.
@ Decrement l
@ Swap a[l] and pivot
@ Call self recursively on left part,
@ with args a (r0), left (r1), r (r2),
@ also preserves r6 and
@ moves r4 (l) to 2nd arg register (r1)
@ Tail-call self on right part,
@ with args a (r0), l (r1), right (r6)
Prolog
partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :(
X @< Pivot ->
Smalls = [X|Rest],
partition(Xs, Pivot, Rest, Bigs)
;
Bigs = [X|Rest],
partition(Xs, Pivot, Smalls, Rest)
).
quicksort([])
--> [].
quicksort([X|Xs]) -->
{ partition(Xs, X, Smaller, Bigger) },
quicksort(Smaller), [X], quicksort(Bigger).
Quicksort
Lua
function quickSort(v, ini, fim)
i, j = ini, fim
pivo = v[math.floor((ini + fim)/2)]
while i <= j do
while (v[i] < pivo) do i=i+1 end
while (v[j] > pivo) do j=j-1 end
if (i<=j) then
v[i], v[j] = v[j], v[i]
i, j = i+1, j-1
end
end
if j > ini then quickSort(v, ini, j) end
if i < fim then
quickSort(v, i, fim) end
end
Comparação com outros algoritmos de ordenação
Quicksort é uma versão optimizada de uma árvore binária ordenada. Em vez de introduzir itens sequencialmente
numa árvore explicita, o Quicksort organiza-os correntemente na árvore onde está implícito, fazendo-o com
chamadas recursivas à mesma. O algoritmo faz exactamente as mesmas comparações, mas com uma ordem
diferente.
O algoritmo que mais se familiariza com o Quicksort é o Heapsort. Para o pior caso neste algoritmo temos
. Mas, o Heapsort em média trata-se de uma algoritmo mais lento que o Quicksort, embora tenha sido
muito debatido essa afirmação. No Quicksort permanece o caso do pior caso, à excepção quando se trata de usar a
variante Intro sort, que muda para Heapsort quando um pior caso é detectado. Caso se saiba à partida que será
necessário o uso do heapsort é aconselhável usá-lo directamente, do que usar o introsort e depois chamar o heapsort,
torna mais rápido o algoritmo.
O Quicksort também compete com o Mergesort, outro algoritmo de ordenação recursiva, tendo este o benefício de
ter como pior caso
. Mergesort, ao contrário do Quicksort e do Heapsort, é estável e pode facilmente
ser adptado para operar em listas encadeadas e em listas bastantes grandes alojadas num tipo de acesso lento a média
como um Network-Attached Storage ou num disco. Embora o Quicksort possa ser operado em listas encadeadas, por
vezes escolhendo um mau pivô sem acesso aleatório. A maior desvantagem do Mergesort é que quando opera em
arrays, requer
de espaço para o melhor caso, considerando que o Quicksort com um particionamento espacial
e com recursão utiliza apenas
de espaço.
Bucket sort com dois buckets é muito idêntico ao Quicksort, o pivô neste caso é garantidamente o valor do meio do
vector.
49
Quicksort
Veja também
•
•
•
•
•
•
Ordenação de vetor
Merge sort
Heapsort
Selection sort
Bubble sort
Busca linear
85-352-0004-5
[2] An Interview with C.A.R. Hoare (http:/ / cacm. acm. org/ magazines/ 2009/ 3/ 21782-an-interview-with-car-hoare/ fulltext). Communications
of the ACM, March 2009 ("premium content").
[3] BAASE, Sara. Computer Algorithms: Introduction to Design and Analysis (em inglês). 2ª ed. Reading, Massachusetts: Addison-Wesley,
1988. 53 p. ISBN 0-201-06035-3
[4] http:/ / perldoc. perl. org/ functions/ sort. html
[5] Documentação oficial da função 'sort' em Perl (http:/ / perldoc. perl. org/ functions/ sort. html). perl.org. Página visitada em 2008-10-20.
[6] http:/ / perldoc. perl. org/ sort. html
Ligações externas
• Rápida aula de Quicksort (http://www.ime.usp.br/~pf/algoritmos/aulas/quick.html)
• Animação do processo de ordenação pelo Quicksort (http://www.cs.ubc.ca/spider/harrison/Java/
sorting-demo.html)
• Explanação video de Quicksort usando cartões e de código em C++ (http://www.datastructures.info/
what-is-quicksort-and-how-does-it-work-quick-sort-algorithm/)
• QuickSort Code (http://www.algorithm-code.com/wiki/Quick_Sort)
Algoritmo de busca
Em ciência da computação, um algoritmo de busca, em termos gerais, é um algoritmo que toma um problema como
entrada e retorna a solução para o problema, geralmente após resolver um número possível de soluções. A maioria
dos algoritmos estudados por cientistas da computação que resolvem problemas são algortimos de busca. O conjunto
de todas as soluções possíveis para um problema é chamado de espaço de busca.
50
Busca linear
51
Busca linear
Na área de informática, ou Ciência da Computação, costuma-se usar o termo busca linear (ou busca sequêncial)
para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo
que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor
ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa
com o gráfico de tempo logarítmo.
Análise de Complexidade
No melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca. No pior caso, o
elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de
elementos. No caso médio, o elemento é encontrado após N/2 comparações. O algoritmo de busca linear é um
algoritmo O(n).
Exemplos de Código
Exemplo de código em C
/**
* Retorna -1 caso não encontre ou a posição, caso encontre.
*/
int procura(char vetor[], int tamanho, char elementoProcurado) {
int i;
for (i = 0; i < tamanho; i++) {
if (vetor[i] == elementoProcurado) {
return i;
}
}
return -1;
}
Exemplo de código em Pascal
function procura(vetor :array [1..10] of integer; elementoProcurado:
integer ; busca : boolean); {supondo que o vetor tem tamanho 10}
var
i : integer;
begin
busca:=false;
for i := 1 to 10 do
begin
if (vetor[i] = elementoProcurado) then
begin
procura := i; {retorna o índice do elemento procurado}
busca:=true; {para indicar que a busca encontrou o
valor procurado no vetor}
Busca linear
52
end;
end;
end.
Exemplo de código em Java
public int procura(Object[] vetor, Object elementoProcurado) {
for (int i = 0; i < vetor.length; i++)
if (vetor[i].equals(elementoProcurado))
return i;
return -1; // Não achou, retorna -1
}
Exemplo de código em PHP
<?php
/**
* Retorna -1 caso não encontre ou a posição
* caso encontre.
*/
function buscaSequencial($elementoProcurado, array $vetor) {
$tamanhoVetor = count($vetor);
for ($i = 0; $i < $tamanhoVetor; $i++) {
if ($vetor[$i] == $elementoProcurado) {
return $i;
}
}
return -1;
}
$a = array(1, 2, 3, 4, 5, 6);
print "<br> buscaSequencial(4, [1,
var_dump(buscaSequencial(4, $a));
?>
2, 3, 4, 5, 6]); return: ";
2, 3, 4, 5, 6]); return: ";
2, 3, 4, 5, 6]); return: ";
2, 3, 4, 5, 6]); return: ";
Busca linear
Fluxograma do Algoritmo
Artigos relacionados
•
•
•
•
•
•
Ordenação de vector
Quick sort
Merge sort
Selection sort
Bubble sort
Pesquisa binária
53
Pesquisa binária
54
Pesquisa binária
Pesquisa binária
classe
Algoritmo de busca
estrutura de dados
caso
otimo
Sim
espaço
Algoritmos
A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em
vetores que requer acesso aleatório aos elementos do mesmo. Ela parte do pressuposto de que o vetor está ordenado
e realiza sucessivas divisões do espaço de busca (divisão e conquista) comparando o elemento buscado (chave) com
o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso
contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do
vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
Análise de Complexidade
A complexidade desse algoritmo é da ordem de Θ(log2 n), em que n é o tamanho do vetor de busca. Apresenta-se
mais eficiente que a Busca linear cuja ordem é O(n).
Pseudo-Código
Um pseudo-código recursivo para esse algoritmo, dados V o vetor com elementos comparáveis, n seu tamanho e e
o elemento que se deseja encontrar:
BUSCA-BINÁRIA (V[], início, fim, e)
i recebe o índice do meio entre início e fim
se (v[i] = e) entao
devolva o índice i
# elemento e encontrado
fimse
se (inicio = fim) entao
não encontrou o elemento procurado
senão
se (V[i] vem antes de e) então
faça a BUSCA-BINÁRIA(V, i+1, fim, e)
senão
faça a BUSCA-BINÁRIA(V, inicio, i-1, e)
fimse
fimse
Pesquisa binária
Implementações
Código em Ruby
def search(vector, lower, upper, element)
return -1 if lower > upper
mid = (lower+upper)/2
if (vector[mid] == element)
element
elsif (element < vector[mid])
search(vector, lower, mid-1, element)
else
search(vector, mid+1, upper, element)
end
end
def binary_search(vector,element)
search(vector, 0, vector.size-1, element)
end
Código em C
//em C para se passar um vetor como parâmetro para uma função, tem que
se passar o ponteiro do vetor
int PesquisaBinaria ( int *array, int chave , int N)
{
int inf = 0; //Limite inferior
(o primeiro elemento do vetor
em C é zero
)
int sup = N-1; //Limite superior
(termina em um número a menos
0 à 9 são 10 numeros )
int meio;
while (inf <= sup)
{
meio = inf + (sup-inf)/2;
if (chave == array[meio])
return meio;
else if (chave < array[meio])
sup = meio-1;
else
inf = meio+1;
}
return -1;
// não encontrado
}
Obs: A linguagem C fornece a função bsearch[1] na sua biblioteca padrão.
55
Pesquisa binária
Java
public static int buscaBinaria( int[] array, int valor )
{
int esq = 0;
int dir = array.length - 1;
int valorMeio;
while ( esq <= dir ) {
valorMeio = esq + ((dir - esq) / 2);
if ( array[valorMeio] < valor ) {
esq = valorMeio + 1;
} else if( array[valorMeio] > valor ) {
dir = valorMeio - 1;
} else {
return valorMeio;
}
}
return -1;
}
Código em python
def binsearch(seq, search):
right = len(seq)
left = 0
previous_center = -1
if search < seq[0]:
return -1
while 1:
center = (left + right) / 2
candidate = seq[center]
if search == candidate:
return center
if center == previous_center:
return - 2 - center
elif search < candidate:
right = center
else:
left = center
previous_center = center
Código em C#
static int pesquisaBinaria(int[] vetor, int chave)
{
//Ordena o vetor.
Array.Sort(vetor);
56
Pesquisa binária
int meio;
int Min = 0;
int Max = vetor.Length - 1;
do
{
meio = (int)(Min + Max) / 2;
if (vetor[meio] == chave)
{
//Retorna a posição do número na seqüencia.
return meio;
}
else if (chave > vetor[meio])
Min = meio + 1;
else
Max = meio - 1;
}
while (Min <= Max);
//Caso o retorno for -1, então o número não existe na seqüencia.
return -1;
}
Código em Pascal
function BuscaBinaria (Vetor: array of string; Chave: string; Dim:
integer): integer;
var inicio, fim: integer; {Auxiliares que representam o
inicio e o fim do vetor analisado}
meio: integer; {Meio do vetor}
begin
fim := Dim; {O valor do último índice do vetor}
inicio := 1; {O valor do primeiro índice do vetor}
BuscaBinaria := -1; {Retorna o valor -1 se a chave nao for
encontrada.}
repeat
meio := (inicio+fim) div 2;
if (Chave = vetor[meio]) then
begin
BuscaBinaria := meio;
inicio:=fim+1; {Interrompo o repeat quando a
chave for encontrada sem ter que testar lá no until. Bonito não?!}
end;
if (Chave < vetor[meio]) then
fim:=(meio-1);
if (Chave > vetor[meio]) then
inicio:=(meio+1);
until (inicio > fim);
57
Pesquisa binária
58
end;
Código Recursivo em Pascal
function BuscaBinariaRecursiva(var Vetor: array of string; L,H:
integer; chave: string): integer;
var m:integer;
{variavel auxiliar que indica o meio do vetor}
begin
ordena(Vetor,H);
{Procedimento que ordena o vetor, tais como:
bubble sort, quick sort, entre outros}
if L>H then
{L= variavel que indica o começo do vetor, H=
variavel que indica o fim do vetor}
BuscaBinariaRecursiva:=-1
else
begin
m:=(L+H) div 2;
if x<Vetor[M] then
BuscaBinariaRecursiva:=BuscaBinariaRecursiva(Vetor,L,M-1,x)
else
if x>Vetor[M] then
BuscaBinariaRecursiva:=BuscaBinariaRecursiva(Vetor,M+1,H,x)
else
BuscaBinariaRecursiva:=M;
end;
end;
Código em Lua
function buscaBinaria(v, x)
ini = 1
fim = #v
while(ini<=fim)
do
pivo= math.floor((fim+ini)/2)
if(x > v[pivo])
then
ini = pivo+1
end
if(x < v[pivo])
then
fim = pivo-1
end
if (x==v[pivo])
then
return pivo
end
end
Pesquisa binária
59
return -1
end
Código em Scheme
(define vetor (vector 1 2 4 6 8 9 10 23 45 ))
(define (buscab vetor numero inicio fim)
(letrec ([ndivi (floor (/ (+ fim inicio) 2))] [n-medio
(vector-ref vetor ndivi)])
(cond
[(> inicio fim) false]
[(= numero n-medio) ndivi]
[(< numero n-medio) (buscab vetor numero inicio (- ndivi 1))]
[else (> numero n-medio) (buscab vetor numero (+ ndivi 1)
fim)])))
(buscab vetor 23 0 9)
Código em PHP
function buscaBinaria($valorPesquisa, array $vetor) {
$n_elementos = count($vetor);
$inicio = 0; $fim = $n_elementos -1; $meio = (int) (($fim $inicio) / 2) + $inicio;
while ($inicio <= $fim) {
if ($vetor[$meio] < $valorPesquisa) {
$inicio = $meio + 1;
} elseif ($vetor[$meio] > $valorPesquisa) {
$fim = $meio - 1;
} else {
return $meio;
}
$meio = (int) (($fim - $inicio) / 2) + $inicio;
}
return -1;
}
$a = array(1, 2, 3, 4, 5, 6);
print "call buscaBinaria(4, [1, 2, 3, 4, 5, 6]); return: ";
var_dump(buscaBinaria(4, $a));
Pesquisa binária
[1] bsearch(3) - binary search of a sorted array (http:/ / linux. die. net/ man/ 3/ bsearch)
Ligações externas
• Tecnologia da Informação - Goiânia - GO (http://www.go.senac.br/faculdade)
• Projeto de Algoritmos - Paulo Feofiloff -IME-USP (http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.
html)
• NIST Dicionário de Algoritmos e Estrutura de Dados :binary search (http://www.nist.gov/dads/HTML/
binarySearch.html)
• Tim Bray. On the Goodness of Binary Search (http://www.tbray.org/ongoing/When/200x/2003/03/22/
Binary). Pequeno ensaio das vantagens da busca binária e exemplo de código em Java.
• Explanação e código da busca binária em C++ (http://www.datastructures.info/
what-is-a-binary-seach-algorithm-and-how-does-it-work/)
• Google Research: Nearly All Binary Searches and Mergesorts are Broken (http://googleresearch.blogspot.com/
2006/06/extra-extra-read-all-about-it-nearly.html)
60
Algoritmo de ordenação Fonte: http://pt.wikipedia.org/w/index.php?oldid=26828026 Contribuidores: Andrevruas, Carnevalli, EduM, Hgfernan, João Carvalho, Leonardo.stabile, LeonardoG,
Marivb, Ndnaum, OS2Warp, Rafael.afonso, Rcaetano, Ricardo Ferreira de Oliveira, Santana-freitas, 18 edições anónimas
Bubble sort Fonte: http://pt.wikipedia.org/w/index.php?oldid=27756759 Contribuidores: Adailton, Alchimista, Andrevruas, Aprendiz de feiticeiro, Calraiden, Carnevalli, Ccuembej, EduM,
Eduardocolabardini, Educobuci, Felipo bacani, Gdst, Gean, Hgfernan, Jbsilva, Jonas AGX, João Carvalho, Kaze Senshi, Lailsonbm, Leonardo.stabile, LeonardoG, Luís Felipe Braga, Marivb,
Mestre5, Nuno Tavares, Níssius Guilet Ribas, OffsBlink, Rafael.afonso, Rafaelcosta1984, Reynaldo, Ricardo Ferreira de Oliveira, SalazarGui, Santana-freitas, Softpalm, Steinlh, Teles,
Thiagoharry, Tyran, Viniciusmc, Vupi, Xandi, 206 edições anónimas
Insertion sort Fonte: http://pt.wikipedia.org/w/index.php?oldid=27779369 Contribuidores: Alchimista, Analyst.rafael, Aprendiz de feiticeiro, Arademaker, Beria, Brunosmm, Davemustaine,
Dioneto, Dtavares, EduM, Giro720, Hennet, Hgfernan, Joaocastror, Jonas AGX, KarenHT, Loge, Luizkreile, Luís Felipe Braga, Níssius Guilet Ribas, OS2Warp, Ozymandias, Ricardo Ferreira de
Oliveira, Thiagoharry, Victorwss, Viniciusmc, 136 edições anónimas
Selection sort Fonte: http://pt.wikipedia.org/w/index.php?oldid=27528004 Contribuidores: Albmont, Aprendiz de feiticeiro, Bisbis, Carnevalli, Dtavares, Edgurgel, EduM, Hgfernan, Ilustrador,
Jean M. Tanzerino, Leonardo.stabile, Nuno Tavares, Rafael.afonso, Ricardo Ferreira de Oliveira, Rui Silva, Salgueiro, Silveiraneto, Thiagoharry, 61 edições anónimas
Shell sort Fonte: http://pt.wikipedia.org/w/index.php?oldid=27408512 Contribuidores: Carnevalli, DanielTsuneo, EduM, Fernandorossato, João Carvalho, Leslie, M.angicano, Marivb, Master,
OS2Warp, Philipetl, Psychotrance, Ricardo Ferreira de Oliveira, RicoCrivelli, TheCoreh, Thiagoharry, 57 edições anónimas
Quicksort Fonte: http://pt.wikipedia.org/w/index.php?oldid=27749921 Contribuidores: Adailton, Al3xeng, Bertoche, Bisbis, BrunoSupremo, Camponez, Carnevalli, Ccuembej, ChristianH,
Darwinius, Diego UFCG, Dirceu Júnior, Dobau, E2m, EduM, Eparente, Eric Duff, Fabiano Tatsch, Fernando Mussio, Filosoficos, Firmo, Garoto burns, Gbiten, Ghisi.cintia, JoaoMiranda,
Joaosilvakle, Josehneto, Josepojr, Kaze Senshi, LeonardoG, LeonardoRob0t, Malafaya, Manuel Anastácio, Marcelo Reis, Mauro schneider, Nuno Tavares, OS2Warp, Osias, PatríciaR, Pedro7x,
Rafaelcosta1984, Ricardo Ferreira de Oliveira, Rod, Ruy Pugliesi, Salgueiro, Stuckkey, Sturm, Thiagoharry, Vini 175, Viniciusmc, 155 edições anónimas
Algoritmo de busca Fonte: http://pt.wikipedia.org/w/index.php?oldid=25974053 Contribuidores: Giro720, Salgueiro, 4 edições anónimas
Busca linear Fonte: http://pt.wikipedia.org/w/index.php?oldid=24881625 Contribuidores: Darwinius, FML, Jonas AGX, Josehneto, Leslie, Manuel Anastácio, Nuno Tavares, Steinlh,
Thegoergen, Thiagoharry, 10 edições anónimas
Pesquisa binária Fonte: http://pt.wikipedia.org/w/index.php?oldid=27447620 Contribuidores: Agil, Alvaromenezes, Anderson90, Andrevruas, Brunosmm, CommonsDelinker, Cralize,
Diegotremper, EduM, Eng.joseandro, Epinheiro, FML, GOE, Giro720, Gökhan, Jonas AGX, Kaze Senshi, Marivb, Nuno Tavares, OS2Warp, Ozymandias, Rafael.afonso, Ricardo Ferreira de
Oliveira, Steinlh, Thiagoharry, 95 edições anónimas
61
Imagem:Insertion sort animation.gif Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Insertion_sort_animation.gif Licença: Creative Commons Attribution-Sharealike 2.5
Contribuidores: Nuno Nogueira (Nmnogueira)
Imagem:Selection sort animation.gif Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Selection_sort_animation.gif Licença: Public Domain Contribuidores: en:Marco Polo at
en.wikipedia.org
Imagem:Bubble sort animation.gif Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Bubble_sort_animation.gif Licença: Creative Commons Attribution-Sharealike 2.5
Contribuidores: Original uploader was Nmnogueira at en.wikipedia
Ficheiro:Bubblesort.png Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Bubblesort.png Licença: Public Domain Contribuidores: Original uploader was Thiagoharry at pt.wikipedia
Ficheiro:Insertion_sort_animation.gif Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Insertion_sort_animation.gif Licença: Creative Commons Attribution-Sharealike 2.5
Contribuidores: Nuno Nogueira (Nmnogueira)
Image:Selection sort animation.gif Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Selection_sort_animation.gif Licença: Public Domain Contribuidores: en:Marco Polo at
en.wikipedia.org
Ficheiro:Selection-Sort-Animation.gif Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Selection-Sort-Animation.gif Licença: GNU Free Documentation License Contribuidores:
en:Joestape89
Image:Sorting quicksort anim.gif Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Sorting_quicksort_anim.gif Licença: Creative Commons Attribution-ShareAlike 3.0 Unported
Contribuidores: Wikipedia:en:User:RolandH
Ficheiro:Quicksort example small.png Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Quicksort_example_small.png Licença: Public Domain Contribuidores: Maksim, 1 edições
anónimas
Ficheiro:Busca sequencial.png Fonte: http://pt.wikipedia.org/w/index.php?title=Ficheiro:Busca_sequencial.png Licença: Public Domain Contribuidores: Original uploader was Thiagoharry at
pt.wikipedia
62
Licença
Licença
Creative Commons Attribution-Share Alike 3.0 Unported
//creativecommons.org/licenses/by-sa/3.0/
63

Elementos de Apoio Pesquisa e Ordenação 2011

Transcrição

Documentos relacionados

Bubble sort

Os 40 alunos de uma turma foram muito mal em uma prova. O

Lista 3

MedBook - Medsky

ee 540 - exercício em classe 03

MOSAICOS RECURSO DIDÁTICO Software Geogebra (http://www

02 de Março de 2016 ICSA - UFOP Rua do Catete,166

Carta de solicitação de emprestimo

Baixar este arquivo PDF - Revista Eletrônica Unicruz

MÉTODO DO PARALELOGRAMO