Lista de Projeto de algoritmos

Lista do dia das Crianças

Questão 28 :

O Quick Sort utiliza a técnica de dividir e conquistar. Na fase de dividir, ele pega qualquer um elemento do vetor, chamado de pivô, e reorganiza os elementos uma forma que os elementos do lado esquerdo do pivô sejam menores ou iguais aos elementos da direita, assim ele vai dividindo até não ser mais necessário. Esse processo é chamado de particionamento. Na fase de conquista, ordenamos recursivamente o lado esquerdo e o lado direito do pivô. Dessa forma, nada é feito na fase de combinação, porque o vetor já está ordenado.

Resumindo, o Quick Sort não tem fase de combinação porque ele no momento em que ele divide o vetor, já ordena, tornando a fase de combinação inútil.

Questão 29:

        Para evitar o pior caso do Quick Sort, deve-se pegar o seu pivô no meio do vetor, para que a ordenação ocorra de forma mais rápida, pois o seu algoritmo ordena o vetor comparando o pivô com a esquerda e a direita do vetor, sendo assim, sua complexidade fica nlogn. No pior caso, o pivô é pego nas extremidades do vetor, dificultando assim a ordenação, tornando ela em O(n^2).

Questão 30:

- Seleção:

void selecao( int * v)

{

int i,j,min,aux; // Variaveis para o for, o min e o aux para apontar para o vetor

for (i=0; i// Serve para percorrer todo o vetor 

{

min = i; // Aponta o min para a posição que o for esta no momento

for (j=i+1; j< max; j++) // recebe a posição a frente do i esta, apartir desse ponto, percorre todo o vetor.

{ if ( v[j]// Verefica se a posição do j é menor que a posição da variável min.

{min = j;} // caso for verdade, aponta o min para a posição j.

//troca(v[i],v[min]);

aux= v[i]; // A variável aux recebe o conteúdo i

v[i]=v[min]; // A posição i, recebe o conteúdo da posição min do vetor.

v[min]=aux; // A posição min recebe aux como conteúdo.

---

}

}

}

//---------

- Intercalação:

void insercao(int *v)

{ int i, j, x; // Inicialização de variaveis

for (j = 1; j < max; j++) // Percorre todo o vetor

{ x = v[j]; // x recebe o conteúdo do vetor j

i=j-1; // i recebe o índice de j - 1

while((i>=0) && (v[i]> x)) // Enquanto o i for maior e igual a 0 e vetor i for maior que x

{ v[i+1] = v[i];// o vetor de posição i + 1 recebe o conteúdo da posição i 

i=i-1; } // i decrementa

v[i+1] = x; // O conteúdo do vetor i + 1 recebe x como conteúdo.

}

}

- Mergesort :

void sort (int v[], int p, int r )

{

if( p < r - 1 ) // conferir se o vetor ainda não chegou no final

{

int q = ( p + r ) / 2; // calcula a mediana do vetor

sort(v, p, q ); // chamando recursivamente a mesma função

sort(v, q, r ); //  chama a mesma funçao

merge(v, p, q, r ); // chama a função intercalo

}

}

- Particiona :

int partition(int *v, int p,int r)

{ int pivo,i,j; // declarando variáveis

pivo=v[p]; // o pivô aponta para esquerda do vetor

i=p;

j=r+1;

while (1) //  enquanto for verdadeiro 

{

while(v[++i]<= pivo) // percorre o vetor da esquerda ate o pivo

{ if( i==r) break;} // se a posição i for igual a ultima posição do vetor da um break

while(v[--j]>pivo)  //  percorre o vetor da direita ate o pivo

{ if( j==p) break;} se a posição j for igual a ultima posição do vetor da um break

if ( i >=j) // se o lado esquerda for maior ou igual ao lado direito da um break