Bubble Sort With Restricted Step Size

Sorting algorithms form the foundation of computer science education, and among the simplest to understand is bubble sort. Still, the standard implementation suffers from inefficiency when dealing with large datasets or elements that need to travel long distances across the array. A fascinating variation addresses this limitation through a concept known as bubble sort with restricted step size, which modifies how elements are compared and swapped during each pass through the data.

Understanding Standard Bubble Sort

Before exploring the restricted step size variant, it helps to review how traditional bubble sort operates. The algorithm repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Even so, this process continues until no swaps are needed, indicating the list is sorted. The name derives from how smaller elements gradually "bubble" to the top of the list while larger elements sink to the bottom.

The critical characteristic of standard bubble sort is its step size of one. Also, each comparison involves neighboring elements at positions i and i+1. While this simplicity makes the algorithm easy to implement and understand, it creates a significant performance bottleneck. An element at the end of the array must participate in n-1 swaps to reach the beginning, requiring multiple complete passes through the data.

The Concept of Restricted Step Size

Bubble sort with restricted step size introduces a controlled gap between compared elements. Practically speaking, instead of comparing only adjacent pairs, the algorithm compares elements separated by a specific distance k, where k represents the step size. The "restricted" aspect refers to imposing limits on how large this step can become or how it changes throughout the sorting process.

This modification allows elements to move across the array more quickly than in the standard version. An element can jump multiple positions forward or backward in a single swap operation, rather than inching along one position at a time. The restriction ensures the algorithm maintains some of bubble sort's simplicity while gaining performance improvements.

Algorithm Mechanics

The restricted step size bubble sort follows a structured approach:

1. Initialize the step size: Begin with a step value k, typically set to a fraction of the array length or a predetermined maximum limit.
2. Perform comparisons: Iterate through the array, comparing elements at positions i and i+k.
3. Execute swaps: If the elements are out of order, swap them immediately.
4. Reduce the step size: After completing a pass, decrease k according to a specific sequence or restriction rule.
5. Terminate: Stop when k reaches one and a complete pass finds no swaps necessary.

The restriction on step size usually manifests as an upper bound or a specific reduction sequence. As an example, the step size might never exceed half the array length, or it might decrease by a factor of two each iteration, similar to Shell sort's approach but using bubble sort's swapping mechanism Worth knowing..

Scientific Analysis of Performance

The time complexity of bubble sort with restricted step size depends heavily on the restriction parameters and the initial data distribution. In the best-case scenario, where the array is already sorted, the algorithm achieves O(n) complexity, identical to the optimized standard bubble sort.

That said, the average and worst-case complexities vary based on the step size restrictions:

• Loose restrictions (allowing larger step sizes): Approach O(n²) complexity but with smaller constant factors than standard bubble sort
• Strict restrictions (limiting step size growth): Maintain O(n²) worst-case but perform better on nearly sorted data
• Optimal restriction sequences: Can achieve O(n log n) or O(n^(3/2)) depending on the gap sequence chosen

The space complexity remains O(1) since the algorithm sorts in-place, requiring only a constant amount of additional memory for temporary swap variables.

Comparison with Related Algorithms

Understanding where bubble sort with restricted step size fits in the sorting landscape requires comparison with both its standard counterpart and similar algorithms:

Standard Bubble Sort: The restricted version moves elements faster across the array but introduces slightly more complex logic. For

small arrays or educational contexts, standard bubble sort remains easier to understand and implement. The restricted step-size version is most useful when simple logic is desired, but the extra cost of long-distance swaps is acceptable.

Shell Sort: This algorithm is closely related, since it also compares and swaps elements separated by a gap. The main difference is that Shell sort typically uses an insertion-style movement within each gap, while restricted step-size bubble sort uses repeated bubble-style swaps. So naturally, Shell sort is usually faster in practice It's one of those things that adds up..

Insertion Sort: Insertion sort performs well on nearly sorted data and is stable, meaning it preserves the relative order of equal elements. Restricted step-size bubble sort may move elements faster in early passes, but it generally loses the stability and low overhead that make insertion sort attractive for small or partially sorted arrays.

Cocktail Shaker Sort: Cocktail shaker sort improves bubble sort by scanning in both directions. It helps move large elements toward the end and small elements toward the beginning more quickly, but each movement is still local. A restricted step-size variant can move elements farther in a single swap, giving it an advantage on some disordered inputs.

Implementation Considerations

A basic implementation requires three main components:

1. A method for choosing the initial step size.
2. A rule for reducing the step size after each pass.
3. A final pass with step size one to guarantee the array is fully sorted.

A simple version might use repeated halving:

restrictedStepBubbleSort(array):
    n = length(array)
    step = n / 2

    while step > 0:
        swapped = false

        for i from 0 to n - step - 1:
            if array[i] > array[i + step]:
                swap array[i] and array[i + step]
                swapped = true

        step = step / 2

        if step == 1 and swapped == false:
            break

The exact gap reduction rule has a major effect on performance. Practically speaking, a simple halving sequence is easy to implement, but more sophisticated sequences may reduce the number of passes required. Examples include Shell-style gap sequences, Knuth gaps, or other empirically tested reductions Less friction, more output..

It sounds simple, but the gap is usually here.

Advantages and Limitations

The main advantage of restricted step-size bubble sort is that it preserves the intuitive swap-based structure of bubble sort while allowing elements to move more quickly toward their final positions. This can reduce the number of passes needed, especially when small elements are located near the end of the array or large elements are located near the beginning No workaround needed..

Even so, the algorithm also has limitations:

• It is generally not stable.
• Its performance depends heavily on the chosen step-size sequence.
• It is usually slower than more advanced algorithms such as quicksort, mergesort, heapsort, or well-implemented Shell sort.
• It may perform unnecessary long-distance swaps that do not contribute efficiently to final ordering.

Because of these limitations, restricted step-size bubble sort is rarely the best choice for production sorting tasks involving large datasets. Its value is mostly educational or practical in small, simple contexts where algorithmic transparency matters

When to Apply Restricted Step‑Size Bubble Sort

Although the algorithm rarely competes with optimal O(n log n) methods on large inputs, there are niche scenarios where its simplicity and predictable behavior become assets:

• Educational demonstrations – The swap‑centric logic makes it an excellent vehicle for teaching concepts such as pass‑based iteration, early‑exit detection, and the impact of gap sequences.
• Embedded or safety‑critical systems – When code size and deterministic execution are critical, a compact implementation can be preferable to a more complex library routine, provided the dataset is known to be small (e.g., < 100 elements).
• Hybrid sorting pipelines – Some libraries use a “small‑array fallback” strategy. After a divide‑and‑conquer algorithm (quicksort, introsort) has reduced sub‑problems to a manageable size, a restricted step‑size bubble sort can polish the remaining slices with negligible overhead.
• Partially ordered streams – If incoming data is already roughly sorted and the step‑size sequence is tuned to the expected disorder, the algorithm can finish in far fewer passes than a classic bubble sort while avoiding the recursion stack of quicksort.

Tuning the Gap Sequence

The choice of step‑size reduction directly influences both runtime and the number of swaps. Common strategies include:

Empirical testing on typical hardware shows that Sedgewick’s sequence often yields the smallest total number of comparisons for random inputs, while Knuth’s provides a good balance between simplicity and performance for partially sorted data. The optimal choice therefore depends on the expected distribution of the input and any constraints on code size Nothing fancy..

Optimizations Worth Considering

1. Early termination with a “sorted flag” – The snippet already includes a swapped flag; extending it to also track whether any swap occurred with the current step size can cut the final pass short.
2. Bidirectional passes – Combining a forward restricted‑step pass with a backward pass (akin to cocktail shaker) can improve the movement of outliers, especially when the gap shrinks slowly.
3. Adaptive step reduction – Instead of a fixed divisor, dynamically adjust the reduction factor based on the number of swaps observed in the previous pass. Fewer swaps suggest the array is nearing order, allowing the step to be reduced more aggressively.
4. Cache‑friendly access patterns – By processing gaps that are powers of two, memory accesses tend to align with cache line boundaries, reducing miss rates on modern CPUs.
5. Parallel gap processing – For very large arrays, independent gap phases can be distributed across threads, though the overall complexity remains dominated by the O(n²) nature of the algorithm.

Practical Example: Python Implementation

Below is a compact, Python‑centric implementation that incorporates several of the refinements described above. It uses Sedgewick’s gap sequence and a bidirectional sweep to illustrate how the algorithm can be made more efficient while retaining its transparent swap‑based logic Practical, not theoretical..

def restricted_step_bubble_sort(arr):
    """Sort *arr* in‑place using a restricted step‑size bubble sort with
    Sedgewick gaps and bidirectional passes."""
    n = len(arr)

    # Sedgewick gap sequence (pre‑computed up to a reasonable size)
    gaps = [1, 5, 19, 41, 109, 209, 505, 909, 2089, 3937, 8929]
    gaps = [g for g in gaps if g < n]

    for step in reversed(gaps):          # start with the largest gap
        swapped = True
        while swapped:
            swapped = False
            # Forward pass
            for i in range(n - step):
                if arr[i] > arr[i +