void fswap(int *a, int *b){
    int c = *a;
    *a = *b;
    *b = c;
}

void print_tab(int *tab, int size){
    printf("%d\n", size);
    for (int i = 0; i < size; i++)
        printf("%d\n", tab[i]);
}

int main()
{

    int n = 5;
    int tab[] = {6, -5, -1, 5, 1}; // 1 -1 5 -5 6

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n - 1; j++){
            if (tab[i] > tab[i + 1])
                fswap(&tab[i], &tab[i + 1]);
        }
    }
    printf("tst: %d\n\n", n);
    print_tab(tab, n);

    return 0;
}

Hello,

A quoi sert la variable j ? (oui, tu as été distrait).

Ligne 21, tab[i+1] est en dehors du tableau lorsque que i vaut n-1. Et de là, que le swap ait lieu ou pas, n'importe quoi peut se passer: plantage, dégradation de variable.

-
Edité par edgarjacobs 28 décembre 2021 à 19:47:25

Du coup ça expliquerait pourquoi n devient 0 : le tableau déborde sur la variable n. (Il suffit qu'elle soit stockée juste après, ce qui est possible.)

robun a écrit:

Du coup ça expliquerait pourquoi n devient 0 : le tableau déborde sur la variable n. (Il suffit qu'elle soit stockée juste après, ce qui est possible.)

Tout a fait !

D'ailleurs, quand on regarde les adresses des variables locales, (en tout cas ce que j'ai constaté chez moi, peut être pas valable de partout), souvent elles sont empilées dans l'ordre inverse :

Autrement dit, la variable n est rangée après le tableau statique.

Si on déclarait a,b,c,d dans la fonction, en mémoire ce serait d,c,b,a.

Et on donc un débordement du tableau bousille la variable n. 

Souvent quand on a des variables folles, c'est intéressant de regarder si les variables/tableaux déclarés juste après ne débordent pas.

L'accès à tab[n-1 + 1] est illégal (indice en dehors des bornes).

Savoir si c'est sur n que ça déborde, c'est compliqué. En fait, selon les niveaux d'optimisation, les variables peuvent etre logées en mémoire, ou dans des registres, voire être éliminées.

Ce qui est amusant, c'est que si on demande à afficher leur adresse, ça force le compilateur à les loger en mémoire, parce que sinon elles ne peuvent pas avoir d'adresse. Vouloir observer les variables, ca change leur concrétisation'par le compilateur.

En fait le seul moyen de voir ce que le compilateur fait, c'est de regarder la traduction en langage machine. Ça dépend du compilateur, des options etc.

Ceci dit quand on explique qu'une variable, c'est un nom pour désigner un emplacement, c'est vrai seulement  dans le monde merveilleux d'un modèle abstrait d'exécution qui est décrit par la norme, et qui sert de référence. 

Les compilateurs fabriquent autre chose, dont le comportement doit être équivalent, modulo les comportements déclarés indéfinis.

Un cas célèbre et particulièrement scabreux, c'est les boucles infinies qui peuvent être éliminées sous certaines conditions. Un programme qui boucle officiellement équivalent à un programme qui termine, merci le standard.

-
Edité par michelbillaud 29 décembre 2021 à 8:10:05

Merci beaucoup pour vos réponses, j'étais en train de serrer tout seul chez moi ..

Donc, si on part de ce principe il est possible avec un petit programme en C de modifier toutes les adresses d'un autre programme et du coup par exemple avoir une accès un soft payant ou carrément de le modifier ? (ce n'est pas mon but, mais juste dans l'idée) ?

Mais bon, revenons sur Terre quelque instants car je peine toujours à faire réaliser ce que je veux: trier en fonction du nombre 0 mais je sais pas, écrire ce que l'on souhaite n'est pas chose aisée. Si vous pouvez encore m'éclairer un petit peu svp

int main()
{
    int n = 5;
    int ref = 0;
    int tab[] = {6, -5, -1, 5, 1}; // 1 -1 5 -5 6

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n - 1; j++){
            if (tab[j] < 0 && -tab[j] > tab[j + 1])
                fswap(&tab[j], &tab[j + 1]);
        }
    }

    print_tab(tab, n);
    return 0;
}

En vous remerciant .

Theo_78 a écrit:

Merci beaucoup pour vos réponses, j'étais en train de serrer tout seul chez moi ..

[...]

C'est aussi pour cela qu'il est important de connaître et savoir utiliser des outils qui t'aident (bien plus rapidement que nous sur un forum). Des outils tels qu'un debuger, un memory profiler …

Theo_78 a écrit:

[...]

Donc, si on part de ce principe il est possible avec un petit programme en C de modifier toutes les adresses d'un autre programme et du coup par exemple avoir une accès un soft payant ou carrément de le modifier ? (ce n'est pas mon but, mais juste dans l'idée) ?

