Partizionamento Array In C

[Yoichi]

Salve a tutti, ho da poco iniziato a studiare informatica. Avevo in mente di fare un programma in C (che conosco davvero poco, sono nuovo alla programmazione) che facesse la partizione di un array secondo un elemento discriminante "x", cioè, tutti gli elementi<x devono andare a sinistra e tutti quelli>x devono andare a destra. Ci sto provando ormai da due giorni, ma quando vado a stampare gli elementi dell'array me li restituisce esattamente nello stesso ordine.

#include <stdio.h>
int main()
{
  int a[100];
  int i,j,n,x,t;
   i=1;
 
    printf("Inserisci il numero di elementi: \n");
    scanf("%d", &n);
     j=n;
    printf("Inserisci il discriminante: \n");
    scanf("%d", &x);
    for(i=1;i<n;i++) {
       printf("Inserisci gli elementi: \n");
       scanf("%d", &a[i]);
     }
     for(i=1;i<n;i++) {
        if(a[i]<=x) {
            i = i+1;
        }
        if(a[i]>x) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            j= j-1;
       }
    }
   for(i=1;i<n;i++)
       printf("%d\n", a[i]);
return 0;
}

 

[Marcus Aseth]

in C++ è così (codice sotto) però non so quanto di questo codice puoi usare anche in C.

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

void PrintArray(int(&arr)[10], string &&s)
{
    cout << s;
    for (auto &n : arr) { cout << n << " "; }
    cout << endl;
}

int main()
{
    int val[10]{ 7,6,2,3,0,9,8,1,5,4 };
    PrintArray(val, "Before Sort:\n");

    sort(&val[0], &val[10]);
    PrintArray(val, "After Sort:\n");

    stable_partition(&val[0], &val[10], bind2nd(greater_equal<int>(), 5));
    PrintArray(val, "After Partition, greater or equal 5 to the left:\n");
    return 0;
}

Risultato:

Before Sort:
7 6 2 3 0 9 8 1 5 4
After Sort:
0 1 2 3 4 5 6 7 8 9
After Partition, greater or equal 5 to the left:
5 6 7 8 9 0 1 2 3 4
Premere un tasto per continuare . . .

 

[rodhellas]

in C++ è così (codice sotto) però non so quanto di questo codice puoi usare anche in C.

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

void PrintArray(int(&arr)[10], string &&s)
{
    cout << s;
    for (auto &n : arr) { cout << n << " "; }
    cout << endl;
}

int main()
{
    int val[10]{ 7,6,2,3,0,9,8,1,5,4 };
    PrintArray(val, "Before Sort:\n");

    sort(&val[0], &val[10]);
    PrintArray(val, "After Sort:\n");

    stable_partition(&val[0], &val[10], bind2nd(greater_equal<int>(), 5));
    PrintArray(val, "After Partition, greater or equal 5 to the left:\n");
    return 0;
}

Risultato:

Before Sort:
7 6 2 3 0 9 8 1 5 4
After Sort:
0 1 2 3 4 5 6 7 8 9
After Partition, greater or equal 5 to the left:
5 6 7 8 9 0 1 2 3 4
Premere un tasto per continuare . . .

Può usare solo il return 0 :lol:.

 

[rodhellas]

Comunque @Yoichi , ci sono vari errori da correggere:
Fare i = 1 non ha senso se poi lo fai in ogni for;
E' prassi comune contare le posizione degli array partendo da 0 ( perchè più efficiente e simile al conteggio che fa il computer). Se lo fai partire da 1, devi contare anche la posizione n (tant'è che nei tuoi cicli ti perdi sempre un valore). Non solo, ma j deve essere uguale ad n-1, sennò vai fuori array;
Nel secondo for (quello per scambiare valore), non devi fare i = i+1, c'è già il for che incrementa l'indice ( rischiando di andare in segmentation fault );
Ad occhio, ti ritorna lo stesso array perchè vai a fare due volte lo scambio.
Per finire, alla fine tutto il tuo ragionamento si può ricondurre ad ordinare l'array in ordine crescente (o decrescente se lo vuoi fare al contrario).

 

