Lage et program som sorterer tall -stigende rekke

[arna]

Hvordan kan man best lage en kode som sorterer tall i stigende rekkefølge? Jeg har klart en grei løsning på det føler jeg men der er det bare 4 tall som er i bildet. Og koden ser forøvrig kanskje hårete ut. Noen forslag til forbedringer eller hvordan jeg skal skrive koden?

 

#include <iostream>

using namespace std;

 

void order(int&, int&, int&, int&);

int main()

{

int tall1, tall2, tall3, tall4;

 

  cout << "\nHva er tall1? ";  cin >> tall1;

  cout << "\nHva er tall2? ";  cin >> tall2;

  cout << "\nHva er tall3? ";  cin >> tall3;

  cout << "\nHva er tall4? ";  cin >> tall4;

  cout << "\n";

 

  order(tall1, tall2, tall3, tall4);

 

  cout << "\nLaveste tall er rangert i rekkefølge: "

      << "\n" << tall1

    << "\n" << tall2

    << "\n" << tall3

    << "\n" << tall4;

  return 0;

}

 

void order(int& t1,int& t2,int& t3,int& t4)

{

int temp; //hjelpevariabel

 

if( t1 > t4 )    //Hvis tall 1 er større enn 4

{    //bytter de plassering

  temp = t1; 

  t1 = t4;     

  t4 = temp; 

}

if ( t1 > t3)  //Hvis tall 1 er større enn 3

{    //bytter de plassering

  temp = t1; 

  t1 = t3; 

  t3 = temp; 

} 

if (t2 > t4)  //Hvis tall2 er større enn 4

{    //bytter de plassering

  temp = t2; 

  t2 = t4; 

  t4 = temp; 

}

  if (t2 > t3)  //Hvis tall2 er større enn 3

{      //bytter de plassering

  temp = t2;

  t2 = t3; 

  t3 = temp; 

}

}

[Belarnion]

f.eks med én array der du legger inn tallene i random rekkefølge, deretter en

prog. setning som oppretter enda en array.

Så lager du en løkke som søker gjennom den originale arrayen etter det minste tallet og setter det på plass 0 i den andre arrayen. Slik fortsetter den til alle tallene i den originale arrayen har blitt sortert i den siste arrayen.

Endret 15. oktober 2005 av oddarne84

[arna]

ååh. Bare synd jeg ikke har lært arrays enda hehe

[Gjakmarrja]

ååh. Bare synd jeg ikke har lært arrays enda hehe

5009774[/snapback]

 

Bruk .NET framework... det e lettere der!

[JBlack]

Siden jeg i liten grad har benyttet meg av templates selv tidligere, så tenkte jeg hvorfor ikke prøve å gjøre dette the c++ way. Andre får kritisere om jeg har gjort noe dumt.

 

#include <list>
#include <iostream>

#define ANTALL_TALL 4

using namespace std;

int getInt(int i){ //BUG: Håndterer ikke feil input fra bruker
 int ret;
 cout << "\nHva er tall " << i << "? ";
 cin >> ret;
 return ret;
}

void printList (list<int> &l,ostream &s=cout){
 list<int>::iterator i;
 for( i=l.begin(); i != l.end(); i++ ) s << *i << " ";
 s << endl;
}

int main(){
 list<int> l;

 for (int i=1;i<=ANTALL_TALL;i++) l.push_back(getInt(i));
 cout << "Lista over tall før sortering:\n";
 printList(l);
 l.sort();
 cout << "Lista over tall etter sortering:\n";
 printList(l);
}

[genstian]

du kan også gjøre

 

vector<int> tall(12345);
// tall[0] = 1; tall[1] = 5; tall[2] = 2; osv
// sort(tall.begin(), tall.end()); eller sort(tall.end(), tall.begin());
//tall[0] = 1, tall[1] = 2 tall[2] = 5 osv

[Peter]

Siden jeg i liten grad har benyttet meg av templates selv tidligere, så tenkte jeg hvorfor ikke prøve å gjøre dette the c++ way. Andre får kritisere om jeg har gjort noe dumt.

 

*snip*

 

Synes kodeløsningen din var helt fin, jeg tenkte å lage noe lignende.

Jeg tror dog jeg ville brukt vector av personlig preferanse.

 

Jeg hadde en lignende opgave for ikke lenge siden, men jeg måtte lage sorteringsalgoritmen på egen hånd. Synes det var veldig lærerikt, og anbefaler alle å være innom det før eller siden. Utfordringen er å gjøre det UTEN å bruke ekstra variabler.

[Klette]

En stygg 5min sak... trolig det mest uoptimaliserte som finnes, men den funker da

 

