Algorithm - Quick sort (C, qsort)

Docs › Algorithm
, 
1
void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *);
  • stdlib.h
  • O(nlogn) (최악: O(n^2))

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    if (*(int*)a > *(int*)b) return 1;
    else if (*(int*)a < *(int*)b) return -1;
    return 0;
}

int n;

int main() {
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    qsort(arr, n, sizeof(int), compare);
    
    for (int j = 0; j < n; j++) {
        printf("%d ", arr[j]);
    }
}
  • input
1
2
10
9 2 6 5 1 7 3 4 8 1
  • output
1
1 1 2 3 4 5 6 7 8 9