Buscar

Como usar vetores em algoritimos para organizar celulas?

💡 5 Respostas

User badge image

Joao Andre MArtins Dias

Parceiro como a pergunta está meio genéria, não sei em que linguagem você está trabalhando e tão pouco sei o que exatamente você quis dizer com  celulas.

Sendo assim ai está um algorítimo de ordenação muito eficiente, o QuickSort com Pivô em linguagem C. Se as tais celulas forem estruturas(structs) basta adaptar para um vetor de estruturas e fazer a comparação com o atributo da estrutura desejado.

Ex: struct celula{

int codigo;

char nome[10];

};

seria um vetor de celulas, celula vet[] e não masi int vet, e a comparação seria pelo vete[i].codigo;

Em fim... Se as celulas forem mais que 100.000 eu recomendo trocar a implementação de recursiva para iterativa, com o uso de uma estrutura auxiliar do tipo pilha, para simular a recursão, o que deixaria o algorítimo consideravelmente mais rápido. e é bem simples de fazer.

/*
 * File:   main.cpp
 * Author: joao
 * Quick Sort recursivo com pivô em vetores
 */

#include <stdlib.h>
#include <stdio.h>
#include<math.h>
using namespace std;

//----------------------------------

void quickSort(int vet[], int ini, int fim) {
    int i = ini, j = fim, aux, pivo = vet[(ini + fim) / 2];
    while (i < j) {
        while (vet[i] < pivo) {
            i++;
        }
        while (vet[j] > pivo) {
            j--;
        }
        if (i <= j) {
            aux = vet[i];
            vet[i] = vet[j];
            vet[j] = aux;
            i++;
            j--;
        }
    }
    if (ini < j) {
        quickSort(vet, ini, j);
    }
    if (i < fim) {
        quickSort(vet, i, fim);
    }
}
//----------------------------------

void quickSortP(int vet[], int tl) {
    quickSort(vet, 0, tl);
}

void preencherVetor(int vet[], int tl) {
    for (int i = 0; i < tl; i++) {
        vet[i] = (rand() % ((150 - 1) + 1)) + 1;

    }
}

void exibirvetor(int vet[], int tl) {
    printf("\n------------------------------\n");
    for (int i = 0; i < tl; i++) {
        printf("[%d] - ", vet[i]);
    }
}

int main(int argc, char** argv) {
    int tl=10,vet[tl];
    preencherVetor(vet, tl);
    exibirvetor(vet,tl);
    quickSortP(vet, tl);
    exibirvetor(vet,tl);

}

1
Dislike0
User badge image

Joao Andre MArtins Dias

Pra ninguém falar que eu dei uma de Macarrão com queijo do Cris(Para fazer um quickSort iterativo você só precisa de... Uma pilha...kkk) em fim.

Pilha.h

struct No {
        int info;
        struct No *prox;
    };
    typedef struct No No;
    //-------------------------------------------------------------------

    void init(No **pilha);
    void push(No **pilha, int info);
    void pop(No **pilha, int *info);
    char isEmpty(No *pilha);
    //-------------------------------------------------------------------
    // Recebe um ponteiro para uma pilha e Inicializa a pilha
    void init(No **pilha) {
        *pilha = NULL;
    }
    // recebe um ponteiro para uma pilha e uma informação a a insere
    void push(No **pilha, int info) {
        No *nova = (No*) malloc(sizeof (No));
        nova->info = info;
        nova->prox = *pilha;
        *pilha = nova;
    }
    // recebe um ponteiro para uma pilha e o endereço para um inteiro como
    // parametros retira o elemento da pilha para o parametro inteiro
    void pop(No **pilha, int *info) {
        if (*pilha != NULL) {
            No *aux = *pilha;
            *info = (*pilha)->info;
            *pilha = (*pilha)->prox;
            free(aux);
        }
    }
    // recebe um ponteiro para uma pilha e retorna 1 se for vazia
    char isEmpty(No *pilha) {
        return pilha == NULL;
    }

//---------------------------------------------------------------------------

/*
 * File:   main.cpp
 * Author: joao
 * Quick Sort Iterativo com pivô em vetores
 */

#include <stdlib.h>
#include <stdio.h>
#include<math.h>
#include"Pilha.h"
using namespace std;

//----------------------------------

void quickSort(int vet[], int ini, int fim) {
    int i = ini, j = fim, aux, pivo = vet[(ini + fim) / 2];
    No *pIni, *pFim;
    init(&pIni);
    init(&pFim);
    push(&pIni, ini);
    push(&pFim, fim);
    while (!isEmpty(pIni)) {
        pop(&pIni, &ini);
        i = ini;
        pop(&pFim, &fim);
        j = fim;
        pivo = vet[(ini + fim) / 2];
        while (i < j) {
            while (vet[i] < pivo) {
                i++;
            }
            while (vet[j] > pivo) {
                j--;
            }
            if (i <= j) {
                aux = vet[i];
                vet[i] = vet[j];
                vet[j] = aux;
                i++;
                j--;
            }
        }

        if (ini < j) {
            push(&pIni, ini);
            push(&pFim, j);
        }
        if (i < fim) {
            push(&pIni, i);
            push(&pFim, fim);
        }
    }

}
//----------------------------------

void preencherVetor(int vet[], int tl) {
    for (int i = 0; i < tl; i++) {
        vet[i] = (rand() % ((150 - 1) + 1)) + 1;

    }
}

void exibirvetor(int vet[], int tl) {
    printf("\n------------------------------\n");
    for (int i = 0; i < tl; i++) {
        printf("[%d] - ", vet[i]);
    }
}

int main(int argc, char** argv) {
    int tl = 10, vet[tl];
    preencherVetor(vet, tl);
    exibirvetor(vet, tl);
    quickSort(vet, 0, tl);
    exibirvetor(vet, tl);

}

//-----------------------------------------------------

Meu Professor de Pesquisa e Ordenação tem um prazer sádico e passa em aula o quick recursivo e na prova o iterativo...kkk Deus sabe que esse método já me derrubou mais de uma vez...kkk

Mas é um bom exemplo de como funciona um metodo recursivo, que tem apenas dois momentos ou ele empilha ou ele desempilha. e é o que ocorre aqui, em vez de controlarmos o fim do algorítimo com a condição i<j agora controlamos também pelo fim da pilha. E onde antes faziamos uma chamada recursiva ao método empihamos a posição de inicio e fim e desempilhamos a cada iteração, simulando assim a recursão.

 

0
Dislike0
User badge image

Andre Smaira

Como usar vetores em algoritimos para organizar celulas?

#Vetor-Algoritimo


Para a resolução desta tarefa foram utilizados conhecimentos sobre vetores e algoritmos.


Vetores podem ser declarados com mais de uma dimensão, o que nos possibilita transformá-lo em uma matriz, facilitando muito a organização de células. Um exemplo de declaração de matriz é:


int matriz[3][4];


Essa declaração cria uma matriz de inteiros de ordem 3x4, ou seja, que contém 12 valores do tipo inteiro.


Utilizando vetores com mais de uma dimensão, como as matrizes.

0
Dislike0

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

✏️ Responder

SetasNegritoItálicoSublinhadoTachadoCitaçãoCódigoLista numeradaLista com marcadoresSubscritoSobrescritoDiminuir recuoAumentar recuoCor da fonteCor de fundoAlinhamentoLimparInserir linkImagemFórmula

Para escrever sua resposta aqui, entre ou crie uma conta

User badge image

Outros materiais