Punto informatico Network
Login Esegui login | Non sei registrato? Iscriviti ora (è gratuito!)
Username: Password:
  • Annuncio Pubblicitario

[Ansi C] Ordine crescente

Il forum per tutti i developer. Leggere attentamente il regolamento di sezione prima di postare.

[Ansi C] Ordine crescente

Messaggioda Monkey13 » dom gen 21, 2007 10:00 am

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. [^]
"La civiltà ebbe inizio quando per la prima volta l'uomo scavò la terra e vi gettò un seme." Kahlil Gibran
Avatar utente
Monkey13
Bronze Member
Bronze Member
 
Messaggi: 545
Iscritto il: gio giu 23, 2005 8:35 pm
Località: Padova (Vigodarzere)

Messaggioda Ices_Eyes » dom gen 21, 2007 11:28 am

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--;
    }
}
Avatar utente
Ices_Eyes
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5543
Iscritto il: ven ott 24, 2003 10:37 am
Località: Prov. di Venezia

Messaggioda M@ttia » dom gen 21, 2007 11:43 am

Ices_Eyes ha scritto: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);


[^]
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero


Messaggioda Monkey13 » dom gen 21, 2007 2:09 pm

Ok! Grazie per le risposte, ma che strano però, come mai mettono un esercizio così in un libro per le superiori?
"La civiltà ebbe inizio quando per la prima volta l'uomo scavò la terra e vi gettò un seme." Kahlil Gibran
Avatar utente
Monkey13
Bronze Member
Bronze Member
 
Messaggi: 545
Iscritto il: gio giu 23, 2005 8:35 pm
Località: Padova (Vigodarzere)

Messaggioda Ices_Eyes » dom gen 21, 2007 2:33 pm

Monkey13 ha scritto: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 [:D]
Avatar utente
Ices_Eyes
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5543
Iscritto il: ven ott 24, 2003 10:37 am
Località: Prov. di Venezia

Messaggioda M@ttia » dom gen 21, 2007 2:37 pm

Ices_Eyes ha scritto:
Monkey13 ha scritto: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 [:D]

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...
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Messaggioda Ices_Eyes » dom gen 21, 2007 2:38 pm

M@ttia ha scritto:
Ices_Eyes ha scritto:
Monkey13 ha scritto: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 [:D]

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 [std]
Avatar utente
Ices_Eyes
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5543
Iscritto il: ven ott 24, 2003 10:37 am
Località: Prov. di Venezia

Messaggioda Monkey13 » lun gen 22, 2007 10:11 am

Ices_Eyes ha scritto:
Monkey13 ha scritto: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 [:D]


Infatti sono in un istituto tecnico di informatica... [:D]
Però la cosa bizzarra è che è un esercizio del biennio, dove veniva posto anche con il pascal.
"La civiltà ebbe inizio quando per la prima volta l'uomo scavò la terra e vi gettò un seme." Kahlil Gibran
Avatar utente
Monkey13
Bronze Member
Bronze Member
 
Messaggi: 545
Iscritto il: gio giu 23, 2005 8:35 pm
Località: Padova (Vigodarzere)


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti

cron
Powered by phpBB © 2002, 2005, 2007, 2008 phpBB Group
Traduzione Italiana phpBB.it

megalab.it: testata telematica quotidiana registrata al Tribunale di Cosenza n. 22/09 del 13.08.2009, editore Master New Media S.r.l.; © Copyright 2008 Master New Media S.r.l. a socio unico - P.I. 02947530784. GRUPPO EDIZIONI MASTER Spa Tutti i diritti sono riservati. Per la pubblicità: Master Advertising