Shell Sort Algorithm in DSA Python - Execution Trace

Concept Flow - Shell Sort Algorithm

Start with array

↓

Choose initial gap = n/2

↓

For each gap

↓

Perform gapped insertion sort

↓

Reduce gap (gap = gap/2)

↓

Repeat until gap = 0

↓

Array sorted

Shell Sort starts with a big gap and sorts elements far apart, then reduces the gap and sorts again until gap is 0, resulting in a sorted array.

Execution Sample

DSA Python

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

This code sorts an array by comparing elements at a gap and reducing the gap until the array is sorted.

Execution Table

Step	Operation	Array State	Gap	Comparison	Swap?	Resulting Array State
1	Initialize	[23, 12, 1, 8, 34, 54, 2, 3]	4	N/A	N/A	[23, 12, 1, 8, 34, 54, 2, 3]
2	Compare arr[0] and arr[4]	[23, 12, 1, 8, 34, 54, 2, 3]	4	23 vs 34	No	[23, 12, 1, 8, 34, 54, 2, 3]
3	Compare arr[1] and arr[5]	[23, 12, 1, 8, 34, 54, 2, 3]	4	12 vs 54	No	[23, 12, 1, 8, 34, 54, 2, 3]
4	Compare arr[2] and arr[6]	[23, 12, 1, 8, 34, 54, 2, 3]	4	1 vs 2	No	[23, 12, 1, 8, 34, 54, 2, 3]
5	Compare arr[3] and arr[7]	[23, 12, 1, 8, 34, 54, 2, 3]	4	8 vs 3	Yes	[23, 12, 1, 3, 34, 54, 2, 8]
6	Reduce gap	[23, 12, 1, 3, 34, 54, 2, 8]	2	N/A	N/A	[23, 12, 1, 3, 34, 54, 2, 8]
7	Compare arr[2] and arr[0]	[23, 12, 1, 3, 34, 54, 2, 8]	2	1 vs 23	Yes	[1, 12, 23, 3, 34, 54, 2, 8]
8	Compare arr[3] and arr[1]	[1, 12, 23, 3, 34, 54, 2, 8]	2	3 vs 12	Yes	[1, 3, 23, 12, 34, 54, 2, 8]
9	Compare arr[4] and arr[2]	[1, 3, 23, 12, 34, 54, 2, 8]	2	34 vs 23	No	[1, 3, 23, 12, 34, 54, 2, 8]
10	Compare arr[5] and arr[3]	[1, 3, 23, 12, 34, 54, 2, 8]	2	54 vs 12	No	[1, 3, 23, 12, 34, 54, 2, 8]
11	Compare arr[6] and arr[4]	[1, 3, 23, 12, 34, 54, 2, 8]	2	2 vs 34	Yes	[1, 3, 23, 12, 2, 54, 34, 8]
12	Compare arr[7] and arr[5]	[1, 3, 23, 12, 2, 54, 34, 8]	2	8 vs 54	Yes	[1, 3, 23, 12, 2, 8, 34, 54]
13	Reduce gap	[1, 3, 23, 12, 2, 8, 34, 54]	1	N/A	N/A	[1, 3, 23, 12, 2, 8, 34, 54]
14	Compare arr[1] and arr[0]	[1, 3, 23, 12, 2, 8, 34, 54]	1	3 vs 1	No	[1, 3, 23, 12, 2, 8, 34, 54]
15	Compare arr[2] and arr[1]	[1, 3, 23, 12, 2, 8, 34, 54]	1	23 vs 3	No	[1, 3, 23, 12, 2, 8, 34, 54]
16	Compare arr[3] and arr[2]	[1, 3, 23, 12, 2, 8, 34, 54]	1	12 vs 23	Yes	[1, 3, 12, 23, 2, 8, 34, 54]
17	Compare arr[4] and arr[3]	[1, 3, 12, 23, 2, 8, 34, 54]	1	2 vs 23	Yes	[1, 3, 12, 2, 23, 8, 34, 54]
18	Compare arr[5] and arr[4]	[1, 3, 12, 2, 23, 8, 34, 54]	1	8 vs 23	Yes	[1, 3, 12, 2, 8, 23, 34, 54]
19	Compare arr[6] and arr[5]	[1, 3, 12, 2, 8, 23, 34, 54]	1	34 vs 23	No	[1, 3, 12, 2, 8, 23, 34, 54]
20	Compare arr[7] and arr[6]	[1, 3, 12, 2, 8, 23, 34, 54]	1	54 vs 34	No	[1, 3, 12, 2, 8, 23, 34, 54]
21	Reduce gap	[1, 3, 12, 2, 8, 23, 34, 54]	0	N/A	N/A	[1, 3, 12, 2, 8, 23, 34, 54]