nazgul, med med mindre ekstra data enn dette?

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{

std::vector<int> tall;
std::vector<int>::iterator it;
std::vector<int>::iterator _it;

//Legg inn verdier
tall.push_back(3);
tall.push_back(5);
tall.push_back(2);
tall.push_back(4);
tall.push_back(1);

// Print listen før sortering
for(int i =0; i < 5; i++){ cout << tall[i] << " "; }
std::cout << std::endl;

//basis verdier
bool sorted = false;
it = tall.begin();

while(!sorted){

 if(it!=tall.end()) _it = it +1;
 if((int)(*it) > (int)(*_it))
 {
 	tall.push_back((int)(*it));
 	tall.erase(it);
 	it = tall.begin();
 	
 	for(int i =0; i < 5; i++){ cout << tall[i] << " ";} std::cout << std::endl;
 	
 }
 else 
 {
 	++it;
 	sorted = true;
 }

 if(it==tall.end() && sorted == true)
 {
 	sorted = true;
 }
 else {
 	sorted = false;
 }
  }


return 0;
}

[Peter]

Hehe, jeg skal se på det i morgen.

Vi burde nesten legge inn noe som tar tiden også, så det blir litt morsom konkurranse?

Da selvfølgelig med litt flere tall inne i bildet, f.eks. 1000 stk floats?

 

Regler:

Må bruke std::vector, da et array antakelig vil være raskere i dette tilfellet.

Sorteringalgoritmen må skrives egenhendig

Bruke minimum antall variabler for å utføre selve sorteringen

 

Noen flere regler?

Endret 15. oktober 2005 av Nazgul

[Klette]

hmm, vel kan jo poste resultatene til greia mi nå

500 000 sorteringer av en vector med 5 int verdier:

 

På min MacOSX 10.4 Powerbook (nyeste, husker ikke hastigheten )

 

Kristian-Klettes-PowerBook:~/Documents/Programmering klette$ time ./sortTest
3 5 2 4 1 
1 2 3 4 5 

real    0m2.407s
user    0m2.134s
sys     0m0.019s
Kristian-Klettes-PowerBook:~/Documents/Programmering klette$ time ./sorter  
3 5 2 4 1 
1 2 3 4 5 

real    0m11.307s
user    0m10.186s
sys     0m0.067s

 

der sorter er min algoritme, mens sortTest bruker sort(begin,end) greia

 

Koden for sortTest

#include <iostream>
#include <vector>

int main()
{
std::vector<int> tall2;

 tall2.push_back(3);
tall2.push_back(5);
tall2.push_back(2);
tall2.push_back(4);
tall2.push_back(1);

 for(int i =0; i < 5; i++){ std::cout << tall2[i] << " "; }
std::cout << std::endl;

for(int runs2 = 0; runs2 < 500000; runs2++)
{
tall2.clear();
tall2.push_back(3);
tall2.push_back(5);
tall2.push_back(2);
tall2.push_back(4);
tall2.push_back(1);

sort(tall2.begin(), tall2.end());
}

 for(int i =0; i < 5; i++){ std::cout << tall2[i] << " "; }
std::cout << std::endl;

return 0;

}

Endret 15. oktober 2005 av Klette

[Klette]

Noen flere regler?

 

 

Vel, sorteringsfunksjonen må støtte alle typer tallverdier (int, double, floats etc).

 

ikke bare tiden den tar men også antall itereringer burde telle.

min nåværende algortime får

iterasjoner = (entries / 2) * (entries-1)

 

kun c++/c kode, ikke asm.

 

må kunne compile på alle plattformer som støtter c++ skikkelig.

 

 

noe mer?

[Dead_Rabbit]

Hehe. Morsomt.

*tenke ut en revolusjonerende algorithme*

[Klette]

Her kommer i hvertfall mitt innslag til konkuransen:

template<class T>	
std::vector<T> SortVector(std::vector<T> &data)
{

typename std::vector<T>::iterator it;
typename std::vector<T>::iterator _it;

bool sorted = false;
it = data.begin();
int numruns = 0;

while(!sorted){

 if(it!=data.end()) _it = ++it; --it;
 
 if((T)(*it) > (T)(*_it))
 {
 	data.push_back((T)(*it));
 	data.erase(it);
 
 	numruns++;
 }
 else 
 {
 	++it;
 	sorted = true;
 }
 if(it==data.end() && sorted == true)
 {
 	sorted = true;
 	//cout << "Number of iterations: " << numruns << endl;
 	return data;
 }
 else {
 	sorted = false;
 }
  }
  
}

 

Denne gir som sagt (n/2)*(n-1) iterasjoner for å sortere. (Bedre å si det slik enn ved tid, da tiden er veldig cpu avhengig...)

Dataene kopieres ikke i særlig grad og den vil derfor ikke ta opp mer minne enn nødvendig.