[...]

Oui, mais non …

Les OS modernes isolent les programmes. Ton programme quand il est en cours d'exécution ne voit que lui et rien d'autre (pour simplifier), pour lui c'est comme s'il tournait tout seul sur ta machine, s'il disposait de toute la mémoire et de tous les accès (suivant les droits qu'il possède).

Theo_78 a écrit:

[...]
Mais bon, revenons sur Terre quelque instants car je peine toujours à faire réaliser ce que je veux: trier en fonction du nombre 0 mais je sais pas, écrire ce que l'on souhaite n'est pas chose aisée. Si vous pouvez encore m'éclairer un petit peu svp
[...]

Le tri que tu désires implémenter sera un tri par comparaison. Un tri par comparaison est, comme son nom l'indique, un tri qui pour décider si un élément vient avant ou après un autre les compare.

Les tris usuels utilisent une comparaison simple (> ou < voire ≤ ou ≥). Ici tu dois utiliser une autre comparaison entre deux éléments. Tu vas comparer deux éléments non pas sur leur valeur mais sur la valeur de leur distance à 0 ; ce qui se simplifie tout simplement en leur valeur absolue.

a vient avant b ssi |a|<|b| (par exemple) …

-
Edité par White Crow 29 décembre 2021 à 14:09:05

-1 viens avant -5  car 1 < 5

 1 viens avant 5   car 1 < 5

ce qui nous fait -1, -5, 1, 5  ?

Ou bien je n'ai pas compris ?

Pour un tri à bulles, on a besoin de savoir si un truc vient avant un autre.

D'où une étape: écrire une fonction qui indique si la valeur a vient avant la valeur b dans l'ordre voulu.

Pour l'ordre croissant habituel, c'est

bool vient_avant(int a, int b) {
   return  a < b;
}

Exercice : ici on a l'ordre des valeurs absolues comme critère principal, et le signe comme critère secondaire ?

Il y a juste un petit détail auquel faire attention … INT_MIN et sa valeur absolue.

Sinon dans l'exemple dans le code :

int tab[] = {6, -5, -1, 5, 1}; // 1 -1 5 -5 6

tendrait à faire comprendre que Michel a raison de se soucier du signe car sinon un tri stable sur «la distance à 0» donnerait plutôt [-1, 1, -5, 5, 6].

Un autre point pour faire plus «classique» serait d'implémenter une fonction de comparaison «standard» qui lorsqu'on compare deux éléments a et b (dans cet ordre) renvoie -1 si a est plus petit (dans le sens «vient avant»), 0 si ils sont égaux (dans le sens «à la même distance») et 1 si b est plus petit …

C'est aussi pour cela qu'il est important de connaître et savoir utiliser des outils qui t'aident (bien plus rapidement que nous sur un forum). Des outils tels qu'un debuger, un memory profiler …

 Expliquer comme ça, c'est vrai que le concept parait puissant et donc mieux protéger je suppose ; donc un cracker préférera sortir son vieux XP

#include <stdlib.h>
#include <stdio.h>

void    print_tab(int *tab, int size)
{
    for (int i = 0; i < size; i++)
        printf("%d\n", tab[i]);
}

void    fswap(int *a, int *b)
{
    int c = *a;
    *a = *b;
    *b = c;
}

void    sort_array(int *tab, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size - 1; j++)
        {
            if (tab[j] > tab[j + 1])
                fswap(&tab[j], &tab[j + 1]);
        }
    }
}

int     get_distance(int a, int b)
{
    if (a > b)
        return a - b;
    return b - a;
}

int     is_in_array(int *tab, int size, int value)
{
    if (!tab)
        return 0;
    for (int i = 0; i < size; i++){
        if (tab[i] == value)
            return 1;
    }
    return 0;
}

int     *copy_my_tab(int *dst, int *src, int size)
{
    for (int i = 0; i < size; i++){
        dst[i] = src[i];
    }
    return dst;
}

void    sort_my_tab(int (*array)[], int size, int index)
{
    int *tab = *array;
    int distances[size];

    for (int i = 0; i < size; i++){
        distances[i] = get_distance(tab[i], index);
    }

    sort_array(distances, size);

    int result[size];
    int tmp[size];
    int indexResult = 0;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (distances[i] == get_distance(tab[j], index) && ( !is_in_array(tmp, size, j) || (i == 0 && j == 0) ) ){
                tmp[indexResult] = j;
                result[indexResult] = tab[j];
                indexResult++;
                break;
            }
        }
    }
    copy_my_tab(*array, result, size);
}

int main()
{
    int n = 4;
    int tab[] = {9, 5, 6, 2};

    sort_my_tab(&tab, n, 0);

    printf("Result\n\n");
    print_tab(tab, n);
    return 0;
}

