C ordenação de vetores bucket sort

K1_nd3r · 23 de março de 2021

Pessoal boa tarde a todos, gostaria de agradecer antes pois já me ajudaram bastante, mas preciso da força de vocês novamente. Tenho um trabalho onde devo usar o método de ordenação bucket sort para ordenar os vetores que foram e impressos em ordem crescente.Os vetores são divididos em ordem decrescente e ordem aleatória e estes tem tamanho de 100(cem), 1000(mil), 10000(dez mil) e 100000(cem mil) números.O código não acusa erros no compilador mas na hora de rodar a parte que seria das funções ele deixa de responder na mesma hora e o programa para de ser executado, acredito eu no alto de minha energumenidade que seja algum problema com variáveis mas não sei como resolver, e lembrando que o código não está 100% terminado mas o erro não tem relação, acredito eu. Desde já agradeço.

#include <stdio.h>
#include <locale.h>
#include <cstdlib>
#include <stdlib.h>
#include <math.h>
#define TAM 10
struct bucket{
	int qtd;
	int *val;
};
void twogirlsonebucket(int *v, int n, int numbuckets);
void selectionsort(int *bc, int t);

void twogirlsonebucket(int* v, int n, int numbuckets){
	int maior, menor, i, j, numbucket, pos;
	struct bucket *bc;
	maior=menor=v[0];

	//buscador do maior e menor valor
	for(i=1; i<n; i++){
		if(v[i]> maior){
			maior=v[i];
		}
		else if(v[i]<menor){
			menor=v[i];
		}
	}

	//para alocar os baldes no vetor utilizando a quantidade de baldes
	bc = (struct bucket*) malloc(numbucket* sizeof bc);

	//inicializando os baldes com quantidade zero
	for(i=1; i<numbucket; i++){
		bc[i].qtd = 0;

	}
	for(i=1; i<n; i++){

		/*calculando a diferença do número atual com o menor número,
        e dividindo pelo tamanho teremos a posição*/
		pos=(v[i]-menor)/TAM;

		/*as duas linhas a seguir tem a função de armazenar
		os valores aleatóriamente nos baldes para depois serem devidamente armazenados*/
		bc[pos].val[bc[pos].qtd] = v[i];
		bc[pos].qtd++;
	}
	pos=0;
	for(i=1; i<numbucket; i++){

		/*utilizando o método de selection sort
		para ordenar os números nos baldes*/
		selectionsort(bc[i].val, bc[i].qtd);
		for(j=0; j<bc[i].qtd; j++){
			v[pos]=bc[i].val[j];
			pos++;
		}
	}
	free(bc);

}
void selectionsort(int* bc, int t){
	int i, j, menor, troca;
	t= TAM;
	for(i=0; i<t-1; i++){
		menor=i;
		for(j=i+1; j<t; j++){
			if(bc[i]<bc[menor]){
				menor = j;
			}
		}
		if(i!=menor){
			troca=bc[i];
			bc[i]=menor;
			bc[menor]=troca;
		}
	}

}

