Sorteringsalgoritmen Bubble Sort

• 2025-05-21
• Martin Haagen

Bubble Sort är en av de mest välkända sorteringsalgoritmerna. Den har blivit populär eftersom den är enkel att förstå och dessutom en utmärkt introduktion till analys av algoritmer och datastrukturer. Algoritmen beskrevs för första gången av Edward Harry Friend i den vetenskapliga artikeln “Sorting on Electronic Computer Systems” från 1956.

Algoritmen arbetar på en array där den jämför två intilliggande element. Om det första elementet innehåller ett värde som är större än det andra, byter de plats. Sedan går algoritmen vidare och jämför det andra och tredje elementet. På detta sätt skjuts de större värdena successivt mot slutet av arrayen. När hela arrayen har genomgåtts kommer det största elementet att finnas längst till höger. Därefter börjar algoritmen om från början. Listan genomlöps lika många gånger som det finns element för att garantera att alla har hamnat på rätt plats.

Algoritmen har en tidskomplexitet på O(n²), vilket innebär att tiden det tar att sortera växer kvadratiskt i förhållande till mängden data. Med andra ord: om man dubblar datamängden fyrdubblas arbetet som krävs för att sortera den. Därför blir algoritmen snabbt oanvändbar för stora datamängder. Minneskomplexiteten är O(1) eftersom algoritmen sorterar elementen på plats utan att använda extra minne.

Det finns vissa sätt att optimera algoritmen. Man kan till exempel successivt minska hur långt in i arrayen som sorteringen sker, eftersom man vet att elementen i slutet redan är på rätt plats. Detta påverkar dock inte algoritmens Big-O-klassificering.

Exempel implementation i C++

Att implementera Bubble Sort i C++ är en bra övning – både för att förstå algoritmens funktion och för att träna sina C++-kunskaper. Nedan finns ett exempel på en implementation i C++. Datatypen vector liknar en vanlig array, men har inbyggt stöd för att ändra storlek.

 1#include <vector>
 2
 3void bubbleSort(std::vector<int>& arr) {
 4    int n = arr.size();
 5    for (int i = 0; i < n - 1; ++i) {
 6        for (int j = 0; j < n - i - 1; ++j) {
 7            if (arr[j] > arr[j + 1]) {
 8                std::swap(arr[j], arr[j + 1]);
 9            }
10        }
11    }
12}

Exempel implementation i Java

Bubble Sort är inte beroende av ett specifikt programmeringsspråk och går därför utmärkt att implementera även i Java. Tänk på att List är ett interface i Java. För att sorteringen ska vara effektiv är ArrayList den bästa datatypen att använda med denna sorteringsalgoritm.

 1import java.util.List;
 2import java.util.Collections;
 3
 4public class BubbleSorter {
 5    public static void bubbleSort(List<Integer> arr) {
 6        int n = arr.size();
 7        for (int i = 0; i < n - 1; ++i) {
 8            for (int j = 0; j < n - i - 1; ++j) {
 9                if (arr.get(j) > arr.get(j + 1)) {
10                    Collections.swap(arr, j, j + 1);
11                }
12            }
13        }
14    }
15}