Untitled

 avatar
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...