int main() {

	//VARIÁVEIS
	int menu1T, menu2T, aux3, aux4, n, i ;


	//ACENTUAÇÃO
	setlocale(LC_ALL, "Portuguese");

	printf("Ordenação bucket sort\n");
		printf("1 - vetores decrescentes\n2 - vetores aleatórios\n");
		scanf("%d",&menu1T);
		aux3=0;
		aux4=0;
	FILE *f;

	switch(menu1T){
			case 1:
				printf("1 - vetor 100\n2 - vetor 1000\n3 - vetor 10000\n4 - vetor 100000\n");
				scanf("%d",&menu2T);
				switch(menu2T){
					case 1:
						f=fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 1 - Descrescente - Vetor 100.txt","r");
							if(f==NULL){
								printf("Erro na abertura!\n");
							}
						else{
								printf("Sucesso na abetura do arquivo\n");
							}

						{n=100;
						int numbuckets;
						//para calcular a quantidade de baldes necessários
						numbuckets =n/TAM;
						int v[n];
						for(i=0;i<n;i++){
							fscanf(f,"%d ",&v[i]);
						}
						twogirlsonebucket (v, n, numbuckets);
						for(i=0; i<n; i++){
							printf("%d ",v[i]);
						}


						}


						break;
					case 2:
						f=fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 1 - Descrescente - Vetor 1000.txt","r");
							if(f==NULL){
								printf("Erro na abertura!\n");
							}
							else{
								printf("Sucesso na abetura do arquivo\n");
							}
						{n=1000;
						int v[n];}
						break;
					case 3:
						f=fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 1 - Descrescente - Vetor 10000.txt","r");
							if(f==NULL){
								printf("Erro na abertura!\n");
							}
							else{
								printf("Sucesso na abetura do arquivo\n");
							}
						{n=10000;
						int v[n];}

						break;
					case 4:
						f=fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 1 - Descrescente - Vetor 100000.txt","r");
							if(f==NULL){
								printf("Erro na abertura!\n");
							}
							else{
								printf("Sucesso na abetura do arquivo\n");
							}
						{n=100000;
						int v[n];}

						break;
					}

				break;
			case 2:

				switch(menu2T){
					case 1:
						f=fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 2 - Aleatório - Vetor 100.txt","r");
							if(f==NULL){
								printf("Erro na abertura!\n");
							}

							else{
								printf("Sucesso na abetura do arquivo\n");
							}
						{n=100;
						int v[n];}

						break;
					case 2:
						f=fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 2 - Aleatório - Vetor 1000.txt","r");
							if(f==NULL){
								printf("Erro na abertura!\n");
							}
							else{
								printf("Sucesso na abetura do arquivo\n");
							}
						{n=1000;
						int v[n];}

						break;
					case 3:
						f=fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 2 - Aleatório - Vetor 10000.txt","r");
							if(f==NULL){
								printf("Erro na abertura!\n");
							}
							else{
								printf("Sucesso na abetura do arquivo\n");
							}
						{n=10000;
						int v[n];}

						break;
					case 4:
						f=fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 2 - Aleatório - Vetor 100000.txt","r");
							if(f==NULL){
								printf("Erro na abertura!\n");
							}
							else{
								printf("Sucesso na abetura do arquivo\n");
							}
						{n=100000;
						int v[n];}

						break;
					}

				break;
			}

	//SAÍDA


	return 0;
}

AdrianoSiqueira · 24 de março de 2021

Não executei sei código, mas esse travamento que você descreveu pode ser normal. Dependendo da quantidade de itens e da potência da sua máquina, o processamento dos dados pode demorar. Tenta executar seu código com um vetor de tamanho pequeno (10 por exemplo) e veja se o problema persiste.

arfneto · 24 de março de 2021

Seu programa está um pouco longe de sequer compilar direito.

E foi escrito de um modo frágil e que dificulta muito os testes e o desenvolvimento. Escrever assim vai tomar um tempo muito maior que o necessário para testar e manter isso.

Vou listar alguns dos problemas e se considerar relevante pode testar a diferença...

nunca use um programa interativo para testar nada. Só coloque menus e leituras do teclado quando a lógica estiver testada. Só vai perder tempo com isso.
pouco ajuda ter comentários com acentos ou mesmo mensagens com acentos se o programa não funciona ainda. Coloque isso depois, e se for realmente necessário.
use nomes significativos
```
	int menu1T, menu2T, aux3, aux4, n, i;
```
Cada variável dessas na função com o nome de 'i' ou aux2 ou aux3 ou aux4 é um desastre.
- Qual a diferença entre aux2 e aux4?
- Vai se lembrar daqui a duas semanas? Daqui a duas horas?
Evite esse tipo de comentário
```
	//VARIÁVEIS
	int menu1T, menu2T, aux3, aux4, n, i;
```
nada acrescenta. Se imagina que a declaração seja de variáveis. Comente a lógica do que está fazendo e porque, coisas relevantes. E ter ou não um acento no comentário pouco ajuda. E não sai igual em qualquer computador...
teste SEMPRE o retorno de scanf(). Qual o propósito de seguir com o programa se não conseguiu ler algo? Tem um livro? Seu IDE mostra o protótipo das funções? Leu algo sobre scanf()?
se você tem um menu use uma função para isso, uma função que mostra as opções e retorna o que o usuário escolheu. É mais esperto
não use void. É um desperdício. Retorne algo.
nunca use variáveis de controle de um loop fora dele a menos que tenha uma razão séria para isso. E se tem uma razão séria, não chame essa variável de 'i' por exemplo. Isso é uma bomba relógio. Essa variável fica viva na função toda. Levou uns anos para corrigirem isso na linguagem, mas foi feito. Nos anos 80.
não misture lógica com formatação e leitura. Só vai atrasar tudo. E muito
não escreva o programa inteiro de uma vez. De nada vai servir. Escreva o programa para testar um certo número de valores, reproduzíveis, sempre. Até estar correto. Aí em minutos se pode aumentar a massa de teste.