Koden burde fungere greit på std::list også, da den sorterer sekvensielt.

Endret 16. oktober 2005 av Klette

[Peter]

template<class T>
void sortVector(std::vector<T>& _vec) {
int numRuns=0;

bool moved;
T s;
int start = -1,end = _vec.size();
for(int x=0;x<500000;x++) {
       while(start++ != end--) {
 	moved = false;
 	for(int i=start;i<end;i++) {
   if(_vec[i] > _vec[i+1]) {
   	s = _vec[i];
   	_vec[i] = _vec[i+1];
   	_vec[i+1] = s;
   	moved = true;
   }
   ++numRuns;
 	}
 	for(int i=end;i>start;i--) {
   if(_vec[i-1] > _vec[i]) {
   	s = _vec[i];
   	_vec[i] = _vec[i-1];
   	_vec[i-1] = s;
   	moved = true;
   }
   ++numRuns;
 	}
 	if(moved == false) break;
 }
}
std::cout << "Its: " << numRuns << std::endl;
}

 

Her er mitt forslag.

Synes ikke det blir helt riktig å ta etter iterasjoner heller, da min itererer mye mer enn din, men iterasjonene mine blir kortere for hver iterasjon (om du skjønner hva jeg mener)

 

Tror dog ikke at min er noe raskere enn din, snarere tvert imot. Sikkert noen muligheter for optimaliseringer, men jeg måtte bare legge ut noe så det ikke virket som jeg trakk meg

 

Hadde du giddet å kjøre denne med time på powerbooken din da jeg ikke har noe *nix miljø tilgjengelig?

[Klette]

Med 2000 int tall bruker din cirka 6.5sek uten noen gcc optimaliseringer, mens min bruker rett under 12sek.

Så din slår meg nok der

 

Til mitt forsvar kan jeg jo si at min støtter også std::list ved kun få håndgrep

 

 

Merkelig egentlig, prøvde samme metoden (Det å jobbe seg inn fra hver ende), men det resulterte i tregere kode hos meg. brukte også en random søker i midten ved lange lister med hell. Ulempen med dette var jo at koden ikke ble brukbar for lists lengre.... Og der har du vel hvorfor du har en kjappere kode. Du kan swape mellom dataene ved hjelp av random access ([] operatoren), noe som en sekvensiell søker ikke kan (kan selvfølgene legge til en ekstra data slik som du har gjort og kopiere dataen for å så øke eller minke iteratoren, men målet var jo så lite eksta data som mulig.

Endret 17. oktober 2005 av Klette

[Peter]

Tror faktisk koden min kan optimaliseres ved å bruke pointers i stedet for de aktuelle verdiene. Dvs at s er en T* istedet for bare T. Lite å hente på integere, men på float og double burde det jo være noe.

 

 

Må bare legge til at jeg synes du vant denne konkurransen da målet først og fremst var å bruke så lite variabler som mulig.

Endret 17. oktober 2005 av Nazgul

[Klette]

vi kan si uavgjort siden min fungerer på lists også. Din er helt klart en bedre løsning på vectorer. Sjekket minneforbruker, og det er tilnærmet likt. Kan analyserer de to forskjellige litt grundigere i morgen da jeg har litt mer verktøy tilgjengelig på pcen hjemme.

 

Gratulerer til oss begge (med mindre noen fler kommer med forslag da... zirener! få opp farte din sopp.. )

[Dead_Rabbit]

Sopp kan du selv være!

Hehe Uansett...

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

template <class T>
void sortc(vector<T>&);

int main()
{
       cout << "Enter a couple of numbers to sort: ";
       vector<int> numbers;
       int num;
       while(cin >> num)
               numbers.push_back(num);

       cout << "Sorting... \n";
       
       sortc(numbers);

       for(vector<int>::const_iterator it = numbers.begin(); it!=numbers.end(); it++)
               cout << (*it) << " ";

       cout << endl;

       return 0;
}

template <class T>
void sortc(vector<T>& con)
{
       for(int j = con.size()-1; j !=0; --j) {
               for(int i = con.size()-1; i !=0; --i) 
                       if(con[i] < con[i-1])
                       swap(con[i], con[i-1]);
       }
}

 

Edit: copy-paste-life

(edit2: Må si jeg er veldig skeptisk til hvor effektiv denne algorithmen er, hehe)

Endret 18. oktober 2005 av zirener

[Dead_Rabbit]

Uansett, det beste hadde vel vært å bruke std::sort.

[don_Vito]

std::sort benytter vel flettesortering (?) som er en bra metode,de vil holde stabil seg på O(n log n).. Quicksort er vel ikke så raskt, vil variere.

 

Ordersort er raskere enn quicksort og bubblesort...

Endret 18. oktober 2005 av don_Vito