Alors un mem profiler comme valgrind te dirais :

$ valgrind --leak-check=full --track-origins=yes --show-reachable=yes ./ocr
==382808== Memcheck, a memory error detector
==382808== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==382808== Using Valgrind-3.17.0 and LibVEX; rerun with -h for copyright info
==382808== Command: ./ocr
==382808== 
==382808== Conditional jump or move depends on uninitialised value(s)
==382808==    at 0x1092EC: is_in_array (ocr.c:41)
==382808==    by 0x109596: sort_my_tab (ocr.c:73)
==382808==    by 0x10968A: main (ocr.c:89)
==382808==  Uninitialised value was created by a stack allocation
==382808==    at 0x109450: sort_my_tab (ocr.c:66)
==382808== 
Result

5
6
9
==382808== Conditional jump or move depends on uninitialised value(s)
==382808==    at 0x48DDFD3: __vfprintf_internal (in /usr/lib/libc-2.33.so)
==382808==    by 0x48CA2DE: printf (in /usr/lib/libc-2.33.so)
==382808==    by 0x10919C: print_tab (ocr.c:7)
==382808==    by 0x1096AA: main (ocr.c:92)
==382808==  Uninitialised value was created by a stack allocation
==382808==    at 0x109450: sort_my_tab (ocr.c:66)
==382808== 
==382808== Use of uninitialised value of size 8
==382808==    at 0x48C43CB: _itoa_word (in /usr/lib/libc-2.33.so)
==382808==    by 0x48DDD9B: __vfprintf_internal (in /usr/lib/libc-2.33.so)
==382808==    by 0x48CA2DE: printf (in /usr/lib/libc-2.33.so)
==382808==    by 0x10919C: print_tab (ocr.c:7)
==382808==    by 0x1096AA: main (ocr.c:92)
==382808==  Uninitialised value was created by a stack allocation
==382808==    at 0x109450: sort_my_tab (ocr.c:66)
==382808== 
==382808== Conditional jump or move depends on uninitialised value(s)
==382808==    at 0x48C43DC: _itoa_word (in /usr/lib/libc-2.33.so)
==382808==    by 0x48DDD9B: __vfprintf_internal (in /usr/lib/libc-2.33.so)
==382808==    by 0x48CA2DE: printf (in /usr/lib/libc-2.33.so)
==382808==    by 0x10919C: print_tab (ocr.c:7)
==382808==    by 0x1096AA: main (ocr.c:92)
==382808==  Uninitialised value was created by a stack allocation
==382808==    at 0x109450: sort_my_tab (ocr.c:66)
==382808== 
==382808== Conditional jump or move depends on uninitialised value(s)
==382808==    at 0x48DE793: __vfprintf_internal (in /usr/lib/libc-2.33.so)
==382808==    by 0x48CA2DE: printf (in /usr/lib/libc-2.33.so)
==382808==    by 0x10919C: print_tab (ocr.c:7)
==382808==    by 0x1096AA: main (ocr.c:92)
==382808==  Uninitialised value was created by a stack allocation
==382808==    at 0x109450: sort_my_tab (ocr.c:66)
==382808== 
==382808== Conditional jump or move depends on uninitialised value(s)
==382808==    at 0x48DDEB7: __vfprintf_internal (in /usr/lib/libc-2.33.so)
==382808==    by 0x48CA2DE: printf (in /usr/lib/libc-2.33.so)
==382808==    by 0x10919C: print_tab (ocr.c:7)
==382808==    by 0x1096AA: main (ocr.c:92)
==382808==  Uninitialised value was created by a stack allocation
==382808==    at 0x109450: sort_my_tab (ocr.c:66)
==382808== 
0

La première erreur mentionnée est l'utilisation d'une variable non initialisée … et si tu regardes bien, en ligne 73 tu appelles is_in_array avec tmp que tu n'as pas initialisé …

Et tu en as d'autres des erreurs …

Attention, tu utilsies des VLA qui peuvent t'exploser la pile …

Merci pour ta réponse @White Crow, j'ai regardé ce qu'étaient des VLA, ok je comprend mais comment aurais-tu fais toi ? Juste pour avoir une petite idée et aussi m'améliorer. Et si tu peux me confirmer que tout est OK selon toi ? Le code fonctionne, je parle ici de petite idées d'amélioration ?

Merci

#include <stdlib.h>
#include <stdio.h>

void    print_tab(int *tab, int size)
{
    for (int i = 0; i < size; i++)
        printf("%d\n", tab[i]);
}

void    print_tab2(int *tab, int size)
{
    for (int i = 0; i < size; i++)
        printf("%d, ", tab[i]);
    printf("\n");
}

void    fswap(int *a, int *b)
{
    int c = *a;
    *a = *b;
    *b = c;
}

