Depois de
implementar seu algoritmo na linguagem de programcao de sua escolha, analize as
implementacoes abaixo e discuta o tempo aproximado de execucao, o melhor e pior
caso e possiveis otimizacoes.
void Bubble()
{
int len=strlen(str);
for(int
l=len-1;l>0;l--)
for(int i=0;i<l;i++)
if(str[i]>str[i+1])
{
char temp=str[i];
str[i]=str[i+1];
str[i+1]=temp;
}
}
void Sort()
{
int start=0;
int len=strlen(str);
while(start<len-1)
{
char *csr=str+start+1;
int smallestIndex=start;
while(*csr!=0)
{
if(*csr<str[smallestIndex]) smallestIndex=csr-str;
csr++;
}
if(smallestIndex!=start)
{
char temp=str[start];
str[start]=str[smallestIndex];
str[smallestIndex]=temp;
}
start++;
}
}
void quickSort(int
start,int end)
{
if(end-start==1)
{
if(str[start]>str[end])
{
char tmp=str[start];
str[start]=str[end];
str[end]=tmp;
}
}
else if(end-start<1) return;
int i=start+1;
int j=end;
do
{
while(i<end && str[i] < str[start]) i++;
while(str[j] > str[start]) j--;
if(i<=j)
{
char tmp=str[i];
str[i]=str[j];
str[j]=tmp;
i++;j--;
}
} while (i<j);
char tmp=str[i-1];
str[i-1]=str[start];
str[start]=tmp;
quickSort(start,j);
quickSort(i,end);
}
Quais as
caracteristicas das implementacoes abaixo?
#define NUM_CARDS 52
// To simulate an almost
real, but perfect shuffling
void shuffle(int
cards[NUM_CARDS],int newCards[NUM_CARDS])
{
for(int t=0;t<NUM_CARDS/2;t++)
{
newCards[t*2]=cards[t];
newCards[t*2+1]=cards[t+NUM_CARDS/2];
}
}
// To optimize shuffling
void shuffle(int
cards[NUM_CARDS])
{
srand(time(NULL));
for(int t=0;t<NUM_CARDS;t++)
{
int card1=(int)((rand()/(double)RAND_MAX)*NUM_CARDS);
int card2=(int)((rand()/(double)RAND_MAX)*NUM_CARDS);
int tmp=cards[card1];
cards[card1]=cards[card2];
cards[card2]=tmp;
}
}
void * __cdecl memcpy (
void * dst,
const void * src,
size_t count
)
{
void * ret = dst;
/*
* copy from lower addresses to higher
addresses
*/
while (count--) {
*(char *)dst = *(char *)src;
dst = (char *)dst + 1;
src = (char *)src + 1;
}
return(ret);
}
Comente o que acontece quando as areas de memoria se sobrepoe, qual a
funcao da palavra reservada ‘const’ na declaracao da funcao, o que acontecera
se removermos o ‘const’?
Antes de
estudar a implementacao abaixo, pense como resolver o problema de preservar o
conteudo da area de origem quando esta se sobrepoe a area de destino.
void * __cdecl memmove (
void * dst,
const void * src,
size_t count
)
{
void * ret = dst;
if (dst <= src || (char *)dst >=
((char *)src + count)) {
/*
* Non-Overlapping Buffers
* copy from lower addresses to
higher addresses
*/
while (count--) {
*(char *)dst = *(char
*)src;
dst = (char *)dst + 1;
src = (char *)src + 1;
}
}
else {
/*
* Overlapping Buffers
* copy from higher addresses
to lower addresses
*/
dst = (char *)dst + count - 1;
src = (char *)src + count - 1;
while (count--) {
*(char *)dst = *(char
*)src;
dst = (char *)dst - 1;
src = (char *)src - 1;
}
}
return(ret);
}
Comente o
tempo estimado de execucao para as operacoes de insercao e remocao do elemento
no topo da fila.
Dica: o
melhor algoritmo ‘e O(n).
Comente se
‘e possivel determiner qual o elemento duplicado.
Determine a
estrutura de dados e o no que serao utilizados na implementacao.
ASCII tem o
comprimento de um byte com o bit mais significativo zerado e Kanji tem o
comprimento de 2 bytes com o bit ais significativo do primeiro byte setado.
Tente utilizar a maior parte da memoria possivel.