C++ Nybörjarguide forts

Tillbaka till artikelarkivet

Filer

Verktyg

Kommentarer (35)
Utskriftsvänligt format

Betyg

markedunmaked 5.7

Välkommen till fortsättningskursen i C++, om ni är här så har ni troligtvis redan läst artiklen C++ Nybörjarguide av Independence. Här kommer ni få lära er om:

Structurer & fstream
Vectorer & Listor
Stackar & Köer
Sök & Sorterings algoritmer
m.m.

Navigation:

< Föregående del || Nästa del >

Text - 4 Sök & Sortering algoritmer

Det är vädigt ofta man behöver sortera en array eller söka igenom den, kanske det har hållts en tävling och man matar in alla värdena huller om buller som sedan ska sorteras för att visa vem som vinner. Det finns många olika sätt att göra det på, dock är vissa sätt mer effektiva än andra. Här kommer de vanligaste och mest grundläggande sätten att sortera och söka.

Sortering

Jag kommer bara gå igenom den sorteringsalgoritm som är den mest grundläggande av alla, bubblesort.

Bubblesort


Du har en array och du får genom att gå igenom varje tal och sen jämföra det talet mot alla andra i listan, om detta talet år mindre än eller större än beroende på hur du vill ha arrayyen sorterad. Ett exempel:

  1. void bubbel(int data[], int antal) //antal är lika med så många fält som data är
  2. {
  3.    for(int m=antal-1; m>0; m--){
  4.       for(int n=0; n < m; n++){
  5.          if(data[n] > data[n+1]){
  6.             int temp = data[n];
  7.             data[n] = data[n+1];
  8.             data[n+1] = temp;
  9.          }
  10.       }
  11.    }
  12. }


Den här koden sorterar en talföljd eller en sträng med minst först.

Insertionsort

I insertionsort tar man ett tal på en position och jämför det med talet på positionen innan. (man börjar på position 2 eller på en array [1]). Detta gör då att arrayen innan det tal man sorterar är redan sorterat så man ska helt enkelt stoppa in talet på den positionen och skuta talet på positionen och alla efterföljande tal en position.

  1. void insert(int data[], int antal) //antal är lika med så många fält som data är
  2. {
  3.    for(int m=1; m<antal; m++)
  4.    {
  5.       int n=m;
  6.       int key = data[m];
  7.       for(; n>0 && data[n-1] > key; n--)
  8.       {
  9.          data[n] = data[n-1];
  10.       }
  11.       data[n]=key;
  12.    }
  13. }


Det finns även andra sätt att sortera på, quicksort är oftast den som sägs vara bäst men ska helst användas på så osorterade arrayer som möjligt. Olika sorterings algoritmer är olika bra på olika storlekar på arrayen, till exempel har jag blivit lärd att använda insertion sort på arrayer på under 30 element men merge sort är bättre för fler Försök gärna lära er dom också.

Sökning

Nu kommer här en väldigt bra grej, jag tror att alla kan göra en vanlig sök algoritm nu, men om man har en sorterad lista så kommer här en grej som kommer göra erat program mycket snabbare (beroende på hur stora listor ni har):
  1. int binarsok(int data[], int antal, int tal) // tal är det tal du letar efter.
  2. {
  3.    int min=0, max=antal-1, pos=-1;
  4.  
  5.    while(min<=max && pos==-1){
  6.       int mitt=(min+max)2;
  7.       if(tal>data[mitt])
  8.          min=mitt+1;
  9.       else if(tal<data[mitt])
  10.          max=mitt-1;
  11.       else
  12.          pos=mitt;
  13.    return pos;
  14. }

Som ni kanske kan se så kollar koden först om talet du letar efter är i mitten, och om den är det så blir pos likamed positionen och pos returneras. Annars så går den till mitten av vad som är kvar på den halva som ligger närmast talet du letar efter och upprepar. Detta kan mer än halvera tiden det tar att söka men kräver att arrayen eller vektorn är sorterad.

Slut

Navigation:

< Föregående del || Nästa del >

Till toppen