F�rum O que � quick sort e selection sort(exemplos)? #571007

15/11/2016

Boa tarde!

Tirando algumas d�vidas em v�deos no youtube, entendi que os m�todos de ordena��o quick e selction sort, s�o:

Quick Sort:

� realizada a separa��o um elemento como piv� e assim dividimos os itens nos maiores a direita e menores a esquerda e realizamos a comparativa de i como 1� e j como �ltimo da separa��o e se o item i for menor e j maior que o piv� mantemos no �ndice, se n�o invertemos a sua posi��o.

Selection Sort:

Nesse selecionamos um elemento como exemplo o 1� e fazemos a comparativa do selecionado com todos os outros e ao final mantemos o menor no 1� indice e ap�s realizamos o mesmo processo com o 2� e assim sucessivamente.

Estou correto, poderiam me passar exemplos?

Obrigado!

Phelipe Lopes

Curtir t�pico

+ 0

Responder

Posts

16/11/2016

Vagner Carvalho

Boa noite.
Eu tenho esse c�digo como exemplo em Object Pascal.
Fiz para a disciplina de estrutura de dados na faculdade.

{}
Program estrutura_de_dados;

uses crt;
const 
		inicio = 1; 
		max = 10;
type 
	vetor = array [inicio..max] of integer;
	
var	
	V: vetor;
	i,a,cod: integer;
	saida: string;
	
procedure quick_sort(var V:vetor; inicio:integer; max:integer);
var 
	i,j,aux,meio:integer;
begin
	i:=inicio;
    j:=max;
    meio:=V[(inicio + max) div 2];
    while(i < j)do begin
		while(V[i] < meio)do begin
				i:=i + 1;
			end;
				while(V[j] > meio)do begin
					j:=j - 1;
				end;
					if(i <= j)then begin
						aux:= V[i];
                        V[i]:=V[j];
                        V[j]:=aux;
                        i:=i + 1;
                        j:=j - 1;
					end;
                end;
                if(j > inicio)then begin
                        quick_sort(V, inicio, j);
                end;
                if(i < max)then begin
                        quick_sort(V, i, max);
                end;
end;

procedure insertion_sort(V:vetor; n: integer);
var
	x,j:integer;	
begin
	for j := n - 1 downto 1 do
	begin
		x := V[j];
		i := j + 1;
		while (i <= n) and (x > V[i]) do
		begin
			V[i - 1] := V[i];
			inc(i);
		end;
			V[i - 1] := x;
	end;
	writeln;
	write('Os elementos classificados s�o os seguites: ');
	writeln;
	writeln;
	for i:=1 to n do
	begin
		write(V[i],' ');
	end;
	writeln;	
end;

function binaria (V: vetor; k,n: integer): boolean;
var
	achou: boolean;
	inicio, meio, fim, pos: integer;
begin
	inicio:= 1;
	fim:= n;
	achou:= false;
	pos:= 0;
	repeat
		meio:= (inicio + fim) div 2;
		if (V[meio] > k) then
			fim:= meio -1
		else
			if (V[meio] < k) then
				inicio:= meio + 1
			else
				begin
					pos:= meio;
					achou:= true;
				end;
	until achou or (inicio > fim);
	binaria:= achou;	
end;

function sequencial (V:vetor; k,n:integer):boolean;
var
	achou: boolean;
	i,pos: integer;
begin
	achou:= false;
	pos:= 0;
	i:= 1;
	repeat
		if (V[i] = k) then
			begin	
				pos:= i;
				achou:= true;
			end
			else
				i:= i + 1;
	until achou or (i > n);
	sequencial:= achou;	
end;

Begin
	for i:= 1 to max do
	begin
		write('Informe os valore: ');
		readln(V[i]);
	end;
	repeat
		writeln;
		writeln(' 1 = quick sort');
		writeln(' 2 = insertion sort');
		writeln(' 3 = busca binaria');
		writeln(' 4 = busca sequencial');
		writeln;
		write('Informe o c�digo da busca: ');
			readln(cod);
			if (cod = 1) then
			begin
				quick_sort(V,inicio,max);
				writeln;
				for  i:= 1 to max do 
				begin
					write(V[i],' ');
				end;
					readkey;
					writeln;
				end;
			if (cod = 2) then	
			begin
				insertion_sort(V,max);
			end;
			if (cod = 3) then	
			begin
				writeln;
				write('Informe o n�mero que deseja verificar: ');
				readln(a);
				writeln;
				writeln('A informa��o �: ',binaria(V,a,max));
			end;
			if (cod = 4) then
			begin
				writeln;
				write('Informe o n�mero que deseja verificar: ');
				readln(a);
				writeln;
				writeln('A informa��o �: ',sequencial(V,a,max));			
			end		   
			else 
				if (cod >=5) or (cod <= 0) then
				begin
					writeln;
					writeln('Codigo invalido.');
				end;		
			writeln;  
			write('Deseja fazer outra busca? Sim ou n�o = N: ');
		 	readln(saida);
 	  until saida = 'N';
End.

Responder

Gostei + 0

16/11/2016

Vagner Carvalho

Quick sort

Program quick_sort;
uses crt;
const 
		inicio = 1; 
		max = 10;
type 
	vetor = array [inicio..max] of integer;
	
var	
	V: vetor;
	i: integer;
	
procedure quick_sort(var V:vetor; inicio:integer; max:integer);
var 
	i,j,aux,meio:integer;
begin
	i:=inicio;
    j:=max;
    meio:=V[(inicio + max) div 2];
    while(i < j)do begin
		while(V[i] < meio)do begin
				i:=i + 1;
			end;
				while(V[j] > meio)do begin
					j:=j - 1;
				end;
					if(i <= j)then begin
						aux:= V[i];
                        V[i]:=V[j];
                        V[j]:=aux;
                        i:=i + 1;
                        j:=j - 1;
					end;
                end;
                if(j > inicio)then begin
                        quick_sort(V, inicio, j);
                end;
                if(i < max)then begin
                        quick_sort(V, i, max);
                end;
end;


Begin
	for i:= 1 to max do
	begin
		write('Informe os valore: ');
			readln(V[i]);
	end;
	quick_sort(V,inicio,max);
	writeln;
	for  i:= 1 to max do 
	begin
          write(V[i],' ');
    end;
    readkey;
End.

Responder

Gostei + 0