💡 Gap reduced to 0, sorting complete

Variable Tracker

Variable	Start	After Step 5	After Step 12	After Step 20	Final
arr	[23, 12, 1, 8, 34, 54, 2, 3]	[23, 12, 1, 3, 34, 54, 2, 8]	[1, 3, 23, 12, 2, 8, 34, 54]	[1, 3, 12, 2, 8, 23, 34, 54]	[1, 3, 12, 2, 8, 23, 34, 54]
gap	4	4	2	1	0

Key Moments - 3 Insights

Why do we start with a large gap and reduce it instead of sorting with gap=1 from the start?

Starting with a large gap moves elements far apart closer to their correct positions quickly, reducing the total number of swaps needed later. This is shown in steps 1-5 where gap=4 moves some elements, making later smaller gap sorts faster.

Why do we compare elements at index i and i-gap instead of adjacent elements?

Shell Sort compares elements that are 'gap' apart to partially sort the array in groups. This is visible in the execution_table where comparisons like arr[0] vs arr[4] happen at gap=4, not adjacent elements.

What happens when gap becomes 1?

When gap is 1, Shell Sort performs a normal insertion sort on the nearly sorted array, which is efficient. Steps 13-20 show this final pass where adjacent elements are compared and swapped if needed.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 5?

A [23, 12, 1, 8, 34, 54, 2, 3]

B [23, 12, 1, 3, 34, 54, 2, 8]

C [1, 12, 23, 3, 34, 54, 2, 8]

D [1, 3, 12, 2, 8, 23, 34, 54]

💡 Hint

Check the 'Resulting Array State' column at step 5 in the execution_table.

At which step does the gap reduce from 4 to 2?

A Step 5

B Step 12

C Step 6

D Step 13

💡 Hint

Look at the 'Gap' column in the execution_table and find where it changes from 4 to 2.

If the initial gap was set to 1 instead of n//2, how would the sorting behave?

A It would perform a normal insertion sort from the start.

B It would skip sorting entirely.

C It would sort only half the array.

D It would cause an error.

💡 Hint

Refer to the concept_flow and execution_table steps where gap=1 corresponds to insertion sort.

Concept Snapshot

Shell Sort Algorithm:
- Start with gap = n//2
- Perform gapped insertion sort
- Reduce gap by half each time
- Repeat until gap = 0
- Efficient for medium-sized arrays
- Combines insertion sort and gap reduction

Full Transcript

Shell Sort is a sorting method that starts by sorting elements far apart using a gap, then reduces the gap gradually until it sorts adjacent elements. The process begins with a gap equal to half the array size. For each gap, the algorithm compares and swaps elements that are gap positions apart, partially sorting the array. Then the gap is reduced by half, and the process repeats. When the gap reaches 1, it performs a normal insertion sort on the nearly sorted array, which is efficient. The execution table shows each comparison and swap step, tracking the array state and gap changes. This method improves over simple insertion sort by moving elements faster towards their correct positions early on.

Practice

1. What is the main idea behind the Shell Sort algorithm?

easy

A. It uses a pivot element to partition the list into smaller parts.

B. It sorts elements by repeatedly swapping adjacent elements until sorted.

C. It divides the list into two halves and sorts each half separately.

D. It sorts elements by comparing and swapping distant elements first, then reducing the gap.

Solution

1. Step 1: Understand Shell Sort's approach

   Shell Sort starts by sorting pairs of elements far apart from each other, then progressively reduces the gap between elements to be compared.

2. Step 2: Compare with other sorting methods

   Unlike bubble sort (adjacent swaps) or quicksort (pivot partition), Shell Sort uses a gap sequence to improve efficiency.

3. Final Answer:

   It sorts elements by comparing and swapping distant elements first, then reducing the gap. -> Option D

4. Quick Check:

   Shell Sort = Distant element comparisons first [OK]

Hint: Remember: Shell Sort reduces gap size step-by-step [OK]

