adicionando o RadixSort

[ErickMVdO]

Fiz algumas mudanças para encaixar nos parâmetros passados na main, mas ta tudo funcionando.

[ErickMVdO]

Problemas resolvidos!

[ErickMVdO]

Corrigido!

[bcribas]

Para um arquivo com 1024 elementos ordenados de maneira reversa:

$ ./radixsort < input/10-reverso 
double free or corruption (out)
Aborted

Log do valgrind:

==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109A25: radixsort (radixsort.c:113)
==133574==    by 0x109203: main (main.c:28)
==133574== 
==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109A86: radixsort (radixsort.c:117)
==133574==    by 0x109203: main (main.c:28)
==133574== 
==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109AE7: radixsort (radixsort.c:121)
==133574==    by 0x109203: main (main.c:28)
==133574== 
==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109B48: radixsort (radixsort.c:125)
==133574==    by 0x109203: main (main.c:28)
==133574== 
==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109BA9: radixsort (radixsort.c:129)
==133574==    by 0x109203: main (main.c:28)
==133574== 
==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109C0A: radixsort (radixsort.c:133)
==133574==    by 0x109203: main (main.c:28)
==133574== 
==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109C6B: radixsort (radixsort.c:137)
==133574==    by 0x109203: main (main.c:28)
==133574== 
==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109CCC: radixsort (radixsort.c:141)
==133574==    by 0x109203: main (main.c:28)
==133574== 
==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109D2D: radixsort (radixsort.c:145)
==133574==    by 0x109203: main (main.c:28)
==133574== 
==133574== Conditional jump or move depends on uninitialised value(s)
==133574==    at 0x109D8E: radixsort (radixsort.c:149)
==133574==    by 0x109203: main (main.c:28)
==133574== 

Agora vou deixar você descobrir ;)

Outra coisa importante é que o sizeof dos mallocs devem ser de Item e não de int, para garantir que sempre vai fazer o malloc certo, por exemplo caso o Item seja um long.

E também no radixsort.h trocar o primeiro ifdef e define por outra coisa, por exemplo __radixsortH__, pois do jeito que está conflita com o define feito pelo Makefile e que é utilizado pelo main.h.

[]s

[ErickMVdO]

Fiz alguns testes aqui, e para os valores acima de 1000 ordenado ou 1018 ordenado de forma reversa o código realmente está quebrando. Porém, quando eu tiro a sequência de free isso para de acontecer. Sabe o por quê?

[bcribas]

Fiz alguns testes aqui, e para os valores acima de 1000 ordenado ou 1018 ordenado de forma reversa o código realmente está quebrando. Porém, quando eu tiro a sequência de free isso para de acontecer. Sabe o por quê?

A dica está no log do valgrind, os seus laços nas linhas 113 até 149 dependem de valores não inicializados. Lembre que o malloc não inicializa o vetor, então é incerto o que tem lá dentro. E no caso pode acontecer de algum dos vetores não possuir 0 e aí você está corrompendo estruturas que armazenam informações de malloc (por isso o problema fica evidente com o free). Além disso o vetor vai precisar ser 1 elemento maior que (n-l+1) para garantir que vai ter um 0 no fim do vetor, senão os seus laços podem não parar em um vetor v que possua todos os elementos repetidos.

A implementação da parte de "reagrupamento" dos vetores dividos possui como premissa algo que não é correto, e em geral usamos '\0' para representar um char de valor 0, os vetores são do tipo Item, a comparação deveria ser com 0.

Arrumando a comparação, explicada acima, você precisa resolver o problema do vetor não inicializado, isso pode ser resolvido se trocar o malloc por calloc, mas isso pode ser bem lento, pois o calloc vai fazer algo parecido com um memset no vetor (que essencialmente percorre o vetor inicializando), e com 10 vetores (potencialmente grandes) a penalidade pode ser grande.

Acho que seria mais rápido se você (nas linhas 56 a 105) depois de armazenar o valor já poderia salvar um 0 ao lado, mas isso envolve crescer o tamanho do vetor em 1 posição, pois imagina um vetor que só tenha 1.

[ErickMVdO]

Eu não sabia dessa informação do malloc, mas corrigi o erro seguindo suas dicas

[bcribas]

Eu não sabia dessa informação do malloc, mas corrigi o erro seguindo suas dicas

Faltou uma correção para ter a inicialização do vetor corretamente. Do jeito que o código está pode ser que ele falhe quando for chamado diversas vezes em um código, por conta da não inserção de 0 no final dos vetores.

O efeito é parecido com a do código abaixo:

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
  int *a=malloc(4*sizeof(int));
  for(int i=0;i<4;i++)
  {
    a[i]=3+i;
    printf("%d\n",i);
  }
  free(a);
  a=malloc(4*sizeof(int));
  for(int i=0;i<4;i++)
    printf("%d\n",i);
}

Veja que mesmo fazendo o free e alocando novamente o vetor os valores permanecem inalterados. Essa é a característica do malloc de nào inicializar a região de memória recém-alocada. Em geral funciona nos programas por causa de alguma configuração no Kernel que garante que toda memória alocada pela primeira vez estará zerada (isso é para garantir que um processo não consiga recuperar dados de outros programas).