o que é menos legível?

	int twogirlsonebucket(int, int, int*); //    [1]
	int two_girls_one_bucket(int, int, int*); // [2]
	int TwoGirlsOneBucket(int, int, int*); //    [3]
	int Two_Girls_One_Bucket(int, int, int*); // [4]

provavelmente o [1] e foi o que você usou...

main() deve ser a primeira função de seu programa. Sempre. Se possível em um arquivo separado. É mais produtivo para você e para quem vá er seu programa.

main() deve ser a primeira função de seu programa. Sempre. Se possível em um arquivo separado. É mais produtivo para você e para quem vá er seu programa.
Deixe os #define SEMPRE antes dos #include

main() deve ser a primeira função de seu programa. Sempre. Se possível em um arquivo separado. É mais produtivo para você e para quem vá er seu programa.
Deixe os #define SEMPRE antes dos #include
Que significa "vetores decrescentes" ou "vetores aleatórios" ? Se isso é a ordem dos dados nos vetores de teste, que diferença faz agora? Se concentre em rodar o sort para um vetor com, digamos, 1 mil elementos. Depois veja o resto
Que pretende com isso?:

f = fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 1 - Descrescente - Vetor 100.txt", "r");
```
			f = fopen("C:\\Users\\PC\\Desktop\\IFES\\Linguagem de programação\\Trabalho\\Ordem 1 - Descrescente - Vetor 100.txt", "r");
```
Se vai ler os dados de uma arquivo para que um menu pedindo o tamanho?
- nunca use o nome de um arquivo assim completo no open(). Só dá problema. Use apenas o nome do arquivo
```
	FILE* f = fopen("Vetor100.txt", "r");
```
  e coloque no diretório do programa. E declare a variável na hora de abrir.
- não use espaços em nomes de arquivos. Só dá problema. E muito menos acentos.

K1_nd3r · 24 de março de 2021

Boa tarde @arfnetoe muito obrigado pelo feedback, e realmente a única coisa pior que o código aqui é quem o escreveu kkk, brincadeiras à parte, seu comentário me ajudou bastante e adotei o que disse, mas ainda tenho algumas dúvidas, mas antes sobre os vetores, eu tenho que usar especificamente esses dos arquivos, pois é uma exigência do trabalho assim como o menu no main, e no desespero fui direto neles, algumas dessas variáveis são inúteis realmente e já retirei. As minhas dúvidas são as seguintes e se puder me responder ou me nortear seria de muita ajuda. Sobre o vetor baseado na estrutura

bc = (struct bucket*) malloc(numbucket* sizeof bc);

ou mesmo alguma passagem de parâmetros do main para a função, não sei se os fiz de maneira correta e acredito que seja um dos motivos pelo qual o programa não compila corretamente, mas não sei qual seria a solução adequada pra isso e também alguns outros problemas que não percebi ainda.

Sobre não utilizar uma função void, no caso do meu programa o que exatamente eu deveria retornar?

arfneto · 24 de março de 2021

12 minutos atrás, K1_nd3r disse:

mas antes sobre os vetores, eu tenho que usar especificamente esses dos arquivos, pois é uma exigência do trabalho assim como o menu no main

Se você fizer algo distinto do seu enunciado antes ninguém vai saber... Não faz diferença para o trabalho mas você pode terminar bem antes, talvez na mesma tarde para um programa assim, se seguir algo no aminho que te expliquei e escrever em torno dos dados.

O menu do main() é algo folclórico. Para o enunciado não faz diferença se o menu é um trecho de código em main() ou uma função

	char menu(); // mostra o tal menu e retorna a opcao

