C QuickSort com resultado errado!

Lobarinhas · 30 de abril de 2020

Tarde boa para todos!

To quebrando a cabeça brincando com C só pra ver se ainda consigo arranhar algo!

O exercício é: "Leia 3 valores inteiros e ordene-os em ordem crescente. No final, mostre os valores em ordem crescente, uma linha em branco e em seguida, os valores na sequência como foram lidos."

Meu código é:

#include <stdio.h>
#include <math.h>

void quick(int vet[], int esq, int dir){
    int pivo = esq, i,ch,j;         
    for(i=esq+1;i<=dir;i++){        
        j = i;                      
        if(vet[j] < vet[pivo]){     
            ch = vet[j];               
            while(j > pivo){           
                vet[j] = vet[j-1];      
                j--;                    
            }
            vet[j] = ch;               
            pivo++;                    
        }
    }
    if(pivo-1 >= esq){              
        quick(vet,esq,pivo-1);      
    }
    if(pivo+1 <= dir){              
        quick(vet,pivo+1,dir);      
    }
 }
 
 
 	main()
{
	int i, num[64], esq, dir;
	
		for (i = 0; i < 3; i++)
	{
		scanf("%d", &num[i]);
	}
	
		quick (num, esq, dir);
		
			
		for (i = 0; i < 3; i++)
	{
		printf("\n%d", &num[i]);
	}
	

	
	return(0);

}

O problema aqui é que ele me retorna valores de 7 digitos meio aleatorios ... não são os que eu entro

Eu primeiro arrisquei o insertion sort mas o resultado nao mudou ... tentei chamar a função em outro lugar (entre os for) mas também nao mudou ...
E eu to fazendo esse exercicio "simples" em sort porque eu qro aprender um pouco mais sobre esses métodos de ordenação e mesmo os próprios métodos, só pra ajudar a ter mais opções na hora de programar!

É isso, quem puder ajudar, agradeço

Matheus Maldi · 30 de abril de 2020

Primeiro faça o teste com hardded code em vez de ficar fazendo scanf, isso vai acelerar o teste

int main()
{	
  	int vet[5] = { 5, 4, 3, 2, 1 };
  
  	seu_quick_sort(vet, 0, 4);
  
  	// faça um for para printar o loop  	
  
 	return 0; 
}

adicionado 14 minutos depois

Segue um codigo simples do quick sort para int:

void quick_sort_int (int* array, int i_lo, int i_hi)
{
    int lo = i_lo, hi = i_hi;
    int mid = array[((lo + hi) >> 1)];
    do
    {
        while (array[lo] < mid)
            ++lo;
        while (array[hi] > mid)
            --hi;

        if (lo <= hi)
        {
            int temp = array[lo];
            array[lo] = array[hi];
            array[hi] = temp;
            lo++;
            hi--;
        }
    } while (lo < hi);
    if (hi > i_lo)
        quick_sort_int (array, i_lo, hi);
    if (lo < i_hi)
        quick_sort_int (array, lo, i_hi);
}

e agora um código extremamente complexo de quicksort genérico, este codigo faz:

Usa insertion_sort caso o range a ser ordenado é menor que 128 (ganha um pouco de perforçance)

Seleciona entre index menor, meio e maior, qual será o pivo.

Consegue evitar varias chamadas recursivas.

static inline void swap (void* l, void* r, size_t size)
{
    if (size == sizeof(__int64_t))
    {
        __int64_t temp = *(__int64_t*)l;
        *(__int64_t*)l = *(__int64_t*)r;
        *(__int64_t*)r = temp;
    }
    else if (size == sizeof(__int32_t))
    {
        __int32_t temp = *(__int32_t*)l;
        *(__int32_t*)l = *(__int32_t*)r;
        *(__int32_t*)r = temp;
    }
    else if (size == sizeof(__int16_t))
    {
        __int16_t temp = *(__int16_t*)l;
        *(__int16_t*)l = *(__int16_t*)r;
        *(__int16_t*)r = temp;
    }
    else if (size == sizeof(__int8_t))
    {
        __int8_t temp = *(__int8_t*)l;
        *(__int8_t*)l = *(__int8_t*)r;
        *(__int8_t*)r = temp;
    }
    else
    {
        char *l_ptr = l, *r_ptr = r;
        do
        {
            char tmp = *l_ptr;
            *l_ptr++ = *r_ptr;
	        *r_ptr++ = tmp;
        } while (--size > 0);
    }
}

