GROUPE GENIUS REPETITION
TEUFACK DOURY C.
ALGORITHMES DE TRIS
Tri Insertion
#include <stdio.h>
#include <stdlib.h>
#define N 6
int main()
{
int tab[N];
int i, j, cle;
printf("Entrez les elements du tableau : \n");
for(i = 0; i < N; i++)
{
scanf("%d", &tab[i]);
}
printf("Tableau initial :\n");
for(i = 0; i < N; i++)
{
printf("%d \t", tab[i]);
}
printf("\n");
for(i = 1; i < N; i++)
{
cle = tab[i];
j = i-1;
while(cle < tab[j] && j > -1)
{
tab[j+1] = tab[j];
j = j-1;
}
tab[j+1] = cle;
}
// Affichage du tableau trie
printf("Tableau trie :\n");
for(i = 0; i < N; i++)
{
printf("%d \t", tab[i]);
}
return 0;
}
Pour plus d’informations, voir le Groupe Genius : 1
+237 652027193
+237 658395978
GROUPE GENIUS REPETITION
TEUFACK DOURY C.
TRI SELECTION
#include <stdio.h>
#include <stdlib.h>
#define N 10
int main()
{
int tab[N];
int i, j, k, tmp;
printf("Entrez les elements du tableau : \n");
for(i = 0; i < N; i++)
{
scanf("%d", &(tab[i]));
}
printf("Tableau initial :\n");
for(i = 0; i < N; i++)
{
printf("%d \t", tab[i]);
}
printf("\n");
// Tri du tableau
for(i = 0; i < N; i++)
{
k = i;
for(j = i+1 ; j < N; j++)
{
if(tab[k] > tab[j])
{
k = j;
}
}
tmp = tab[i] ;
tab[i] = tab[k];
tab[k] = tmp;
}
// Affichage du tableau trié
printf("Tableau trie :\n");
Pour plus d’informations, voir le Groupe Genius : 2
+237 652027193
+237 658395978
GROUPE GENIUS REPETITION
TEUFACK DOURY C.
for(i = 0; i < N; i++)
{
printf("%d \t", tab[i]);
}
return 0;
}
Tri bulle
#include <stdio.h>
#include <stdlib.h>
#define N 10
int main()
{
int tab[N];
int i, j, tmp;
printf("Entrez les elements du tableau : \n");
for(i = 0; i < N; i++)
{
scanf("%d", &tab[i]);
}
printf("Tableau initial :\n");
for(i = 0; i < N; i++)
{
printf("%d \t", tab[i]);
}
// Tri du tableau
printf("\n");
i = N-1;
while(i>-1)
{
for(j = 0; j < i; j++)
{
if(tab[j] > tab[j+1])
{
tmp = tab[j];
tab[j] = tab[j+1];
tab[j+1] = tmp;
}
}
Pour plus d’informations, voir le Groupe Genius : 3
+237 652027193
+237 658395978
GROUPE GENIUS REPETITION
TEUFACK DOURY C.
i = i - 1;
}
// Affichage du tableau trié
printf("Tableau trie :\n");
for(i = 0; i < N; i++)
{
printf("%d \t", tab[i]);
}
return 0;
}
TRI RAPIDE
#include <stdio.h>
#include <stdlib.h>
void printArray(int* tab, int tabSize) {
int i;
for(i = 0; i < tabSize; i++){
printf("%d ", *(tab+i));
}
printf("\n");
return;
}
int* scanArray(int* tab, int tabSize){
tab = (int*)malloc(sizeof(int)*tabSize);
int i=0;
if(tab != NULL){
printf("Entrez les elements du tableau : \n");
for(i = 0; i < tabSize; i++){
scanf("%d", tab+i);
}
}
return tab;
}
int Partionnement(int *A, int p, int r){
int x = A[p];
int i = p-1;
int j = r+1;
Pour plus d’informations, voir le Groupe Genius : 4
+237 652027193
+237 658395978
GROUPE GENIUS REPETITION
TEUFACK DOURY C.
int tmp;
while(i < j){
do{ j--;}while(A[j] > x);
do{ i++;}while(A[i] < x);
if(i < j){
tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
else
return j;
}
}
void Tri_Rapide(int *A, int p, int r){
int q;
if(p < r){
q = Partionnement(A,p,r);
Tri_Rapide(A, p, q);
Tri_Rapide(A, q+1, r);
}
}
int main(void){
int n;
int p, *tab = NULL;
printf("Entrez la taille du tableau : ");
scanf("%d", &n);
tab = scanArray(tab, n);
printf("Tableau intial : \n");
if(tab != NULL){
printArray(tab, n);
}
p = 0;
Tri_Rapide(tab, p, n-1);
printf("Tableau trie : \n");
printArray(tab, n);
Pour plus d’informations, voir le Groupe Genius : 5
+237 652027193
+237 658395978
GROUPE GENIUS REPETITION
TEUFACK DOURY C.
free(tab);
return 0;
}
Tri fusion
#include <stdio.h>
#include <stdlib.h>
void printArray(int* tab, int tabSize) {
int i;
for(i = 0; i < tabSize; i++){
printf("%d ", *(tab+i));
}
printf("\n");
return;
}
int* scanArray(int* tab, int tabSize){
tab = (int*)malloc(sizeof(int)*tabSize)
int i=0;
if(tab != NULL){
printf("Entrez les elements du tableau : \n");
for(i = 0; i < tabSize; i++){
scanf("%d", tab+i);
}
}
return tab;
}
void Fusion(int *A, int p, int q, int r){
int i = p;
int j = q+1;
int *C = (int*)malloc(sizeof(int)*(r-p+1));
int k = 0;
while(i <= q && j <= r){
if(A[i] < A[j]){
C[k] = A[i];
i++;
}
else{
Pour plus d’informations, voir le Groupe Genius : 6
+237 652027193
+237 658395978
GROUPE GENIUS REPETITION
TEUFACK DOURY C.
C[k] = A[j];
j++;
}
k++;
}
// printArray(C, r-p+1);
while(i <= q){
C[k] = A[i];
i++;
k++;
}
while(j <= r){
C[k] = A[j];
j++;
k++;
}
for(k = 0; k < (r-p+1); k++){
A[p+k] = C[k];
}
return;
}
void Tri_Fusion(int *A, int p, int r){
int q;
if(p < r) {
q = (p+r)/2;
Tri_Fusion(A, p, q);
Tri_Fusion(A, q+1, r);
Fusion(A,p,q,r);
}
return;
}
int main(void){
int n;
int p = 0, *tab = NULL;
printf("Entrez la taille du tableau : ");
scanf("%d", &n);
tab = scanArray(tab, n);
Pour plus d’informations, voir le Groupe Genius : 7
+237 652027193
+237 658395978
GROUPE GENIUS REPETITION
TEUFACK DOURY C.
printf("Tableau intial : \n");
if(tab != NULL){
printArray(tab, n);
}
Tri_Fusion(tab, p, n-1);
printf("Tableau trie : \n");
printArray(tab, n);
free(tab);
return 0;
}
Tri par tas
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b) {
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
void printArray(int* tab, int tabSize) {
int i;
for(i = 0; i < tabSize; i++){
printf("%d ", *(tab+i));
}
printf("\n");
return;
}
int* scanArray(int* tab, int tabSize){
tab = (int*)malloc(sizeof(int)*tabSize);
int i=0;
if(tab != NULL){
printf("Entrez les elements du tableau : \n");
for(i = 0; i < tabSize; i++){
scanf("%d", tab+i);
}
}
return tab;
Pour plus d’informations, voir le Groupe Genius : 8
+237 652027193
+237 658395978
GROUPE GENIUS REPETITION
TEUFACK DOURY C.
int Pere(int i){
return(i/2);
}
int Gauche(int i){
return(2*i);
}
int Droit(int i){
return((2*i)+1);
}
void Entasser(int *A, int i, int taille){
int g = Gauche(i);
int d = Droit(i);
int max = i;
if(g < taille && A[g] > A[max]) max = g;
if(d < taille && A[d] > A[max]) max = d;
if(max != i){
swap((A+i), (A+max));
Entasser(A, max, taille-1);
}
}
void Construire_Tas(int *A, int n){
int i;
for(i = n/2; i > -1; i--){Entasser(A,i,n);}
}
int main(void){
int n, i;
int* tab = NULL;
printf("Entrez la taille du tableau : ");
scanf("%d", &n);
tab = scanArray(tab, n);
printf("Tableau intial : \n");
if(tab != NULL){
printArray(tab, n);
}
int taille = n;
Pour plus d’informations, voir le Groupe Genius : 9
+237 652027193
+237 658395978
GROUPE GENIUS REPETITION
TEUFACK DOURY C.
Construire_Tas(tab, n);
for(i = n-1; i > 0; i--){
swap((tab+0), (tab+i));
taille = taille - 1;
Entasser(tab, 0, taille);
}
printf("Tableau trie : \n");
printArray(tab, n);
free(tab);
Pour plus d’informations, voir le Groupe Genius : 10
+237 652027193
+237 658395978
