Shell Sort - Algoritmo de Ordenação - EDA2 a3

[@ikeborges]

Professor, ali no while do insertionsortH tem duas condições, ao implementar meu programar inverti as duas e estava dando SegFault para vetores com mais de 32762 itens. Ao fazer exatamente na ordem do vídeo funcionou normalmente. Sabe me explicar pq a condição j >= l + h teve de vir primeiro para que o programa rodasse normalmente?

[@ikeborges]

Opa! Analisei melhor e entendi. Caso essa condição não fosse a primeira, daria problema na comparação less(tmp, v[j - h]), daí o SegFault kkkkkk.

[@erickgiffoni1276]

Vetor de 50,000 posições Tempo de execução shell sort: 0.006816 segundo(s) Bem rapidinho

[@ProfBrunoRibas]

Oi Erick, como está contando o tempo? Para 50k posições esse valor está muito baixo, estamos imaginando em algo entre 0,5s e 1s em uma máquina moderna com clock de 4GHz. E mesmo compilando com -O2 estamos falando de algo entre 0,17s e 0,32s

[@erickgiffoni1276]

@@ProfBrunoRibas Estou fazendo assim, prof : clock_t clicks = clock(); shellSort(vet, 0, tamanho - 1); clicks = clock() - clicks; Nessa ordem exata ai. Logo depois um printf usando %f para imprimir o tempo em segundos, assim : printf(" Tempo de execucao shell sort: %f segundos ", (float)clicks / CLOCKS_PER_SEC); Será que tem algo não muito correto ? Peguei a referência aqui: www.cplusplus.com/reference/ctime/clock/ Uso a srand( time(NULL) ) para gerar uma semente e a rand() para preencher o vet.

[@ProfBrunoRibas]

Salve Erick! A diferença está na maneira de contar o tempo! O clock(), do jeito que você fez está correto e está considerando o tempo aproximado em que parte do seu programa ficou dentro da CPU em execução, o número não é preciso mas é uma ótima aproximação. E dessa maneira também está descontando o tempo de impressão e de leitura do vetor, o que deixa mais justo o tempo calculado. O que eu estou calculando é o tempo total, de leitura, ordenação e impressão do vetor. O tempo fica um pouco maior. No entanto, os números que te passei antes estavam equivocados :) Tenho aqui na minha máquina os tempos variando de 0,013s e 0,018s para vetores de 50k elementos com o shellsort implementado tal como na aula. Valores esses consideranto tudo. Nesse caso um vetor de 50k elementos para o shellsort já não é mais problema! :) Vamos elevar para 100k e quem sabe até 1kk. []s

[@erickgiffoni1276]

@@ProfBrunoRibas Boa, professor ! Excelente consideração ! Obrigado !

[@iagodelima8598]

Nossa, na minha cabeça esse é o pior algoritmo. Se fosse para chutar eu falaria que essa função é a mais lenta kkk.