[Marcus Aseth]

Bhe, alla luce dei fatti direi che c'è un altro errore nel codice, difficile da notare:

Spoiler

Il fatto che stai utilizzando C anzichè C++ :lol:

 

[Yoichi]

Comunque @Yoichi , ci sono vari errori da correggere:
Fare i = 1 non ha senso se poi lo fai in ogni for;
E' prassi comune contare le posizione degli array partendo da 0 ( perchè più efficiente e simile al conteggio che fa il computer). Se lo fai partire da 1, devi contare anche la posizione n (tant'è che nei tuoi cicli ti perdi sempre un valore). Non solo, ma j deve essere uguale ad n-1, sennò vai fuori array;
Nel secondo for (quello per scambiare valore), non devi fare i = i+1, c'è già il for che incrementa l'indice ( rischiando di andare in segmentation fault );
Ad occhio, ti ritorna lo stesso array perchè vai a fare due volte lo scambio.
Per finire, alla fine tutto il tuo ragionamento si può ricondurre ad ordinare l'array in ordine crescente (o decrescente se lo vuoi fare al contrario).

Ho provato cosi' ma restituisce lo stesso ordine iniziale...

int partizionamento(int a[], int n)
{ //Dichiarazione delle variabili
  int t;
  int i=0;
  int j=n;
  int x;
     for(i=0;i<n;i++){
    printf("Inserisci un numero: \n");
     scanf("%d", &a[i]);
  }

  //Inserimento dell'elemento discriminante
  printf("Inserisci il discriminante: \n");
  scanf("%d", &x);
  /*Gli elementi continuano ad essere esaminati finchè a sinistra non si trova un elemento>x ed a destra un elemento<x */
    while((a[i]<x)&&(i<j)) i++;
    while((a[j]>x)&&(i<j)) j--;
     /*Quando si incontra un elemento a sinistra maggiore di x oppure un elemeno a destra minore di x, si effettua lo scambio */
      while(j>i)
{
         a[i]=t;
          a[i]=a[j];
           a[j]=t;
            i++;
             j--;
              while(a[i]<x) i++;
              while(a[j]>x) j--;





}

}
  //Inizio main
int main(){
int n;
int i;
  printf("Inserisci il numero di elementi: \n");
   scanf("%d", &n);

int a[n];

   partizionamento(a,n);
     for(i=0;i<n;i++)
{
        printf("Array ordinato:%d\n", a[i]);



}








return 0;
}

 

[Marcus Aseth]

Ecco qua (codice sotto).
Lo scritto in modo che sia il piu compatibile possibile con C nel limite delle mie conoscenze, al massimo devi sostituire i cout e cin con i prinf e scanf.
Ma per il resto, funziona.
Alcuni consigli riguardo al tuo codice: Dividi il tutto in quante piu funzioni possibile, non avere una funzione chiamata "partiziona" che si occupa di riempire l'array, ogni funzione deve fare quello che dice.
Nel mio codice è brutto persino il fatto che venga chiesto "Inserisci discriminante: " all'interno di partition, dovrebbe essere chiesto fuori e passato a partition tramite variabile, ho lasciato così perchè son di corsa e non voglio che mi si sfreddi la cena xD
Cmq, evita tutte quelle lettere, ti confondono e basta. Ragiona sul senso della tua variabile e dagli un nome che rispecchia le tue intenzioni e ti aiuta a ragionarci sopra, niente j,n,t,x ,le parole che scrivi nel codice son gratuite quindi mettici un pò più lettere e pensa sempre nell'ottica di qualcun altro che apre il tuo codice e lo legge, vuoi passargli quante piu informazioni possibili.
Commenti come "//Dichiarazione delle variabili" sono abbastanza inutili perchè se vediamo int x; sappiamo che si tratta della dichiarazione di una variabile, equivale all'aver scritto la dichiarazione 2 volte, quindi quando il codice si commenta da sè non commentarlo ;)

#include <iostream>
using namespace std;

int CreateArray(int* (&arr));
void FillArray(int vals[], int size);
void Partition(int vals[], int size);
void PrintArray(int vals[], int size);

int main()
{
    int size, *vals;

    size = CreateArray(vals);

    FillArray(vals, size);

    Partition(vals, size);

    PrintArray(vals, size);

    delete[] vals;
    return 0;
}
int CreateArray(int* (&arr))
{
    int size;
    cout << "Inserisci il numero di elementi: \n";
    cin >> size;
    arr = new int[size];
    return size;
}

void FillArray(int vals[], int size)
{
    cout << "Inserisci " << size << " numeri: \n";
    for (int i = 0; i < size; i++)
    {
        cin >> vals[i];
    }
}

void Partition(int vals[], int size)
{
    int target;
    cout << "Inserisci discriminante: \n";
    cin >> target;

    int left = 0;
    int right = size / 2;

    for (; right < size; left++, right++)
    {
        while (vals[left] < target && left <= size / 2) { left++; }
        while (vals[right] > target && right <= size) { right++; }

        if (left != size / 2 && right != size)
        {
            int temp = vals[left];
            vals[left] = vals[right];
            vals[right] = temp;
        }
        else
        {
            break;
        }
    }

}

void PrintArray(int vals[], int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << vals[i] << " ";
    }
    cout << endl;
}

Risultato:
I piu piccoli del discriminante vanno a sinistra, i piu grandi a destra (non prende in considerazioni molte situazioni quindi se vuoi c'è molto spazio per migliorare il codice)

Inserisci il numero di elementi:
10
Inserisci 10 numeri:
9 8 7 6 5 4 3 2 1 0
Inserisci discriminante:
5
4 3 2 1 0 9 8 7 6 5
Premere un tasto per continuare . . .

 

[Yoichi]

Ecco qua (codice sotto).
Lo scritto in modo che sia il piu compatibile possibile con C nel limite delle mie conoscenze, al massimo devi sostituire i cout e cin con i prinf e scanf.
Ma per il resto, funziona.
Alcuni consigli riguardo al tuo codice: Dividi il tutto in quante piu funzioni possibile, non avere una funzione chiamata "partiziona" che si occupa di riempire l'array, ogni funzione deve fare quello che dice.
Nel mio codice è brutto persino il fatto che venga chiesto "Inserisci discriminante: " all'interno di partition, dovrebbe essere chiesto fuori e passato a partition tramite variabile, ho lasciato così perchè son di corsa e non voglio che mi si sfreddi la cena xD
Cmq, evita tutte quelle lettere, ti confondono e basta. Ragiona sul senso della tua variabile e dagli un nome che rispecchia le tue intenzioni e ti aiuta a ragionarci sopra, niente j,n,t,x ,le parole che scrivi nel codice son gratuite quindi mettici un pò più lettere e pensa sempre nell'ottica di qualcun altro che apre il tuo codice e lo legge, vuoi passargli quante piu informazioni possibili.
Commenti come "//Dichiarazione delle variabili" sono abbastanza inutili perchè se vediamo int x; sappiamo che si tratta della dichiarazione di una variabile, equivale all'aver scritto la dichiarazione 2 volte, quindi quando il codice si commenta da sè non commentarlo ;)

#include <iostream>
using namespace std;

int CreateArray(int* (&arr));
void FillArray(int vals[], int size);
void Partition(int vals[], int size);
void PrintArray(int vals[], int size);

int main()
{
    int size, *vals;

    size = CreateArray(vals);

    FillArray(vals, size);

    Partition(vals, size);

    PrintArray(vals, size);

    delete[] vals;
    return 0;
}
int CreateArray(int* (&arr))
{
    int size;
    cout << "Inserisci il numero di elementi: \n";
    cin >> size;
    arr = new int[size];
    return size;
}

void FillArray(int vals[], int size)
{
    cout << "Inserisci " << size << " numeri: \n";
    for (int i = 0; i < size; i++)
    {
        cin >> vals[i];
    }
}

void Partition(int vals[], int size)
{
    int target;
    cout << "Inserisci discriminante: \n";
    cin >> target;

    int left = 0;
    int right = size / 2;

    for (; right < size; left++, right++)
    {
        while (vals[left] < target && left <= size / 2) { left++; }
        while (vals[right] > target && right <= size) { right++; }

        if (left != size / 2 && right != size)
        {
            int temp = vals[left];
            vals[left] = vals[right];
            vals[right] = temp;
        }
        else
        {
            break;
        }
    }

}

void PrintArray(int vals[], int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << vals[i] << " ";
    }
    cout << endl;
}

Risultato:
I piu piccoli del discriminante vanno a sinistra, i piu grandi a destra (non prende in considerazioni molte situazioni quindi se vuoi c'è molto spazio per migliorare il codice)

Inserisci il numero di elementi:
10
Inserisci 10 numeri:
9 8 7 6 5 4 3 2 1 0
Inserisci discriminante:
5
4 3 2 1 0 9 8 7 6 5
Premere un tasto per continuare . . .

Grazie mille, ragionerò ancora sul codice che ho scritto, ci sto da giorni e non capisco perchè non entri nei cicli while.Sorry per i commenti "sbagliati", come ho detto ho iniziato da poco e devo ancora prenderci la mano. Grazie dei consigli :)

 

[Marcus Aseth]

Non ho commentato il mio codice quindi te lo spiego qui, nel caso ci siano confusioni:

while (vals[left] < target && left <= size / 2) { left++; }
while (vals[right] > target && right <= size) { right++; }

In pratica left e right lavorano su 2 parti diverse dell'array, left può "camminare" da index 0 a metà, right parte da metà ed avanza fino ad 1 oltre l'ultimo index (se hai 10 elementi, l'ultimo index è 9 ma right avanza fino a index 10).

I while escono dai rispettivi loop quando trovano dei valori adatti ad essere scambiati fra loro .

 if (left != size / 2 && right != size)
{
     //scambia left e right
}
else
{
    //esci dal loop
}

se right è uguale all'index oltre la fine dell'array, 10 nel mio esempio, allora usciamo dal loop.
Se left si trova a metà dell'array, di nuovo usciamo.
Se nessuna delle 2, entrambi sono index ad un valore valido per lo scambio e quindi li scambiamo ed il loop continua a cercare fino a che le condizioni per l'uscita non si verificano.

 

[Yoichi]

Non ho commentato il mio codice quindi te lo spiego qui, nel caso ci siano confusioni:

while (vals[left] < target && left <= size / 2) { left++; }
while (vals[right] > target && right <= size) { right++; }

In pratica left e right lavorano su 2 parti diverse dell'array, left può "camminare" da index 0 a metà, right parte da metà ed avanza fino ad 1 oltre l'ultimo index (se hai 10 elementi, l'ultimo index è 9 ma right avanza fino a index 10).

I while escono dai rispettivi loop quando trovano dei valori adatti ad essere scambiati fra loro .

 if (left != size / 2 && right != size)
{
     //scambia left e right
}
else
{
    //esci dal loop
}

Ho provato tradurre il codice in C, però l'ultimo elemento se minore del discriminante non viene spostato, può essere che l'ultimo elemento non venga verificato?

se right è uguale all'index oltre la fine dell'array, 10 nel mio esempio, allora usciamo dal loop.
Se left si trova a metà dell'array, di nuovo usciamo.
Se nessuna delle 2, entrambi sono index ad un valore valido per lo scambio e quindi li scambiamo ed il loop continua a cercare fino a che le condizioni per l'uscita non si verificano.