Skip to content

Instantly share code, notes, and snippets.

@d3cryptofc

d3cryptofc/rangesort.c

Last active October 6, 2024 12:22
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save d3cryptofc/0629f82f18f58ae6db7caf267a38c607 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save d3cryptofc/0629f82f18f58ae6db7caf267a38c607 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
rangesort.c
/*
De repente pensei: pq não ordenar números usando índices? Nào tornaria mais
rápido se cada numero fosse para sua devida posição?
E então escrevi esse algoritmo que possui complexidade linear O(n)
É ainda mais perfeito para números sequenciais que não possuem repetição, a única
desvantagem é que pra ser mais eficiente você deve saber quantos itens tem
o seu array e qual número entre eles é o menor possível para evitar desperdício de memória.
No entanto dá pra otimizar ainda mais e é um dos meus primeiros algoritmos em C.
=========================================================================================
INFORMAÇÃO IMPORTANTE!
Remover buracos requer alocar mais metade do tamanho do array e iterar o array novamente,
portanto pense bem se é importante ou não.
=========================================================================================
*/
#include "stdlib.h"
#include "stdio.h"
#include "stdbool.h"
#include "time.h"
#include <stdint.h>
typedef struct {
size_t value;
size_t quantity;
} Item;
typedef enum {
OL_UNKNOWN_ERROR = 0,
OL_INVALID_LENGTH_ERROR = 1,
OL_MALLOC_ERROR = 2,
OL_REALLOC_ERROR = 3,
OL_NUMBER_GREATER_THAN_ARRLENGTH = 4
} OrderedListError;
Item* sort_range(size_t* array, size_t start_range, size_t* arr_length, bool rmholes, OrderedListError* error_code){
// Erro: Tamanho inválido de array de entrada.
if(*arr_length == 0){
*error_code = OL_INVALID_LENGTH_ERROR;
return NULL;
}
// Alocando espaço (em tamanho da struct Item) para o mesmo tamanho do array de entrada.
Item* new_array = (Item*) calloc(*arr_length, sizeof(Item));
// Erro: Não há memória suficiente para alocar.
if(new_array == NULL){
*error_code = OL_MALLOC_ERROR;
return NULL;
}
// Variável para armazenar a quantidade de inserções feitas no novo array,
// sem contar os itens repetidos.
size_t no_repetead_inserts = 0;
// Loop para iterar o array de entrada.
for(size_t i = 0; i < *arr_length; i++){
// Obtendo o número atual do array na iteração.
size_t current_number = array[i];
// Calculando indice do array, garantindo iniciação em 0.
size_t current_position = current_number - start_range;
// Erro: número maior que tamanho do array.
if(current_number > *arr_length){
*error_code = OL_NUMBER_GREATER_THAN_ARRLENGTH;
return NULL;
}
// Caso a mesma posição no novo array esteja vazia.
if(new_array[current_position].quantity == 0){
// Armazena o item atual no novo array.
new_array[current_position] = (Item){.value=current_number, .quantity = 1};
// Incrementando contador de inserções.
no_repetead_inserts++;
}
// Caso a posição não esteja vazia (já preenchida).
else {
// Apenas incrementa a quantidade.
new_array[current_position].quantity++;
}
}
// REMOÇÃO DE BURACOS
// Isto irá otimizar as buscas, uma vez que reduzirá a quantidade de iterações
// a serem realizadas para encontrar determinado elemento, no entanto, apesar
// da remoção dos buracos ser uma etapa de única vez, pode ser um processo
// demorado dependendo da quantidade de itens pois precisará iterar toda a lista
// uma segunda vez.
// Caso não haja buracos ou não queira remmove-los.
if(*arr_length == no_repetead_inserts || !rmholes){
// Finaliza retornando o novo array.
return new_array;
}
// Alocando espaço para a mesma quantidade de itens do array de entrada.
size_t* arr_position_holes = (size_t*) malloc(sizeof(size_t) * *arr_length);
// Erro: Não há memória suficiente para alocar.
if(arr_position_holes == NULL){
*error_code = OL_MALLOC_ERROR;
return NULL;
}
// Variável usada para saber a posição do último buraco no array.
size_t arr_last_index_hole = 0;
// Variável usada para saber se há buraco disponíveis.
bool has_available_hole = false;
// Variável usada para obter o índice do buraco disponível.
size_t available_index_hole = 0;
// Loop para iterar o novo array.
for(size_t i = 0; i < *arr_length; i++){
// Obtendo o item atual do array na iteração.
Item current_item = new_array[i];
// Caso encontre um buraco logo de cara.
if(current_item.quantity == 0){
// Faz um 'append' do índice atual no array de índices de buracos.
arr_position_holes[arr_last_index_hole] = i;
arr_last_index_hole++;
// Um buraco foi encontrado, isto libera o segundo if.
has_available_hole = true;
// Pula para a próxima iteração, à procura de um item.
continue;
}
// Parece que um buraco foi encontrado.
if(has_available_hole){
// Copiando o item do índice atual para um dos primeiros buracos.
new_array[arr_position_holes[available_index_hole]] = current_item;
// Deletamos o item do índice atual (criando um buraco novo).
new_array[i] = (Item){0, 0};
// Então um novo buraco ficou disponível.
available_index_hole++;
/// Faz um 'append' do índice atual no array de índices de buracos.
arr_position_holes[arr_last_index_hole] = i;
arr_last_index_hole++;
}
}
// Se o loop terminou significa que conseguimos ajuntar os itens todos ã esquerda,
// já podemos liberar a memória que foi alocada para o array de índices de buracos.
free(arr_position_holes);
arr_position_holes = NULL;
// Realocando memória para o tamanho do array sem buracos.
new_array = realloc(new_array, no_repetead_inserts * sizeof(Item));
if(new_array == NULL){
*error_code = OL_REALLOC_ERROR;
return NULL;
}
// Alterando o tamanho de entrada do array inserido pelo usuário.
*arr_length = no_repetead_inserts;
return new_array;
}
void simulate(size_t start_range, size_t length, bool rmholes, uint8_t mode){
// Alocando espaço pra armazenar um array de número não-ordenado.
size_t* unsorted = (size_t*) malloc(sizeof(size_t) * length);
// Iniciando a exibição dos itens do array não-ordenado.
printf("Entrada: [%zu] ", length);
// Realizando uma contagem reversa.
for(size_t i = 0; i < length; i++){
// Inicializando variável `value` com qualquer valor.
size_t value = 0;
// Modo sequencialmente revertido (Ex: 5,4,3,2,1).
if(mode == 0){
value = length - i;
}
// Modo aleatório, com possíveis repetições.
else if(mode == 1){
value = (((size_t) rand()) % length) + start_range;
}
// Modo de somente repetição.
else if(mode == 2){
value = 2;
}
// Armazenando o valor no espaço alocado.
unsorted[i] = value;
// Exibindo o valor.
printf("%zu ", value);
}
// Quebra de linha.
printf("\n");
// Variáveis que armazenarão os tempos de execução.
struct timespec started_time, elapsed_time;
// Iniciando uma variável para armazenar possível erro da função de ordenação.
OrderedListError error_code = 0;
// Armazenando o tempo de início de execução.
clock_gettime(CLOCK_MONOTONIC, &started_time);
// Ordenando o array não-ordenado.
// array: unsorted => endereço do início do array não-ordenado.
// start_range: start_range => o menor número do array.
// arr_length: &length => passando endereço da variável `length` para que seja modificada se necessário.
// rmholes: rmholes => sempre remover os buracos que ficar (afeta desempenho).
// error: &error_code => passando endereço da variável `error` para que insira o código do erro se necessário.
Item *result = sort_range(unsorted, start_range, &length, rmholes, &error_code);
// Armazenando tempo após a execução.
clock_gettime(CLOCK_MONOTONIC, &elapsed_time);
// Liberando memória alocada usada apra o array de itens não-ordenados.
free(unsorted);
unsorted = NULL;
// Caso não retorne um ponteiro para um item.
if(result == NULL){
// Armazenando mensagem genérica de erro.
char* error_msg = "Desconhecido.";
// Caso o tamanho do array seja inválido.
if(error_code == OL_INVALID_LENGTH_ERROR){
error_msg = "Tamanho do array é inválido.";
}
// Caso não seja possível alocar memória na HEAP.
else if(error_code == OL_MALLOC_ERROR){
error_msg = "Não foi possível alocar memória na HEAP.";
}
// Caso não seja possível realocar memória na HEAP.
else if(error_code == OL_REALLOC_ERROR){
error_msg = "Não foi possível realocar memória na HEAP.";
}
// Caso seja encontrado um número maior que o tamanho do array.
else if(error_code == OL_NUMBER_GREATER_THAN_ARRLENGTH){
error_msg = "Encontrado um número maior que o tamanho do array.";
}
// Exibe mensagem, código de erro e finaliza a função.
printf("Ocorreu um erro! (%u) - %s\n", error_code, error_msg);
exit(error_code);
return;
}
// Iterando a nova lista ordenada e exibindo suas propriedades.
printf("Saída: [%zu] ", length);
for (size_t i = 0; i < length; i++) {
printf("%zu(%zu) ", result[i].value, result[i].quantity);
}
printf("\n");
// Liberando memória do array de resultado.
free(result);
result = NULL;
printf("Remoção de buracos: %s\n", rmholes ? "ATIVADA" : "DESATIVADA");
printf(
"Tempo de ordenação: %zu ns\n",
(size_t)(
((elapsed_time.tv_sec - started_time.tv_sec) * 1e9)
+ elapsed_time.tv_nsec - started_time.tv_nsec
)
);
}
int main(){
// Definindo seed do gerador de número pseudo-aleatório.
srand(time(NULL));
// MELHOR CASO: Simulação sequencial sem números repetidos.
// (não será necessário iterar novamente para remover buracos)
simulate(1, 20, true, 0);
printf("\n");
// Simulação com possíveis numeros, mas nem todos repetidos.
// (infelizmente tendo apenas um número que repita, a remoção de buracos é necessária)
simulate(1, 20, true, 1);
printf("\n");
// Simulação com todos os números repetidos.
// (aqui possivelmente uma grande quantidade de espaço foi alocada e desperdiçada)
simulate(1, 20, true, 2);
printf("\n");
// MELHOR CASO: Simulação sequencial sem números repetidos.
// (sem remover buracos)
simulate(1, 20, false, 0);
printf("\n");
// Simulação com possíveis numeros, mas nem todos repetidos.
// (sem remover buracos)
simulate(1, 20, false, 1);
printf("\n");
// Simulação com todos os números repetidos.
// (sem remover buracos)
simulate(1, 20, false, 2);
return 0;
}
@d3cryptofc
Copy link
Author

