Revisions to My BRESort adaptive sorting engine in C

no `i` before declaration

Source Link

edited Oct 11 at 4:58

7.7k
3
21
56

    min_val = arr[i];arr[0];
    max_val = arr[i];arr[0];

    // Single-pass analysis: extract data patterns
    for (int i = 1; i < n; i++) {
        // 1. Measure value range
        if (arr[i] < min_val) min_val = arr[i];
        if (arr[i] > max_val) max_val = arr[i];

        // 2. Measure sortedness and patterns
        if (arr[i] >= arr[i-1]) {
            consecutive_sorted++;
            if (consecutive_sorted > max_consecutive) {
                max_consecutive = consecutive_sorted;
            }
        } else {
            out_of_order++;
            consecutive_sorted = 0;
        }
    }

    min_val = arr[i];
    max_val = arr[i];

    // Single-pass analysis: extract data patterns
    for (int i = 1; i < n; i++) {
        // 1. Measure value range
        if (arr[i] < min_val) min_val = arr[i];
        if (arr[i] > max_val) max_val = arr[i];

        // 2. Measure sortedness and patterns
        if (arr[i] >= arr[i-1]) {
            consecutive_sorted++;
            if (consecutive_sorted > max_consecutive) {
                max_consecutive = consecutive_sorted;
            }
        } else {
            out_of_order++;
            consecutive_sorted = 0;
        }
    }

    min_val = arr[0];
    max_val = arr[0];

    // Single-pass analysis: extract data patterns
    for (int i = 1; i < n; i++) {
        // 1. Measure value range
        if (arr[i] < min_val) min_val = arr[i];
        if (arr[i] > max_val) max_val = arr[i];

        // 2. Measure sortedness and patterns
        if (arr[i] >= arr[i-1]) {
            consecutive_sorted++;
            if (consecutive_sorted > max_consecutive) {
                max_consecutive = consecutive_sorted;
            }
        } else {
            out_of_order++;
            consecutive_sorted = 0;
        }
    }

added 1495 characters in body

Source Link

edited Oct 10 at 23:59

Chris

4.6k
1
7
36

You have this loop:

    // Single-pass analysis: extract data patterns
    for (int i = 0; i < n; i++) {
        // 1. Measure value range
        if (arr[i] < min_val) min_val = arr[i];
        if (arr[i] > max_val) max_val = arr[i];

        // 2. Measure sortedness and patterns
        if (i > 0) {
            if (arr[i] >= arr[i-1]) {
                consecutive_sorted++;
                if (consecutive_sorted > max_consecutive) {
                    max_consecutive = consecutive_sorted;
                }
            } else {
                out_of_order++;
                consecutive_sorted = 0;
            }
        }
    }

You have a condition which is only ever false on the very first iteration. You may wish to unroll this so that this branch is absent in the loop.

    min_val = arr[i];
    max_val = arr[i];

    // Single-pass analysis: extract data patterns
    for (int i = 1; i < n; i++) {
        // 1. Measure value range
        if (arr[i] < min_val) min_val = arr[i];
        if (arr[i] > max_val) max_val = arr[i];

        // 2. Measure sortedness and patterns
        if (arr[i] >= arr[i-1]) {
            consecutive_sorted++;
            if (consecutive_sorted > max_consecutive) {
                max_consecutive = consecutive_sorted;
            }
        } else {
            out_of_order++;
            consecutive_sorted = 0;
        }
    }

You have this loop:

    // Single-pass analysis: extract data patterns
    for (int i = 0; i < n; i++) {
        // 1. Measure value range
        if (arr[i] < min_val) min_val = arr[i];
        if (arr[i] > max_val) max_val = arr[i];

        // 2. Measure sortedness and patterns
        if (i > 0) {
            if (arr[i] >= arr[i-1]) {
                consecutive_sorted++;
                if (consecutive_sorted > max_consecutive) {
                    max_consecutive = consecutive_sorted;
                }
            } else {
                out_of_order++;
                consecutive_sorted = 0;
            }
        }
    }

You have a condition which is only ever false on the very first iteration. You may wish to unroll this so that this branch is absent in the loop.

    min_val = arr[i];
    max_val = arr[i];

    // Single-pass analysis: extract data patterns
    for (int i = 1; i < n; i++) {
        // 1. Measure value range
        if (arr[i] < min_val) min_val = arr[i];
        if (arr[i] > max_val) max_val = arr[i];

        // 2. Measure sortedness and patterns
        if (arr[i] >= arr[i-1]) {
            consecutive_sorted++;
            if (consecutive_sorted > max_consecutive) {
                max_consecutive = consecutive_sorted;
            }
        } else {
            out_of_order++;
            consecutive_sorted = 0;
        }
    }

Source Link

answered Oct 10 at 23:42

Chris

4.6k
1
7
36

Without seeing all of the code, based only on what I can see, I'm not a fan of the 0, 1, and 2 being magic numbers to indicate which sort to use. This should almost certainly be an enum.

enum SortStrategy {
    COUNTING_SORT,
    INSERTION_SORT,
    HYBRID_SORT
};

Your switch also could be refactored to avoid repetition by letting the counting sort case fall through to the default case. By using the enum with meaningful names, the comments become extraneous.

    switch (strategy) { 
    case INSERTION_SORT: 
        bres_insertion_sort(arr, n); 
        break;   

    case HYBRID_SORT: 
        bres_hybrid_sort(arr, n); 
        break;   
 
    case COUNTING_SORT:
    default: 
        bres_counting_sort(arr, n); 
        break;
    }

Other magic numbers to eliminate would be the thresholds for invoking each sorting method.

Stack Exchange Network

Return to Answer