Common Mistakes:

• Confusing Shell Sort with bubble sort
• Thinking it always compares adjacent elements first
• Mixing it up with quicksort's pivot method

2. Which of the following is the correct way to start the gap sequence in Shell Sort for a list of length n?

easy

A. gap = n

B. gap = 1

C. gap = n // 2

D. gap = n * 2

Solution

1. Step 1: Identify the initial gap value

   Shell Sort typically starts with a gap of half the list length, i.e., gap = n // 2.

2. Step 2: Understand gap reduction

   The gap is then reduced by half each iteration until it reaches 0.

3. Final Answer:

   gap = n // 2 -> Option C

4. Quick Check:

   Initial gap = n // 2 [OK]

Hint: Start gap at half the list length [OK]

Common Mistakes:

• Starting gap at 1 (too small)
• Starting gap equal to n (too large)
• Multiplying gap by 2 instead of dividing

3. What will be the output of the following Python code using Shell Sort?

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

arr = [9, 8, 3, 7, 5]
shell_sort(arr)
print(arr)

medium

A. [3, 7, 5, 8, 9]

B. [3, 5, 7, 8, 9]

C. [9, 8, 7, 5, 3]

D. [5, 3, 7, 8, 9]

Solution

1. Step 1: Trace the sorting process

   The code implements Shell Sort correctly. It sorts the list [9, 8, 3, 7, 5] into ascending order.

2. Step 2: Verify final sorted list

   After sorting, the list becomes [3, 5, 7, 8, 9].

3. Final Answer:

   [3, 5, 7, 8, 9] -> Option B

4. Quick Check:

   Sorted list = [3, 5, 7, 8, 9] [OK]

Hint: Shell Sort outputs sorted list in ascending order [OK]

Common Mistakes:

• Assuming original list remains unchanged
• Confusing descending with ascending order
• Misreading the gap reduction loop

4. Identify the error in this Shell Sort implementation:

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j + gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

medium

A. The inner while condition uses arr[j + gap] instead of arr[j - gap].

B. The gap is not reduced correctly in the loop.

C. The for loop range is incorrect; it should start from 0.

D. The temporary variable 'temp' is not assigned properly.

Solution

1. Step 1: Check the inner while loop condition

   The condition uses arr[j + gap] which is incorrect; it should compare arr[j - gap] to temp.

2. Step 2: Confirm correct element shifting

   Using arr[j + gap] can cause index errors or wrong comparisons; arr[j - gap] ensures proper backward comparison.

3. Final Answer:

   The inner while condition uses arr[j + gap] instead of arr[j - gap]. -> Option A

4. Quick Check:

   Compare with arr[j - gap], not arr[j + gap] [OK]

Hint: Check index directions carefully in inner loops [OK]

Common Mistakes:

• Using wrong index direction in comparisons
• Not reducing gap properly
• Incorrect loop start index

5. Given the list [23, 12, 1, 8, 34, 54, 2, 3], what will be the state of the list after the first gap iteration (gap = 4) in Shell Sort?

hard

A. [23, 12, 1, 3, 34, 54, 2, 8]

B. [3, 12, 1, 8, 2, 54, 23, 34]

C. [2, 12, 1, 8, 23, 54, 3, 34]

D. [23, 12, 1, 8, 34, 54, 2, 3]

Solution

1. Step 1: Identify elements compared with gap 4

   Elements compared are pairs 0 & 4, 1 & 5, 2 & 6, 3 & 7.

2. Step 2: Perform swaps if needed

   Compare and swap if left element > right element:
   Index 0 & 4: 23 > 34? No swap.
   Index 1 & 5: 12 > 54? No swap.
   Index 2 & 6: 1 > 2? No swap.
   Index 3 & 7: 8 > 3? Yes, swap 8 and 3.

3. Step 3: Result after first gap iteration

   The list becomes [23, 12, 1, 3, 34, 54, 2, 8].

4. Final Answer:

   [23, 12, 1, 3, 34, 54, 2, 8] -> Option A

5. Quick Check:

   After gap=4: [23, 12, 1, 3, 34, 54, 2, 8] [OK]

Hint: Check pairs separated by gap, swap if left > right [OK]

Common Mistakes:

• Not swapping elements correctly at gap distance
• Confusing final list after full sort with partial iteration
• Ignoring insertion steps within gap