Programmera spel i C++ för nybörjare/C++ referenser online/sortera listor i C++ för nybörjare

Bubble sort

Listor är vanligt förekommande i alla typer av C++ programmering. Det finns många olika sätt att sortera listor men den enklaste av allihop kallas "bubble sort". Namnet har metoden fått som jämförelse av kolsyrebubblor i ett glas läsk som långsamt flyter upp till ytan.

Principen för bubble sort är riktigt enkel. Enligt den här principen flyttas de högre talen uppåt och de lägre neråt tills de kommit i rätt ordning, men man kan naturligtvis göra helt tvärtom:

• Man tar en lista med nummer
• Man jämför det första numret med det andra numret
• Är det första numret lägre byter numren plats.
• Man hoppar till post två och jämför med post tre
• Om numret på post två lägre än post tre byter numren plats.
• Fortsätt så hela listan igenom och börja om med post ett om man sorterat någon post i listan
• Om man gått igenom hela listan utan att en enda post bytt plats är listan färdigsorterad.

Fördel

Mängden kod som krävs för att sortera listan är minimal.

Nackdel

Det är den sorteringsmetod som tar allra längst tid så den bör bara användas på korta listor.

Kodexempel:

//Så här kan bubblesortfunktionen se ut
void bubbleSort(int *array, int length)//Bubble sort funktion 
{
   int i; //Räknare från 0 till listlängd
	int j; // Räknare 

   for(i=0;i<length;i++) //räkna listan
   {
       for(j=0; j< i;j++) //Så länge det finns ett j som är mindre än i
			            //så länge kommer siffror att byta plats
       {
           if(array[i]>array[j]) //Om siffran i listan är störren än j
           {
               int temp=array[i]; //byt plats siffran i listan med temp
               array[i]=array[j]; //byt plats så på i och j
               array[j]=temp; // ge j värdet som i hade innan
               printElements(array, length); //skriv ut värdena på skärman
           }
       }

   }

}

Om du vill se effekterna av sorteringen kan du skriva ut alla elementen i listan med:

void printElements(int *array,int length) //skriv ut varje post i listan
{
   int i=0;
   for(i=0;i<length;i++)
       cout<<array[i]<<", ";
   cout << endl;
}

Bubble sort, komplett kodexempel:

#include "stdafx.h"
#include <iostream>
using namespace std;

void bubbleSort(int *array, int length);
//Innehåller en lista med heltal och en siffra över hur lång listan är

void printElements(int *array,int length);
//Innehåller samma sak

int main(int argc, _TCHAR* argv[])
{
 	const int length = 10; //Listans längd
	int Bubble[length]={0,1,2,3,4,5,6,7,8,9};
       //Jag valde 0-10 bara för att visa tydligt hur det fungerar
	bubbleSort(Bubble,length);
	return 0;
}

//Funktionerna
 void printElements(int *array,int length) //skriv ut varje post i listan
{
   int i=0;
   for(i=0;i<length;i++)
    cout<<array[i]<<", ";
    cout << endl;
}

void bubbleSort(int *array, int length)//Bubble sort funktion 
{
  int i; //Räknare från 0 till listlängd
  int j; // Räknare 

   for(i=0;i<length;i++) //räkna listan
   {
       for(j=0;j< i;j++) //Så länge det finns ett j som är mindre än i
			            //så länge kommer siffror att byta plats
       {
           if(array[i]>array[j]) //Om siffran i listan är störren än j
           {
               int temp=array[i]; //byt plats siffran i listan med temp
               array[i]=array[j]; //byt plats så på i och j
               array[j]=temp; // ge j värdet som i hade innan
               printElements(array, length); //skriv ut värdena på skärman
           }
       }

   }

}

Qsort

Ett mycket snabbare sätt att sortera en lista är funktionen "qsort". Den finns med som standardfunktion i C++ vilket innebär att det inte är särskilt mycket kod att skriva, men samtidigt är funktionens matematik dold för oss vanliga användare. Men det kanske är tur för alla nybörjare. Funktionen finns definierad på engelska här: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

Här nedanför ser du exempelkod på hur qsort sorterar upp sex olika siffror och placerar dem i stigande följd i en lista:

 #include "stdafx.h"
 #include <iostream>
 using namespace std;

int compare (const void * a, const void * b);//förprogrammerad funktion

int main ()
{
 int n; //räknare i listan
 int values[] = { 40, 10, 100, 90, 20, 25 };
 //Listan vi skall sortera

 qsort (values, 6, sizeof(int), compare);
 //Sortering med färdig funktion som har detta:
 //values = listan som skall sorteras
 //6 är helt enkelt antalet poster i listan
 //sizeof(int) räknar ut storleken i minnet för varje post, som råkar vara 
       //heltal. Hade det varit bokstäver i listan hade det stått sizeof(char).
 //compare är en färdig funktion som jämför två heltal.


 for (n=0; n<6; n++) //listans antal poster
	 cout << values[n] << ", "; //skriv ut värdet
 //Skriv ut de sorterade värdena
 return 0;
}

//Funktion

int compare (const void * a, const void * b)
{
 return ( *(int*)a - *(int*)b );
}