static inline void insertion_sort (void* a_lo, void* a_hi, const size_t size_of_element,
    int (*cmp)(const void*, const void*))
{
    for (void* i = a_lo + size_of_element;
        i <= a_hi;
        i += size_of_element)
    {
        for (void* key = i;
            key > a_lo && cmp (key - size_of_element, key) > 0;
            key -= size_of_element)
            swap(key, key - size_of_element, size_of_element);
    }
}

static inline void sort_3 (void* left, void* mid, void* right, const size_t size_of_element,
    int (*cmp)(const void*, const void*))
{
    if (cmp (mid, left) < 0)
        swap (left, mid, size_of_element);
    if (cmp (right, mid) < 0)
        swap (right, mid, size_of_element);
    else
        return;
    if (cmp (mid, left) < 0)
        swap (left, mid, size_of_element);
}

void quick_sort_g (void* restrict address_lo, void* restrict address_hi, const size_t size_of_element,
    int (*cmp)(const void*, const void*))
{
skip_recursive_call:;
    // real len is (address_hi - address_lo) / size_of_element + size_of_element;
    // but is not important here;
    size_t len = (address_hi - address_lo) / size_of_element;
    if (len <= 128)
    {
        insertion_sort (address_lo, address_hi, size_of_element, cmp);
        return;
    }

    register void* a_lo = address_lo;
    register void* a_hi = address_hi;
    register void* mid = address_lo + (len >> 1) * size_of_element;
    sort_3 (a_lo, mid, a_hi, size_of_element, cmp);

    a_lo += size_of_element;
    a_hi -= size_of_element;

    do
    {
        while (cmp (a_lo, mid) < 0)
            a_lo += size_of_element;

        while (cmp (a_hi, mid) > 0)
            a_hi -= size_of_element;

        if (a_lo <= a_hi)
        {
            swap (a_lo, a_hi, size_of_element);
            if (mid == a_lo)
                mid = a_hi;
            else if (mid == a_hi)
                mid = a_lo;

            a_lo += size_of_element;
            a_hi -= size_of_element;
        }
    } while (a_lo < a_hi);

    if (a_hi > address_lo)
    {
        if (a_lo < address_hi)
        {
            quick_sort_g (address_lo, a_hi, size_of_element, cmp);

            address_lo = a_lo;
            goto skip_recursive_call;
        }
        else
        {
            address_hi = a_hi;
            goto skip_recursive_call;
        }
    }
    else if (a_lo < address_hi)
    {
        address_lo = a_lo;
        goto skip_recursive_call;
    }
}

void quick_sort (const void * pbase, size_t total_elems, size_t size,
     int (*cmp)(const void*, const void*))
{
    void *first = (void*)pbase;
    void* last = first + (total_elems - 1) * size;
    quick_sort_g (first, last, sizeof(int), cmp);
}

int intvoidcmp (const void* l, const void* r)
{
    int l_int = *(int*)l;
    int r_int = *(int*)r;
    if (l_int > r_int) return 1;
    if (l_int < r_int) return -1;
    return 0;
}

int main ()
{
    int array_length = 1024 * 1024 * 10;
    int *array = (int*)calloc (array_length, sizeof(int));

    srand (1024);
    for (int i = 0; i < array_length; i++)
        array[i] = rand();
  
      quick_sort (array, array_length, sizeof(int), intvoidcmp);

    for (int i = 1; i < array_length; i++)
        if (array[i - 1] > array[i])
            printf ("Fail %p -> %d\n", &array[i], array[i]);
  
    return 0;
}

isrnick · 30 de abril de 2020

@Lobarinhas No seu main você está passando para a função quick os valores das variáveis esq e dir mas essas variáveis não receberam valor nenhum, então tá mandando algum valor lixo que já estava na memória quando o programa foi executado.