Sorting

Put things in order

Bubble sort: walk the array swapping neighbours that are out of order; after each pass the largest remaining value has bubbled to the end. Simple, but about n² steps.

For real work, qsort from <stdlib.h> sorts in about n log n steps. You give it a compare function that returns negative, zero or positive, like strcmp.

Exercise: Bubble sort

Read n (1 to 1000) and n numbers. Sort them in increasing order with bubble sort (write it yourself) and print them separated by spaces.

Bubble sort vs qsort

Solution A

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    static int a[200000];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int pass = 0; pass < n - 1; pass++)
        for (int i = 0; i + 1 < n - pass; i++)
            if (a[i] > a[i + 1]) { int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; }
    printf("%d %d\n", a[0], a[n - 1]);
    return 0;
}

Solution B

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *x, const void *y) {
    int p = *(const int *) x, q = *(const int *) y;
    return (p > q) - (p < q);
}

int main() {
    int n;
    scanf("%d", &n);
    static int a[200000];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    qsort(a, n, sizeof(int), cmp);
    printf("%d %d\n", a[0], a[n - 1]);
    return 0;
}

Input: 200,000 numbers in reverse order

Both print the smallest and largest number. Which finishes within 2 seconds?

• Only A, bubble sort
• Only B, qsort
• Both