1
Equipe: Ítalo Otávio Cardoso Matos
Marco Túlio Maia de Moraes
Marcos Leandro Pinto Moura
Professora: Janine Fabiana Prates Teixeira Oliveira
Disciplina: AEDS II
04 de setembro de 2023
Algoritmo de Ordenação Shell Sort
O Shell Sort se trata de um algoritmo de ordenação por comparação criado por Donald
Shell em 1959. Esse método é uma variação de um outro algoritmo chamado Insertion Sort, e
funciona basicamente realizando comparações entre um elemento de um vetor e outro que está
em um intervalo H de distância desse elemento. Esse intervalo é, normalmente, determinado pelo
resultado da divisão do tamanho do vetor por 2, em seguida, após percorrer todo o vetor
realizando comparações, dividimos o intervalo H por 2 novamente, e assim fazemos até que H
seja igual a 1, nesse momento, o algoritmo se torna muito parecido com o Insertion Sort (daí
tiramos a comparação feita inicialmente com esse outro algoritmo), e então o vetor é
completamente organizado.
EXPLICAÇÃO DO CÓDIGO
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void number(long int vetor[], int tamanho)
{
2
int i;
int global;
printf("GERAR ATE QUAL NUMERO ?\t");
scanf("%d", &global);
for (i = 0; i < tamanho; i++)
{
vetor[i] = rand() % global; // Gera números aleatórios entre 0 e 'global'
}
}
A função `number` gera números aleatórios e os coloca em um vetor. O usuário define o limite
superior para a geração aleatória.
void crescente(long int vetor[], int tamanho)
{
// Implementação do algoritmo de ordenação Shell Sort em ordem crescente
}
A função `crescente` implementa o algoritmo de ordenação Shell Sort para organizar os números
no vetor em ordem crescente.
void decrescente(long int vetor[], int tamanho)
{
// Implementação do algoritmo de ordenação Shell Sort em ordem decrescente
}
3
A função `decrescente` implementa o algoritmo de ordenação Shell Sort para organizar os
números no vetor em ordem decrescente.
int main()
{
clock_t inicio, fim;
inicio = clock();
srand(time(NULL)); // Inicializa a semente do gerador de números aleatórios
long int vetor[100001];
int global;
int x;
int i;
number(vetor, 100001); // Chama a função para gerar números aleatórios no vetor
printf("\nDIGITE O TAMANHO DESSE VETOR -> 100 - 1.000 - 10.000 - 100.000:\t");
scanf("%d", &global);
printf("\nDIGITE A OPCAO DESEJADA:\n");
printf("1 - VETOR EMBARALHADO\n");
printf("2 - VETOR CRESCENTE\n");
printf("3 - VETOR DECRESCENTE\n\n");
scanf("%d", &x);
switch (x)
{
case 1:
// Exibe o vetor antes de ordenar
break;
4
case 2:
crescente(vetor, global); // Chama a função para ordenar o vetor em ordem crescente
printf("\n\nVETOR ORDENADO EM CRESCENTE\n\n");
for (i = 0; i < global; i++)
{
printf(" [%ld]\t", vetor[i]);
}
break;
case 3:
decrescente(vetor, global); // Chama a função para ordenar o vetor em ordem decrescente
printf("\n\nVETOR ORDENADO EM DECRESCENTE\n\n");
for (i = 0; i < global; i++)
{
printf(" [%ld]\t", vetor[i]);
}
break;
default:
printf("\n\n!!!OPCAO INVALIDA!!!\n\n");
}
fim = clock();
double tempo_execucao = (double)(fim - inicio) / CLOCKS_PER_SEC;
printf("\n\nO PROGRAMA LEVOU %.2f SEGUNDOS PARA SER EXECUTADO.\n",
tempo_execucao);
return 0;
5
}
O `main` é a função principal do programa. Aqui, o usuário escolhe entre embaralhar o vetor,
ordená-lo em ordem crescente ou ordená-lo em ordem decrescente. Dependendo da escolha do
usuário, a função apropriada é chamada (crescente ou decrescente). Em seguida, o programa
exibe o vetor resultante e mede o tempo de execução do processo.
Além disso, o programa usa a função `clock` para medir o tempo de execução e exibe esse tempo
no final.
É importante observar que o código tem um limite superior fixo para o tamanho do vetor
(100001), então o usuário pode escolher o tamanho do vetor apenas entre as opções predefinidas
(100, 1000, 10000 ou 100000).
COMPARAÇÃO DE RESULTADOS
Número limite Quantidade de Tempo de
números resposta (média)
100 100 3.5s
Vetor aleatório 1.000 1.000 4.5s
100.000 100.000
100 100
Vetor crescente 1.000 1.000
100.000 100.000
100 100
Vetor 1.000 1.000
decrescente
100.000 100.000