advent2021

Advent of Code 2021 Solutions
git clone git://bsandro.tech/advent2021
Log | Files | Refs

quicksort.h (693B)

      1 #pragma once
      2 
      3 /* ******************* quicksort ***********************/
      4 
      5 static void qs_swap(long long *a, long long *b) {
      6 	long long tmp = *a;
      7 	*a = *b;
      8 	*b = tmp;
      9 }
     10 
     11 static long long qs_partition(long long *numbers, long long low, long long high) {
     12 	long long pivot = numbers[high];
     13 	long long i = low - 1;
     14 	for (long long j = low; j <= high - 1; ++j) {
     15 		if (numbers[j] < pivot) {
     16 			i++;
     17 			qs_swap(&numbers[i], &numbers[j]);
     18 		}
     19 	}
     20 	qs_swap(&numbers[i+1], &numbers[high]);
     21 	return i + 1;
     22 }
     23 
     24 static void qs(long long *numbers, long long low, long long high) {
     25 	if (low < high) {
     26 		long long p = qs_partition(numbers, low, high);
     27 		qs(numbers, low, p - 1);
     28 		qs(numbers, p + 1, high);
     29 	}
     30 }