Comparação dos métodos de ordenação Quicksort e Heapsort

[jhon.sys]

Pessoal, alguém poderia me ajudar a resolver o seguinte exercício. Encontrei alguns modelos no site www.mathworks.com. Mas preciso resolver este exercícios: Alguém pode me ajudar ????

1) Implemente o método de Ordenação Quicksort, onde a escolha do pivô é sempre o primeiro elemento do vetor, e método de Ordenação Heapsort;

2) Para cada método implementado faça os seguintes testes:

a) gerar vetores de n elementos ORDENADOS EM ORDEM CRESCENTE, com n variando de 1000 até 10.000, com intervalo de 1000;

Ordenar esses vetores com ambos os métodos e computar o número de comparações realizadas;

b) gerar vetores de n elementos ORDENADOS EM ORDEM DECRESCENTE, com n variando de 10.000 até 100.000, com intervalo de 10.000;

Ordenar esses vetores com ambos os métodos e computar o número de comparações realizadas;

c) gerar vetores de n elementos ALEATÓRIOS, com n variando de 10.000 até 100.000, com intervalo de 10.000;

Ordenar esses vetores com ambos os métodos e computar o número de comparações realizadas;

d) Fazer um único gráfico de n x número de comparações levando em consideração os testes realizados.

3) Explique o comportamento dos gráficos gerados;

[jhon.sys]

O que possuo::::

funcao x = heapsort (x)
% ------------------------------------------------- -------------------------
% Sintaxe: sx = heapsort (x);
%			  
% Entradas: x é um vetor de comprimento n
%			  
% Saídas: sx é o (ascendente) versão do x classificadas
%			  
% Descrição: Essa função ordena o array de entrada x em ordem crescente
% Usando o algoritmo heapsort
%			  
% Complexidade: O (log n * (n)) o melhor desempenho caso
(* Log n (n))% O desempenho médio-case
Desempenho% O (log n * (n)) no pior caso
% O (1) espaço auxiliar
%			  
% Autor: Brian Moore
% Brimoor@umich.edu
%			  
% Data: 05 de janeiro de 2014
% ------------------------------------------------- -------------------------

Construa% max-heap a partir de x
n = comprimento (x);
x = buildmaxheap (x, n);

% Heapsort
HEAPSIZE = n;
para i = n: -1:2
Put% (n + 1 - i) ª maior elemento no lugar
x = swap (x, 1, i);

% Max-heapify x (1: heapsize)
heapsize = heapsize - 1;
x = maxheapify (x, 1, HEAPSIZE);
final

final

funcao x = buildmaxheap (x, n)
Construa% max-heap de x
% Nota: Na prática, x xhould ser passados ??por referência

para i = andar (n / 2): -1:1
% Coloque filhos de x (i), a fim max-heap
x = maxheapify (x, i, n);
final

final

funcaoo x = maxheapify (x, i, heapsize)
% Coloque filhos de x (i), a fim max-heap
% Nota: Na prática, x xhould ser passados ??por referência

% Cálculo crianças esquerda / direita índices
ll = 2 * i; % Nota: Na prática, usar o deslocamento bit esquerda
rr = ll + 1; % Nota: Na prática, usar o deslocamento bit à esquerda, em seguida, adicione 1 a LSB

% Max-heapify
if ((ll <= heapsize) && (x (II)> x (i)))
maiores = ll;
outro
O maior = i;
final
if ((rr <= heapsize) && (x (rr)> x (maior)))
maiores = rr;
final
se (maior ~ = i)
x = swap (x, i, maior);
x = maxheapify (x, maior, heapsize);
final

final

funcao x = swap (x, i, j)
% Permuta x (i) e x (j)
% Nota: Na prática, x xhould ser passados ??por referência

val = x (i);
x (i) = x (j);
x (j) = val;

final

funcao x = quicksort (x)
% ------------------------------------------------- -------------------------
% Sintaxe: sx = quicksort (x);
%			  
% Entradas: x é um vetor de comprimento n
%			  
% Saídas: sx é o (ascendente) versão do x classificadas
%			  
% Descrição: Essa função ordena o array de entrada x em ordem crescente
% Usando o algoritmo quicksort
%			  
% Complexidade: O (log n * (n)) o melhor desempenho caso
(* Log n (n))% O desempenho médio-case
% O desempenho (n ^ 2) no pior caso
% O (log (n)) espaço auxiliar (pilha)
% ------------------------------------------------- -------------------------

% Maçanetas
kk = 15; % Limite de Inclusão tipo, kk> = 1

% Quicksort
n = comprimento (x);
x = quicksorti (x, 1, n, kk);

final

funcao x = quicksorti (x, ll, uu, kk)
Ordenar% x (ll: uu) via classificação rápida
% Nota: Na prática, x xhould ser passados ??por referência

% Selecione pivô e dados de partição em torno dele
[X mm] = particao (x, ll, uu);

% Divide e conquista
if ((mm - ll) <= kk)
Ordenar% x (ll: (mm - 1)), através de ordenação por inserção
x = insertionsorti (x, ll, mm - 1);
outro
Ordenar% x (ll: (mm - 1)), através de classificação rápida
x = quicksorti (x, ll, mm - 1, kk);
final
if ((uu - mm) <= kk)
Ordenar% x ((mm + 1): uu) via ordenação por inserção
x = insertionsorti (x, mm + 1, uu);
outro
Ordenar% x (mm (+ 1): uu) através de classificação rápida
x = quicksorti (x, mm + 1, uu, kk);
final

final

funcao [x mm] = particao (x, ll, uu)
Partition% x (ll: uu) em torno do índice mm
% Nota: Na prática, x xhould ser passados ??por referência

% ------------------------------------------------- -------------------------
% Selecionar pivot
% ------------------------------------------------- -------------------------
% Método 1: pivô Median-of-3
pp = medianofthree (x, ll, uu); indice pivo % Mediana-de-três

% Método 2: pivô Aleatório
% Pp = randi ([ll uu]); % Índice de pivô Aleatório
% ------------------------------------------------- -------------------------

Partition% em torno do pivô
x = swap (x, ll, pp);
mm = ll;
para j = (ll + 1): uu
if (x (j) <x (II))
	mm = mm + 1;
	x = swap (x, mm, j);
final
final
x = swap (x, ll, mm);

final

funcao pp = medianofthree (x, ll, uu)
% Compute mediana de {x (II), x (mm), x (uu)}
% Nota: Na prática, x xhould ser passados ??por referência

% Elemento Médio (evitando overflow)
mm = ll + floor ((uu - ll) / 2);

% Compute mediana de {x (II), x (mm), x (uu)}
if (x (II) <= x (mm))
se (x (t) a> = x (mm))
	pp = mm;
elseif (x (uu)> = x (II))
	pp = uu;
outro
	pp = ll;
final
outro
if (x (uu)> = x (II))
	pp = ll;
elseif (x (uu)> = x (mm))
	pp = uu;
outro
	pp = mm;
final
final

final

funcao x = insertionsorti (x, ll, uu)
Ordenar% x (ll: uu) via ordenação por inserção
% Nota: Na prática, x xhould ser passados ??por referência

% Tipo de Inclusão
para j = (ll + 1): uu
pivo = x (j);
i = j;
while ((i> ll) && (x (i - 1)> pivo))
	x (i) = x (i - 1);
	i = i - 1;
final
x (i) = pivo;
final

final

funcao x = swap (x, i, j)
% Permuta x (i) e x (j)
% Nota: Na prática, x xhould ser passados ??por referência

val = x (i);
x (i) = x (j);
x (j) = val;

final

Alguem poderia me ajudar ????

[Rui Carlos]

Era boa ideia, em vez de copiares enunciados, e de mostrar um bloco de código enorme (que não me parece que compile sequer em Matlab), focares-te em dúvidas específicas que tenhas.