qsort_partition()

static size_t fl::qsort_partition ( char * base, size_t nmemb, size_t size, qsort_compare_fn compar )

static

Definition at line 376 of file cstdlib.cpp.hpp.

                                                                                              {
    // Use median-of-three for pivot selection
    size_t mid = nmemb / 2;
    size_t last = nmemb - 1;
 
    char* first_elem = base;
    char* mid_elem = base + mid * size;
    char* last_elem = base + last * size;
 
    // Sort first, middle, last to find median
    if (compar(mid_elem, first_elem) < 0) {
        detail::qsort_swap(first_elem, mid_elem, size);
    }
    if (compar(last_elem, first_elem) < 0) {
        detail::qsort_swap(first_elem, last_elem, size);
    }
    if (compar(last_elem, mid_elem) < 0) {
        detail::qsort_swap(mid_elem, last_elem, size);
    }
 
    // Now mid_elem contains the median, swap it to end-1 position
    detail::qsort_swap(mid_elem, base + (last - 1) * size, size);
    char* pivot = base + (last - 1) * size;
 
    // Partition
    size_t i = 0;
    for (size_t j = 0; j < last - 1; ++j) {
        if (compar(base + j * size, pivot) < 0) {
            if (i != j) {
                detail::qsort_swap(base + i * size, base + j * size, size);
            }
            ++i;
        }
    }
 
    // Move pivot to its final position
    detail::qsort_swap(base + i * size, pivot, size);
    return i;
}

References fl::detail::qsort_swap().

Referenced by fl::detail::qsort_impl().

Here is the call graph for this function:

Here is the caller graph for this function: