[Ansi C] Ordine crescente

[Monkey13]

Salva tutti!
Ho appena iniziato a studiare gli array e ora mi sono posto un problema da solo che vorrei risolvere, perché non ci sto dormendo alla notte.

Dato un array-1 di n interi, ordinare gli elementi dell'array in ordine crescente.

Ho provato in svariati modi ma le mie idee sono andate sempre in fallimento. Qualcuno potrebbe scrivere la funzione che esegue questo (penso banale per voi) problema?
Grazie.

[Ices_Eyes]

Monkey, stai chiedendo una cosa che impiega un bel pezzo del corso universatario di base..Esistono moltissimi metodi per ordinare un array, più o meno costosi in termini di tempo i spazio.

Il più semplice direi che è l'algoritmo BubbleSort, che non fa altro che scambiare due numeri vicini, mettendo il maggiore a destra e il minore a sinistra...

Una implementazione può eseere questa:

Codice: Seleziona tutto

void BubbleSort(int* array, int Nelem) {
    int i
    int tmp;

    while (Nelem > 0) {
        for (i=0; i<Nelem - 1; i++) {
            if (array[i] > array[i+1]) {
                tmp = array[i];
                array[i] = array[i+1];
                array[i+1] = tmp;
            }
        }
        Nelem--;
    }
}


[M@ttia]

Monkey, stai chiedendo una cosa che impiega un bel pezzo del corso universatario di base..Esistono moltissimi metodi per ordinare un array

Vero, pure io che faccio matematica ad "algoritmi e Complessità" una buona parte era proprio su questo tipo di Algoritmo (con vari studi dei tempi di esecuzione, analisi ammortizzate, ecc.).

comunque se ti serve solo che funzioni (cioè nessuno ti chiede di scriverne una tu), puoi semplicemente fare (in C++):

Codice: Seleziona tutto

#include <algorithm>
#include <vector>

....

  vector<TipoCheVuoi> MiaArray;
  sort(MiaArray.begin(), MiaArray.end());   


Se invece ne devi proprio implementare una tu, allora io propenderei per un MergeSort o un QuickSort: il Mergesort lo fai ad es. così:

Codice: Seleziona tutto

template<class Typ>
void Merge(vector<Typ>& A, unsigned int i1, unsigned int f1, unsigned int f2)
{
  unsigned int i1_ = i1;

  // X is an Auxiliary Array of Lenght f2- i1 + 1
  vector<Typ> X(f2 - i1 + 1);

  unsigned int i  = 0;
  unsigned int i2 = f1 + 1;

  while (i1 <= f1 && i2 <= f2)
  {
    if (A[i1] <= A[i2])
    {
      X[i] = A[i1];
      ++i; ++i1;
    }
    else
    {
      X[i] = A[i2];
      ++i; ++i2;
    }
  }

  if (i1 <= f1)
  {
    // Copy A[i1; f1] to the End of X
    for (unsigned int j = i1; j <= f1; ++j, ++i) X[i] = A[j];
  }
  else
  {
    // Copy A[i1; f2] to the End of X
    for (unsigned int j = i2; j <= f2; ++j, ++i) X[i] = A[j];
  }

  // Copy X in A[i1; f2]
  for (unsigned int j = 0; j < X.size(); ++j, ++i1_) A[i1_] = X[j];
}

template<class Typ>
void MergeSort(vector<Typ>& A, unsigned int i, unsigned int f)
{
  if (i >= f) return;
  unsigned int m = (i + f)/2;
  MergeSort(A, i, m);
  MergeSort(A, m+1, f);
  Merge(A, i, m, f);
}

...
  vector<TipoCheVuoi> MiaArray;
  MergeSort(MiaArray, 0, MiaArray.size()-1);


[Monkey13]

Ok! Grazie per le risposte, ma che strano però, come mai mettono un esercizio così in un libro per le superiori?

[Ices_Eyes]

Ok! Grazie per le risposte, ma che strano però, come mai mettono un esercizio così in un libro per le superiori?

Bhè, tutto dipende da cosa è richiesto nell'esrcizio. Io li ho fatti tutti anche alle superiori, ma ho fatto informatica, quindi è comprensibile. Il problema è la l'analisi della complessità eccetera, non tanto l'algoritmo in se...Discorso a parte per il quick sort che per me rimarrà sempre una magia

[M@ttia]

Ok! Grazie per le risposte, ma che strano però, come mai mettono un esercizio così in un libro per le superiori?

Bhè, tutto dipende da cosa è richiesto nell'esrcizio. Io li ho fatti tutti anche alle superiori, ma ho fatto informatica, quindi è comprensibile. Il problema è la l'analisi della complessità eccetera, non tanto l'algoritmo in se...Discorso a parte per il quick sort che per me rimarrà sempre una magia

Beh il quicksort ha tempo = (-) (n*log(n)), poiché si basa su una "media" di come statisticamente si sceglie il punto casuale che fa da divisore (non ti scrivo tutta l'analisi perché è lunghetta e magari l'ha anche fatta). Nel caso di sfiga totale il tempo è Omega(n^2), ma solo teoricamente con la sfiga + totale...

[Ices_Eyes]

Ok! Grazie per le risposte, ma che strano però, come mai mettono un esercizio così in un libro per le superiori?

Bhè, tutto dipende da cosa è richiesto nell'esrcizio. Io li ho fatti tutti anche alle superiori, ma ho fatto informatica, quindi è comprensibile. Il problema è la l'analisi della complessità eccetera, non tanto l'algoritmo in se...Discorso a parte per il quick sort che per me rimarrà sempre una magia

Beh il quicksort ha tempo = (-) (n*log(n)), poiché si basa su una "media" di come statisticamente si sceglie il punto casuale che fa da divisore (non ti scrivo tutta l'analisi perché è lunghetta e magari l'ha anche fatta). Nel caso di sfiga totale il tempo è Omega(n^2), ma solo teoricamente con la sfiga + totale...

Si si, l'ho fatta varie volte, e, l'ho anche capito... La magia sta per me nel come in sè l'algoritmo procede

[Monkey13]

Ok! Grazie per le risposte, ma che strano però, come mai mettono un esercizio così in un libro per le superiori?

Bhè, tutto dipende da cosa è richiesto nell'esrcizio. Io li ho fatti tutti anche alle superiori, ma ho fatto informatica, quindi è comprensibile. Il problema è la l'analisi della complessità eccetera, non tanto l'algoritmo in se...Discorso a parte per il quick sort che per me rimarrà sempre una magia

Infatti sono in un istituto tecnico di informatica...
Però la cosa bizzarra è che è un esercizio del biennio, dove veniva posto anche con il pascal.