d3cryptofc commented Oct 5, 2024 •
edited
Loading 

Entrada: [20] 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
Saída: [20] 1(1) 2(1) 3(1) 4(1) 5(1) 6(1) 7(1) 8(1) 9(1) 10(1) 11(1) 12(1) 13(1) 14(1) 15(1) 16(1) 17(1) 18(1) 19(1) 20(1) 
Remoção de buracos: ATIVADA
Tempo de ordenação: 760 ns

Entrada: [20] 13 4 15 3 14 20 20 20 17 13 4 5 15 9 8 20 18 8 6 7 
Saída: [13] 3(1) 4(2) 5(1) 6(1) 7(1) 8(2) 9(1) 13(2) 14(1) 15(2) 17(1) 18(1) 20(4) 
Remoção de buracos: ATIVADA
Tempo de ordenação: 1040 ns

Entrada: [20] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 
Saída: [1] 2(20) 
Remoção de buracos: ATIVADA
Tempo de ordenação: 390 ns

Entrada: [20] 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
Saída: [20] 1(1) 2(1) 3(1) 4(1) 5(1) 6(1) 7(1) 8(1) 9(1) 10(1) 11(1) 12(1) 13(1) 14(1) 15(1) 16(1) 17(1) 18(1) 19(1) 20(1) 
Remoção de buracos: DESATIVADA
Tempo de ordenação: 180 ns

Entrada: [20] 7 15 20 1 15 15 3 16 10 13 6 14 17 20 16 10 20 15 1 16 
Saída: [20] 1(2) 0(0) 3(1) 0(0) 0(0) 6(1) 7(1) 0(0) 0(0) 10(2) 0(0) 0(0) 13(1) 14(1) 15(4) 16(3) 17(1) 0(0) 0(0) 20(3) 
Remoção de buracos: DESATIVADA
Tempo de ordenação: 220 ns

Entrada: [20] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 
Saída: [20] 0(0) 2(20) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 0(0) 
Remoção de buracos: DESATIVADA
Tempo de ordenação: 140 ns

Hipótese 1:

Com somente números repetidos resta somente mover o item para o primeiro buraco, e então o loop acaba sem fazer mais nenhum movimento, enquanto que com vários números aleatórios são realizados várias movimentações de Item.

@d3cryptofc
Copy link
Author

d3cryptofc commented Oct 6, 2024

Integração da biblioteca rangesort em C no python:
https://gist.github.com/d3cryptofc/26166d0200428c4d5330a806bcd72bbe

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment