Nederlandse leereditie

Bubble sort in C: buren verwisselen

Sorteer door buren te vergelijken en stop zodra er geen wissels zijn.

Vergelijk per ronde aangrenzende elementen en wissel ze zo nodig. Het grootste resterende element komt achteraan, zodat de volgende ronde korter kan zijn.

Met een vlag kun je stoppen als er geen wissels waren. Daarmee kost gesorteerde invoer O(N), maar algemene en slechtste gevallen blijven O(N²). De hulpruimte is O(1).

Gebruik arr[j + 1] niet wanneer j al de laatste index is. Test duplicaten en omgekeerde volgorde. Alleen wisselen als links strikt groter is behoudt de volgorde van gelijke waarden.

Broncode

#include <stdio.h>
#include <stdbool.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // Array is already sorted
    }
}

void print_array(const int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void) {
    int data[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(data) / sizeof(data[0]);

    printf("Original array: ");
    print_array(data, n);

    bubble_sort(data, n);

    printf("Sorted array:   ");
    print_array(data, n);
    return 0;
}

Openen in de compiler

Verwacht resultaat

Original array: 64 34 25 12 22 11 90 
Sorted array:   11 12 22 25 34 64 90

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.