void    sort_array(int *tab, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size - 1; j++)
        {
            if (tab[j] > tab[j + 1])
                fswap(&tab[j], &tab[j + 1]);
        }
    }
}

int     get_distance(int a, int b)
{
    if (a < 0)
        a *= -1;
    if (b < 0)
        b *= -1;
    if (a > b)
        return a - b;
    return b - a;
}

int     is_in_array(int *tab, int size, int value)
{
    if (!tab)
        return 0;
    for (int i = 0; i < size; i++){
        if (tab[i] == value)
            return 1;
    }
    return 0;
}

int     *copy_my_tab(int *dst, int *src, int size)
{
    for (int i = 0; i < size; i++){
        dst[i] = src[i];
    }
    return dst;
}

void    sort_my_tab(int (*array)[], int size, int index)
{
    int *tab = *array;
    int distances[size];

    for (int i = 0; i < size; i++){
        distances[i] = get_distance(tab[i], index);
    }

    sort_array(distances, size);

    int result[size];
    int indexResult = 0;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (distances[i] == get_distance(tab[j], index) && is_in_array(result, i, tab[j]) == 0){
                result[indexResult] = tab[j];
                indexResult++;
                break;
            }
        }
    }
    copy_my_tab(*array, result, size);
}

int main()
{
    int n = 4;
    int tab[] = {-5, 4, -2, 3};

    sort_my_tab(&tab, n, -3);

    printf("Result\n\n");
    print_tab(tab, n);
    return 0;
}

-
Edité par Theo_78 30 décembre 2021 à 20:42:18

tldr;

mais bon essaye de mettre INT_MIN à une des valeurs de ton tableau … juste pour voir …

Ce que j'aurais fait ?

Beaucoup plus court en appliquant ce que j'ai écris dans un commentaire précédent.

Et surtout beaucoup plus de tests.

Edit : je m'explique.

Si tu dois tester un tri tu dois tester au moins des tableaux avec :

• une seule valeur ;
• deux valeurs bien choisies ;
• des valeurs un peu aléatoires ;
• des valeurs extrêmes (INT_MIN, INT_MAX) ;
• aucun élément ;
• déjà trié ;
• trié dans le sens inverse ;
• …

-
Edité par White Crow 30 décembre 2021 à 22:35:29

Puisque le sujet est marqué comme résolu ...
Dans un tri à bulles, à chaque passage on amène le plus "grand" en dernière position, et c'est tout ...
Ça ne sert à rien de trier tout le tableau aux tours suivants.
Au second tour on amène le deuxième plus grand en avant-dernière position.
etc.
Donc à chaque tour, on diminue la longueur à trier.

Pour s'en convaincre, on pourrait afficher juste avant et juste après la boucle for dans la fonction sorting()
-
#include <stdio.h>
#include <math.h>
void display(int tab[], int size) {   // J'affiche tout sur une seule ligne.
    printf("[%d]", size);
    for(int i = 0; i < size; i++) printf(" %d", tab[i]);
    printf("\n");
}
void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}
void sorting(int tab[], int size) {
    while(size > 1) {   // Je ne trie pas des tableaux de 1 élément.
        for(int i = 0; i < size-1; i++)
            // Compare les valeurs absolues. Si égales, place la valeur positive avant.
            if(abs(tab[i]) > abs(tab[i+1]) || (abs(tab[i]) == abs(tab[i+1]) && tab[i] < tab[i+1]))
                swap(&tab[i], &tab[i+1]);
        size--;   // Seule la copie locale est modifiée.
    }
}
int main(void){
    int tab[5] = {6, -1, 5, 1, -5};
    int n=5;
    display(tab, n);
    sorting(tab, n);
    display(tab, n);
    return 0;
}
-
[5] 6 -1 5 1 -5                                                                                                         
[5] 1 -1 5 -5 6

-
Edité par PierrotLeFou 31 décembre 2021 à 2:48:04

INT_MIN … Pierrot …

edit: avec ton code (en rajoutant un stdlib pour abs et limits pour INT_MIN) on obtient avec le tableau {INT_MIN, INT_MAX, 6, -1, 5, 1, -5} :

$ ./pierrot 
[7] -2147483648 2147483647 6 -1 5 1 -5
[7] -2147483648 1 -1 5 -5 6 2147483647

-
Edité par White Crow 31 décembre 2021 à 7:42:48

On a déjà discuté de INT_MIN, je ne le considère pas comme un nombre "normal".
Seul -0 devrait être égal à +0

edit:
Je teste avec -INT_MAX et INT_MAX et ça marche:
[7] 6 -1 2147483647 5 1 -2147483647 -5
[7] 1 -1 5 -5 6 2147483647 -2147483647

-
Edité par PierrotLeFou 31 décembre 2021 à 17:41:48