Untitled
unknown
c_cpp
2 years ago
3.0 kB
11
Indexable
#include <stdlib.h> #include <stdio.h> #include <time.h> #include <stdbool.h> void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; return; } void newTab(int* tab, int tabsize) { for (int i = 0; i < tabsize; i++) { tab[i] = rangedRand(0, 100); } } int rangedRand(int min, int max) { return min + rand() / (RAND_MAX / (max - min + 1) + 1); } void printTab(int* tab) { for (int i = 0; i < sizeof(tab); i++) { printf("%i ", tab[i]); } printf("\n"); } void trieNaif(int* tab, int tabsize) { for (int i = 0; i < tabsize; i++) { for (int y = i + 1; y < tabsize; y++) { if (tab[i] > tab[y]) { swap(tab + i, tab + y); } } } return; } void TriSelection(int* tab, int tabsize) { for (int i = 0; i < tabsize - 1; i++) { int minIdx = i; for (int y = i + 1; y < tabsize; y++) { if (tab[minIdx] > tab[y]) { minIdx = y; } } swap(tab + i, tab + minIdx); } } void trieBulle(int* tab, int tabsize) { bool ordered = false; int taille = tabsize; while(!ordered){ ordered = true; for (int i = 0; i < taille-1; i++) { if (tab[i] > tab[i + 1]) { swap(tab + i, tab + i + 1); ordered = false; } } tabsize--; } } int TriInsertionSequentiel(int* tab, int tabsize) { if (tabsize < 2) return -1; for (int i = 1; i < tabsize; i++) { int swapIdx = i - 1; int value = tab[i]; while (swapIdx >= 0 && tab[swapIdx] > value) { swap(tab + swapIdx + 1, tab + swapIdx); swapIdx--; } tab[swapIdx + 1] = value; } return 0; } int rang(int* tab, int indmin, int indmax, int valeur) { while (indmin <= indmax) { int indmid = (indmin + indmax) / 2; if (tab[indmid] == valeur) { return indmid; } else if (tab[indmid] < valeur) { indmin = indmid + 1; } else { indmax = indmid - 1; } } return (tab[indmax] < valeur) ? indmax + 1 : indmax; } int TriInsertionDichotomique(int* tab, int tabsize) { if (tabsize < 2) return -1; for (int i = 1; i < tabsize; i++) { int swapIdx = rang(tab, 0, i, tab[i]); int value = tab[i]; for (int j = i; j > swapIdx; j--) { tab[j] = tab[j - 1]; } tab[swapIdx] = value; } return 0; } int main() { srand(time(NULL)); int tab[10]; //Trie Naif newTab(tab, sizeof(tab)/sizeof(tab[0])); trieNaif(tab, sizeof(tab)/sizeof(tab[0])); printTab(tab); //Trie Bulle newTab(tab, sizeof(tab) / sizeof(tab[0])); trieBulle(tab, sizeof(tab) / sizeof(tab[0])); printTab(tab); //TrieSelection newTab(tab, sizeof(tab) / sizeof(tab[0])); TriSelection(tab, sizeof(tab) / sizeof(tab[0])); printTab(tab); //Trie Insertion Séquentielle newTab(tab, sizeof(tab) / sizeof(tab[0])); TriInsertionSequentiel(tab, sizeof(tab) / sizeof(tab[0])); printTab(tab); //Trie Insertion Dichotomique newTab(tab, sizeof(tab) / sizeof(tab[0])); TriInsertionDichotomique(tab, sizeof(tab) / sizeof(tab[0])); printTab(tab); return EXIT_SUCCESS; }
Editor is loading...