E se em main() você tem

		switch (menu2T) {
		case 1:
			f = fopen("Vetor100.txt", "r");
			if (f == NULL) {
				printf("Erro na abertura!\n");
			}
			else {
				printf("Sucesso na abetura do arquivo\n");
			}
	// ...
			{n = 100;
			int numbuckets;
			//para calcular a quantidade de baldes necessários
			numbuckets = n / TAM;
			twogirlsonebucket(v, n, numbuckets);
	// ...
			break;
		case 2:
			f = fopen("Vetor 1000.txt", "r");
			if (f == NULL) {
				printf("Erro na abertura!\n");
			}
			else {
				printf("Sucesso na abetura do arquivo\n");
			}
             // ...
			break;
		case 3:
			f = fopen("Vetor 10000.txt", "r");
			if (f == NULL) {
				printf("Erro na abertura!\n");
			}
             
             // ...

Entenda que não é esperto assim. Está reescrevendo tudo e misturando a cada case.

E não precisa disso agora porque seu programa não está pronto. Que acha que ganhou escrevendo esse menu e esse código todo? Provavelmente nada. Você precisa disso:

	int	two_girsls_one_bucket( char* arquivo );

E chamar assim:

	twoGirlsOneBucket( "vetor100.txt") );

O menu poderia ser

	char tamanho = menu2(); // mostra o menu de tamanhos e retorna o escolhido 1,2,3 ou 4

29 minutos atrás, K1_nd3r disse:

Sobre o vetor baseado na estrutura

	bc = (struct bucket*) malloc(numbucket* sizeof bc);

Prefira sempre escrever assim:

typedef struct
{
	int qtd;
	int* val;

}	Bucket;
// ...
int 	num_bucket; 

Bucket* bc = (Bucket*) malloc( num_bucket * sizeof(bc) );

É mais seguro e mais fácil de ler. E repete menos struct isso e aquilo.

33 minutos atrás, K1_nd3r disse:

Sobre não utilizar uma função void, no caso do meu programa o que exatamente eu deveria retornar?

Para cada função sempre tem algo que pode retornar: o endereço do vetor classificado, um código de erro, o total de valores...

Poste o programa como está agora

Como vão estar os dados no vetor?

Esse bucket_sort é uma coisa meio b0b1nh@. Apenas vai dividir a entrada em intervalos e depois classificar de alguma forma os intervalos e juntar as partes. Como uma criança colocando um baralho em ordem mas separando os naipes antes: seriam 4 buckets --- baldes --- paus, copas, espadas e ouro.

arfneto · 24 de março de 2021

estive lendo seu programa. não consigo entender algumas coisas
- que espera que tenha no vetor? qual a diferença entre aleatório ou decrescente? Você recebeu esses arquivos?
- que pretende com instruções assim?
```
			{n = 1000;
			int v[n]; }
```
  Em C existe um recurso, não padronizado e de uso complicado (para dizer o mínimo) para declarar coisas como int v[n] por exemplo. Recomendo esquecer isso, mesmo que saiba o que é.
  - Use constantes. Apenas constantes. Ou declara v[1000] ou declara int* v e aloca o tamanho certo depois via malloc()
  - Entenda que esse vetor v só vai existir dentro desse bloco de chaves, e como seu programa não faz nada com ele vai sumir logo em seguida. É um erro grande.

K1_nd3r · 26 de março de 2021

Boa tarde @arfneto comecei a implementar suas dicas no meu programa. Os vetores foram disponibilizados em arquivos e eu devo fazer um mesmo programa para ler e organizar todos e não consegui pensar como conseguiria passar para o meu programa o tamanho deles, e ainda não sei como faço para utilizar o arquivo em um vetor dinâmico e esse é um dos meus problemas, mas seus comentários têm sido de grande ajuda.

arfneto · 26 de março de 2021

54 minutos atrás, K1_nd3r disse:

Os vetores foram disponibilizados em arquivos

Você recebeu esses arquivos então, Wonder Person? Poste um trecho de um, umas linhas.

58 minutos atrás, K1_nd3r disse:

não consegui pensar como conseguiria passar para o meu programa o tamanho deles

Não precisa de fato saber o tamanho deles. Claro que pode ler o arquivo e contar mas seria meio b0b1nh0

Eis como se faz na prática:

você aloca um certo número deles, 1.000 por exemplo
um dos dois acaba primeiro: o arquivo ou o vetor
se acabar o arquivo você faz um trim(), libera o que não usou.
se acabou a memória você aloca mais 1000 ou algum outro número. Muitas vezes se aloca o dobro do que já tinha, por exemplo
para qualquer caso se usa uma função realloc() que faz o serviço todo, movendo todo mundo quando necessário

1 hora atrás, K1_nd3r disse:

como faço para utilizar o arquivo em um vetor dinâmico e esse é um dos meus problemas

Apenas use os ponteiros. Crie uma estrutura para os dados.

Esse lance de bucket sort é meio besta eu acho, mas de todo modo você define os buckets e pode por os dados dentro.

Provavelmente o mais esperto seria fazer uso dos dados e ler o arquivo primeiro, para saber o maior e o menor e fazer a conta dos buckets a usar e aí ler direto pra dentro deles, ou colocar todos no vetor e fazer os buckets apontarem para o vetor depois da leitura

arfneto · 26 de março de 2021

Tenho mais um tempo agora. Voltando a esse lance de ponteiros e baldes, uma estrutura assim serviria

typedef struct 
{
	int			capacidade;
	int			em_uso;			// quando esgotar aloca uma igual quantia
	Bloco*      V;

}   Controle;

Ou assim, dependendo de como vai usar...

typedef struct 
{
    int            capacidade;
    int            em_uso;            // quando esgotar aloca uma igual quantia
    Bloco**        V;

}   Controle;

No primeiro caso um vetor de blocos, no segundo um vetor de ponteiros. A lógica pode ser a mesma: começa com uma certa capacidade e conforme vai precisando estende usando realloc() de stdlib.h

Para o bucket sort ser de alguma utilidade seria o caso de não criar DUAS vezes os dados na memória, certo? Uma vez os com dados que já estavam no disco e outra com os dados em buckets... Isso ajudaria no caso de implementar registros realmente grandes, afinal 1000 baldes de mil registros já tratariam um milhão de chaves...

K1_nd3r · 27 de março de 2021

@arfneto, muito obrigado pela ajuda, fiz outra versão do programa muito mais básica, como você disse pela simplicidade do bucket sort, porém mais trabalhoso por ter que inserir os números dos vetores na raça já que não consegui implementar corretamente o acesso dos arquivos. Ficou mais ou menos assim

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

void Bucket_Sort(int vet[], int n){

    int i, j;
    int contador[n];

    for(i=0; i < n; i++){
        contador[i] = 0;
    }

    for(i=0; i < n; i++){
        (contador[vet[i]])++;
    }

    for(i=0,j=0; i < n; i++){
        for(; contador[i]>0;(contador[i])--){
            vet[j++] = i;
        }
    }
}

int main(){
    int vet[100000];
    int n,i;

    printf("Insira a quantidade de vetores que voce quer ordenar [100, 1000, 10000 ou 100000] : ");
    scanf("%d",&n);
    printf("Entre com %d elementos a serem classificados:\n",n);

    for(i = 0; i < n; i++ ){
        scanf("%d",&vet[i]);
    }
    printf("\n A matriz de elementos antes da classificacao : \n");

    for (i = 0;i < n;i++){
        printf("%d ", vet[i]);
    }

    printf("\n A matriz de elementos depois da classificacao : \n");

    Bucket_Sort(vet, n);

    for (i = 0;i < n;i++){
        printf("%d ", vet[i]);
    }

    printf("\n");

    return 0;

}

Testei pra um vetor decrescente de 100 números e funcionou corretamente, porém para os vetores aleatórios terei que usar arquivos como este anexado, e a única solução que eu consigo aplicar até agora é colocar os números na mão mesmo.

Ordem 2 - Aleatório - Vetor 100000.txt

arfneto · 27 de março de 2021

Talvez não tenha afinal levado a sério as coisas que falei no tópico #3, afinal não incorporou muito aos seus programas.

Entre as coisas que continua fazendo e que só vão te atrasar, direto do #3:

nunca use um programa interativo para testar nada. Só coloque menus e leituras do teclado quando a lógica estiver testada. Só vai perder tempo com isso.
teste SEMPRE o retorno de scanf(). Qual o propósito de seguir com o programa se não conseguiu ler algo? Tem um livro? Seu IDE mostra o protótipo das funções? Leu algo sobre scanf()?
não use void. É um desperdício. Retorne algo.
nunca use variáveis de controle de um loop fora dele a menos que tenha uma razão séria para isso. E se tem uma razão séria, não chame essa variável de 'i' por exemplo. Isso é uma bomba relógio. Essa variável fica viva na função toda. Levou uns anos para corrigirem isso na linguagem, mas foi feito. Nos anos 80.
não misture lógica com formatação e leitura. Só vai atrasar tudo.
main() deve ser a primeira função de seu programa. Sempre. Se possível em um arquivo separado. É mais produtivo para você e para quem vá ler seu programa.
Deixe os #define SEMPRE antes dos #include

7 horas atrás, K1_nd3r disse:

Testei pra um vetor decrescente de 100 números e funcionou corretamente, porém para os vetores aleatórios terei que usar arquivos como este anexado, e a única solução que eu consigo aplicar até agora é colocar os números na mão mesmo

Em 23/03/2021 às 15:37, K1_nd3r disse:

Os vetores são divididos em ordem decrescente e ordem aleatória e estes tem tamanho de 100(cem), 1000(mil), 10000(dez mil) e 100000(cem mil) números

Eu já te perguntei isso antes e você não respondeu. Que significa esse lance de vetores aleatórios ou decrescentes?

7 horas atrás, K1_nd3r disse:

porém mais trabalhoso por ter que inserir os números dos vetores na raça já que não consegui implementar corretamente o acesso dos arquivos

O que significa?

Os vetores NADA tem a ver com seu programa. Nada. O sort vai ordenar os vetores. Só isso. Tanto faz se já está em ordem, ou se a ordem é aleatória ou se tem 100 ou 100 mil números. Nada tem a ver com o bucket sort. Ou com qualquer sort.

Entendeu o que eu quiz dizer sobre isso:

typedef struct 
{
    int            capacidade;
    int            em_uso;            // quando esgotar aloca uma igual quantia
    Bloco**        V;

}   Controle;

Nada perguntou mas também não usou.

A questão dos vetores:

Inicialmente você estava lendo os dados com fscanf() e não há razão para não funcionar assim:

    int v[n];
	for(i=0;i<n;i++)
    {
        fscanf(f,"%d ",&v[i]);
    }

Mas como eu te expliquei não pode declarar v[n]. Como estamos falando de programas para iniciantes acho que não seria o fim do mundo declarar um vetor do maior tamanho afinal, e usar

    v[ 100 * 1000 ];
    int tamanho = 0;
	// ...
	for(i=0;i<tamanho;i++)
    {
        fscanf(f,"%d ",&v[i]);
    }

E acho que agora dá pra entender o porque da estrutura Controle que eu te mostrei acima... em_uso seria o tamanho, capacidade seria 100.000. Sobre os 100 * 1000 entenda que é muito mais fácil de ler assim e o compilador sabe multiplicar direitinho, de modo que isso não irá para seu código assim. Usando a estrutura você cria o valor dinâmicamente do tamanho certo, e eu expliquei como

É muito mais fácil ler de um arquivo que ler do teclado. No entanto saber a ordem interna dos dados no vetor nada significa. Não entendo sequer porque tem isso no enunciado.

Bucket sort e fazer duas vezes a mesma coisa

Acho que eu já falei disso duas vezes: os dados estão em um arquivo e você quer usar esse bucket sort. Se você ler os valores e colocar todos em um vetor e DEPOIS ler o vetor e colocar os MESMOS dados em buckets de novo não será algo assim inteligente: vai estar usando o dobro de memória, por exemplo., E quase a toa. Para 1.000 caras vai ler os 1.000 do arquivo e gravar nesse vetor v e aí vai alocar digamos 15 buckets de um certo tamanho e colocar OS MESMOS dados nesses buckets e então classificar. E DEPOIS classificar os buckets e juntar os dados de volta no vetor original? E nem vai gravar o arquivo no disco, e assim perder todo o trabalho?

Bucket sort e o número de buckets

No caso de vetores decrescentes parece que você usa o calculo do número de buckets dividindo o total pelo tamanho e é, claro, ingênuo, Mas está certo. Só que não há sentido em prever o conteúdo dos dados em um vetor que você nem leu ainda, e o algoritmo não pode se basear nessa fé. Se o cara editar lá e trocar um valor vai reclamar de quem?

No caso de valores aleatórios, como calcular o tamanho dos buckets? você parece ter usado a mesma constante TAM. E o número deles variando por uma proporção entre o maior e o menor valor... Só que isso é pouco.

Pense nesse vetor

Tem uma dúzia de valores. Quantos baldes vai usar? 90200-1/TAM daria 9000..

7 horas atrás, K1_nd3r disse:

única solução que eu consigo aplicar até agora é colocar os números na mão mesmo

O que posso dizer? Use um programa para isso. Não vai ter 20 linhas. E claro escreva um outro para ler os valores, recortar e colar. Afinal vai querer fazer isso logo em seguida, certo?

Como criar um vetor de números decrescentes?

Não. Algo conveniente seria um programa assim, digamos cria, que se você chama

	cria

ele assume 100 registros e cria "vetor.txt" com 100 registro de 100 a 1.

Mas se você usa

	cria outro.txt

Ele cria "outro.txt" no diretório corrente e com 100 registros.

Mas se você usa

	cria vetor_novo.txt 234

ele faz o esperado e cria "vetor_novo.txt" no diretório corrente e com 234 números.

Assim pode criar todos seus arquivos de teste.

Seria complicado escrever um programa desses?

Não. Veja um abaixo, onde boa parte é comentário e só não é bem menor porque tem a frescura de mostrar um certo número de itens em cada linha e tem a parada de aceitar os argumentos para não ter que ficar renomeando arquivos para os testes

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
//
// sem argumentos gera vetor.txt com 100 registros
// com 1 argumento e o nome do arquivo: ex: cria vetor199.txt
// com 2 argumentos o segundo e o tamanho:
// ex: cria coisa.txt 27 cria "coisa.txt" com 27 itens,
// em ordem decrescente, de 27 a 1
//
int main( int argc, char** argv )
{
    const char* nome_padrao = "vetor.txt";
    const int   tamanho_padrao = 100;

    char    arquivo[80]; // o nome do arquivo de saida
    int     tamanho = 0;
    if ( argc > 1 ) 
        strcpy( arquivo, argv[1] );
    else
        strcpy( arquivo, nome_padrao );
    if ( argc > 2 ) 
        tamanho = atoi(argv[2] );
    else
        tamanho = tamanho_padrao;
    // resolvido nome e tamanho do arquivo, mostra
    printf( "Vai criar \"%s\" com %d registros\n",
        arquivo, tamanho );
    // cria o arquivo
    FILE*   F = fopen( arquivo, "w" );
    int nc = 5; // numeros por linha no arquivo
    int col = 1; // vai gravar nc por coluna
    for( int i = tamanho; i>0; i-=1 )
    {
        if ( col < nc )
            col += 1, fprintf( F, "%d  ", i );
        else
            col = 1, fprintf( F, "%d\n", i );
    };  // for
    // se nao era multiplo de nc termina a linha pra ficar bonitinho
    if ( tamanho % nc != 0 ) fprintf( F, "\n");
    return 0;
}

Como ficaria rodando?

Exemplo: "cria outro.txt 23" mostra

dsp$ ./cria outro.txt 23
Vai criar "outro.txt" com 23 registros
dsp$

E em "outro.txt" tem

23  22  21  20  19
18  17  16  15  14
13  12  11  10  9
8  7  6  5  4
3  2  1

E se fosse para criar com valores aleatórios?

Seria igualzinho, já que a lógica é a mesma. No entanto tem uma pegadinha: o retorno de rand(), a função que em geral se usa para obter os tais números aleatórios, retorna um valor entre 0 e RAND_MAX, como está no manual.

Da documentação da Microsoft, em Português:

Citação

A função Rand retorna um número inteiro pseudoaleatório no intervalo de 0 a RAND_MAX (32767). Use a função srand para propagar o gerador de número de pseudoaleatória antes de chamar Rand.

A função Rand gera uma sequência bem conhecida e não é apropriada para uso como uma função criptográfica. Para geração de números aleatórios de segurança mais criptograficamente segura, use rand_s ou as funções declaradas na biblioteca C++ Standard no <random> .

Só que queremos um vetor de int. Isso quer dizer que podem ser 4 ou 8 bytes e COM SINAL. A única garantia em C é que RAND_MAX é no mínimo 32767. Dois bytes. Então precisa de alguma jogada para montar o número.

E daí?

Se pode usar algo assim pra resolver, afinal esse é um programa de sort e isso é secundário:

        int valor = ( (short)rand()<<16 ) + (short) rand(); // pra preencher o int

Um exemplo assim em C

Spoiler


# include <stdio.h>
# include <stdlib.h>
# include <string.h>
//
// sem argumentos gera vetor.txt com 100 registros
// com 1 argumento e o nome do arquivo: ex: cria vetor199.txt
// com 2 argumentos o segundo e o tamanho:
// ex: cria coisa.txt 27 cria "coisa.txt" com 27 itens
// os valores sao aleatorios para um int
//
int main( int argc, char** argv )
{
    const char* nome_padrao = "vetor.txt";
    const int   tamanho_padrao = 100;
    char    arquivo[80]; // o nome do arquivo de saida
    int     tamanho = 0;

    if ( argc > 1 ) 
        strcpy( arquivo, argv[1] );
    else
        strcpy( arquivo, nome_padrao );
    if ( argc > 2 ) 
        tamanho = atoi(argv[2] );
    else
        tamanho = tamanho_padrao;

    srand(21032701); // para os numeros aleatorios

    // resolvido nome e tamanho do arquivo, mostra
    printf( "Vai criar \"%s\" com %d registros\n",
        arquivo, tamanho );
    // cria o arquivo
    FILE*   F = fopen( arquivo, "w" );
    int nc = 5; // numeros por linha no arquivo
    int col = 1; // vai gravar nc por coluna
    for( int i = tamanho; i>0; i-=1 )
    {
        // rand() pode retornar ate 32767 apenas, dependendo
        // do valor de RAND_MAX e queremos 32 bits
        int valor = ( (short)rand()<<16 ) + (short) rand(); // pra preencher o int
        if ( col < nc )
            col += 1, fprintf( F, "%13d", valor );
        else
            col = 1, fprintf( F, "%13d\n", valor );
    };  // for
    // se nao era multiplo de nc termina a linha pra ficar bonitinho
    if ( tamanho % nc != 0 ) fprintf( F, "\n");
    return 0;
}

E se usasse "criardm aleatorio.txt 35" veria

dsp$ ./criardm aleatorio.txt 35
Vai criar "aleatorio.txt" com 35 registros
dsp$

E no arquivo teria os 35 valores

    581546329   -277800741    847322731  -2057878319   1977984709
   1224861824   -648456269   -658964460  -1351813603   2045275211
    543477221  -2010931532  -1384290036   -683515769  -1304649299
  -1012017945   1392882464   -306018936   -779390182   -900118671
    434115419    804320057   1796147370   -212985220    -20484810
  -2033770708    991629035  -1109399400   2012648739   1226779188
    919604430    -14972458  -1074926369    257790329   1610144184

E como ler um trem desses?

Claro, abre o arquivo e usa um loop. Recortar e colar desse programa acima é simples, porque é quase a mesma coisa

Eis uma versão

# include <limits.h>
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
//
// sem argumentos tenta ler vetor.txt
// com 1 argumento e o nome do arquivo
//
int main( int argc, char** argv )
{
    const char* nome_padrao = "vetor.txt";
    char    arquivo[80]; // o nome do arquivo de saida
    int     tamanho = 0;

    if ( argc > 1 ) 
        strcpy( arquivo, argv[1] );
    else
        strcpy( arquivo, nome_padrao );

    printf( "Vai ler \"%s\"\n", arquivo );
    FILE*   F = fopen( arquivo, "r" );
    if ( F == NULL ) return -1;
    int nc = 5; // numeros por linha na saida
    int col = 1; // vai gravar nc por coluna
    int valor = 0;
    int menor = INT_MAX;
    int maior = INT_MIN;
    int res = fscanf( F, "%d", &valor );
    while ( res == 1 )
    {
        tamanho += 1;
        if (valor > maior) maior = valor;
        if (valor < menor) menor = valor;
        if ( col < nc )
            col += 1, printf( "%13d", valor );
        else
            col = 1, printf( "%13d\n", valor );
        res = fscanf( F, "%d", &valor );
    };  // for
    printf("\nLidos %d valores, nenor = %d, maior = %d\n",
        tamanho, menor, maior );
    fclose(F);
    return 0;
}

Como a gente não sabe quantos tem o while() pode ser melhor que o for. E já que estamos lendo não custa nada contar quantos tem e mostrar o maior e o menor, porque certamente vai querer saber isso para o bucket sort, certo?

Eis o resultado para a leitura do arquivo acima, aleatorio.txt

dsp$ ./lev aleatorio.txt
Vai ler "aleatorio.txt"
    581546329   -277800741    847322731  -2057878319   1977984709
   1224861824   -648456269   -658964460  -1351813603   2045275211
    543477221  -2010931532  -1384290036   -683515769  -1304649299
  -1012017945   1392882464   -306018936   -779390182   -900118671
    434115419    804320057   1796147370   -212985220    -20484810
  -2033770708    991629035  -1109399400   2012648739   1226779188
    919604430    -14972458  -1074926369    257790329   1610144184

Lidos 35 valores, nenor = -2057878319, maior = 2045275211
dsp$

K1_nd3r · 27 de março de 2021

@arfneto Consegui terminar o meu trabalho e finalmente consegui utilizar os arquivos corretamente, o que acontece,

1 hora atrás, arfneto disse:

Eu já te perguntei isso antes e você não respondeu. Que significa esse lance de vetores aleatórios ou decrescentes?

meu professor de programação, que é uma matéria um pouco mais fora do meu curso, passou um trabalho em que eu teria que utilizar exatamente os arquivos que ele passou com os vetores, pra ter uma base de comparação entre os trabalhos, por isso eu sabia exatamente o tamanho dos vetores e que eles não deveriam mudar.

1 hora atrás, arfneto disse:

Nada perguntou mas também não usou.

Entendi sim, mas pro meu nível seria mais complicado já que não aprendi muito sobre estruturas e alocação dinâmica, mas quando estava fazendo a primeira versão do programa pareceu fazer sentido em utilizar, mas de qualquer modo:

1 hora atrás, arfneto disse:

Como estamos falando de programas para iniciantes acho que não seria o fim do mundo declarar um vetor do maior tamanho afinal, e usar

.

E muito obrigado pela ajuda e pelo seu tempo, ajudou bastante mesmo, apliquei bastante do que disse na minha realidade aqui de estudante que aprendeu programação agora, foi realmente útil, um abraço.