Bubbelsort, en sorteringsalgoritm

Bubblesort

Sorteringsalgoritmer är väldigt vanliga när man hanterar data.  Det finns många olika sätt att sortera data på. Här ska vi använda en enkel algoritm som heter Bubblesort. Vissa  sorteringsalgoritmer är effektiva medan andra är mindre effektiva. Syftet med en sorteringsalgoritm är att lösa ett speciellt problem, nämligen: att sortera en godtycklig mängd data med avseende på någon relativ jämförelse mellan elementen. Bubblesort ska här användas för att sortera tal i en array så att de står i nummerordning.

Bubble Sort fungerar genom att jämföra två intilliggande element. Om elementet till höger är mindre det vänstra så byter vi plats på dem. Sedan fortsätter vi jämföra intilliggande element genom att gå vidare åt det håll vi jämför i. Här kommer vi att börja framifrån i arrayen (index 0). Vi ska också visa staplar på canvasen som representerar de tal som finns i arrayen. När musen klickas på ska två tal jämföras. Om de står på rätt plats ska de bli gula. Om de behöver byta plats ska de visa röd färg och sen skifta plats.

Först skapas en array med namnet arr och i den lägger vi in ett antal siffror. En variabel med namnet i får värdet 0. En variabel med namnet len för att hålla reda på längden på arrayen (den skapas  för att kunna använda den initiala längden av arrayen  i funktionen mousePressed() ). En variabel med namnet count som ska hålla reda på hur många jämförelser som görs innan arrayen är sorterad. Den sätts till värdet 0.
I setup() skapas en canvas som är 400 * 400 pixlar. funktionen frameRate() används för att specificera hur många gånger per sekund bildskärmen ska uppdateras. Normalt uppdateras skärmen 60 gånger per sekund (om den är på 60 Hertz). Här är frameRate satt till 1 för att vi ska hinna se vad som sker på canvasen.

var arr = [2, 8, 6, 9, 4, 5, 3, 1];
var i = 0;
var len = arr.length;
var count = 0;

function setup() {
createCanvas(400, 400);
frameRate(1);
}

I draw() ska vi rita ut staplar som visar innehållet i arrayen. Bakgrunden sätts till en grå färg. En for-loop loopar igenom hela arrayen. Färg sätts till grön med Alpha på 200 (en viss genomskinlighet). En rektangel ritas ut. Hörnet där rektangeln börjar ritas är i x-led k * 20 + 60 så för första rektangeln (när k =0) blir placeringen x = 60. För andra rektangeln ( k = 1) blir placeringen x = 80 och så vidare. Placering i y -led är 300. Rektangeln ska vara 20 bred och höjden ska vara arr[k] * -20.  arr[k] betyder det värde som står på index k (börjar med 0 och ökar med ett genom hela arrayen. Värdet multipliceras med -20 för att rektangeln ska ritas uppåt.

 Ändra i koden så att det inte står -20 utan 20 för att se hur rektangeln ritas ut då.

En variabel med namnet txt skapas och ges värdet av det tal som arrayen innehåller för varje index. Storlek på text är 16 px. Färgen är svart. Placering av text text(txt, (k * 20) + 67, 295);
textAlign()  anger hur texten ska justeras. Läs mer om detta på P5.js sida under reference

Sist skrivs texten för count ut på mitten i x-led och i y-led 350 pixlar ner.

function draw() {
  background(220);
  for (var k = 0; k < arr.length; k++) {
    fill(0, 255, 0, 200);
    rect(k * 20 + 60, 300, 20, arr[k] * -20);
    var txt = arr[k];
    textSize(16);
    fill(0);
    text(txt, (k * 20) + 67, 295);
    textAlign(CENTER);
    text('count = ' + count, width / 2, 350);
  }
}


Nu ska en funktion skrivas som hanterar vad som sker när musen klickas på. I p5.js finns en funktion mousePressed() som ska användas.

Först ökas count med ett varje gång musen klickas. Därefter kontrolleras om värdet på talet i arrayens index ( i ) är större än värdet på talet i nästa index if (arr[i] > arr[i + 1]) {. Om värdet är större, skapa en variabel som heter temp och sätt den till värdet av talet i array [ i ] . Gör talen röda och byt plats på de två talen
arr[i] = arr[i + 1];
arr[i + 1] = temp;
fill(255, 0, 0);
rect((i) * 20 + 60, 300, 20, arr[i] * -20);

rect((i + 1) * 20 + 60, 300, 20, arr[i + 1] * -20);

Om värdet av det första talet INTE är större Gör dem gula och låt dem stå kvar i sina positioner
else {
fill(255, 255, 0);
rect((i) * 20 + 60, 300, 20, arr[i] * -20);
rect((i + 1) * 20 + 60, 300, 20, arr[i + 1] * -20);
}
Öka sen i med ett och gå vidare i arrayen
i = i + 1;

När programmet nått slutet på arrayen ska loopen börja om på index 0 och längden på arrayen ska minskas med ett. Efter första genomgången av arrayen har det högsta talet hamnat sist vilket gör att det inte behöver vara med i sorteringen längre. Det är därför arrayens längd minskas med ett varje gång hela längden av arrayen är kontrollerad.

function mousePressed() {
  count++;
  if (arr[i] > arr[i + 1]) {
    var temp = arr[i];
    arr[i] = arr[i + 1];
    arr[i + 1] = temp;
    fill(255, 0, 0);
    rect((i) * 20 + 60, 300, 20, arr[i] * -20);
    rect((i + 1) * 20 + 60, 300, 20, arr[i + 1] * -20);
  } else {
    fill(255, 255, 0);
    rect((i) * 20 + 60, 300, 20, arr[i] * -20);
    rect((i + 1) * 20 + 60, 300, 20, arr[i + 1] * -20);
  }
  i = i + 1;
  if (i == len - 1) {
    i = 0;
    len--;
  }
//console.log(len);
}

Hur många klick det tar att sortera en array beror ju på hur den ser ut från början.
 Ändra värden i arrayen och se att den fungerar för olika värden. Om du använder tvåsiffriga tal kanske textens placering och storlek behöver ändras också.