A Lista de Ordenação 3 Quick e Heap Sort

Universidade Federal de Goiás[pic 1][pic 2]

Instituto de Informática

Estrutura de Dados

Prof. Ronaldo Martins da Costa

Prof. Rogério Lopes Salvini

Tutora: Priscila Marques Kai

Aluno: Vinicius Ribeiro Parreira

Matrícula: 201800813

Lista de Ordenação 3

Quick e Heap Sort

1. Considere o vetor A contendo a seguinte sequência de números: 5, 13, 7, 20, 12, 9, 1, 4, 18, 3. Faça a ordenação em ordem crescente utilizando o Quick Sort, apresentando a sequência dos números a cada passo (teste de mesa).

2. Algumas implementações do quickSort sempre usam um [i] como pivô. Dê um exemplo de um vetor de entrada de comprimento n em que tal implementação realizaria n 2 comparações.

3. Escreva um algoritmo em linguagem C que faça a ordenação de uma lista de nomes utilizando o Quick Sort.

 

#include <stdio.h>
void quickSort(char vet[10][10], int inicio, int tam){
   int i, j, pivo, trocasQuick = 0;
   char aux[10];
   i = inicio;
   j = tam - 1;
   pivo = vet[(inicio + tam) / 2][0];
   while (i <= j){
       while (vet[i][0] < pivo && i < tam){
           i++;
       }
       while (vet[j][0] > pivo && j > inicio){
           j--;
       }
       if (i <= j){
           strncpy(aux, vet[i], 10);
           strncpy(vet[i], vet[j], 10);
           strncpy(vet[j], aux, 10);
           i++;
           j--;
           trocasQuick += 1;
       }
   }
   if (j > inicio){
       quickSort(vet, began, j + 1);
   }
   if (i < tam){
       quickSort(vet, i, tam);
   }
}

int main(){
   char vetor[10][10] = {"Luiz","Alberto","Eduardo","Carlos","Vinicius","Xavier","Veronilson","Xander","Zorro","Daniel"};
   quickSort(vetor, 0, 10);
   for(int i = 0; i < 10; i++){
       printf("%s\n", vetor[i]);
   }
   return 0;
}

4. Ilustre a operação de HEAPSORT sobre o arranjo A = 〈5, 13, 2, 25, 7, 17, 20, 8, 4〉.

Vetor A = {5, 13, 2, 25, 7, 17, 20, 8, 4}

1)                                5

                              /   \

                            13     2

                            / \   / \

                           25  7 17 20

                          /  \

                         8    4

2)

                                5

                              /   \

                            25     2

                            / \   / \

                           13  7 17 20

                          /  \

                         8    4

3)

                                5

                              /   \

                            25     20

                            / \   / \

                           13  7 17  2

                          /  \

                         8    4

4)

                               25

                              /   \

                             5     20

                            / \   / \

                           13  7 17  2