Shell Sort Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Shell Sort with gap sequence

What is the output of the following Shell Sort code on the list [23, 12, 1, 8, 34, 54, 2, 3]?

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

arr = [23, 12, 1, 8, 34, 54, 2, 3]
shell_sort(arr)
print(arr)

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

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

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

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

💡 Hint

Trace the sorting steps with gap reducing by half each time.

Shell Sort sorts elements by comparing elements at a certain gap and reducing the gap until it becomes 1, which is a normal insertion sort. The final sorted list is ascending.

🧠 Conceptual

intermediate

Understanding gap sequence in Shell Sort

Which of the following statements about the gap sequence in Shell Sort is TRUE?

A The gap sequence must always be a power of two.

B The gap sequence is irrelevant; Shell Sort always performs the same.

C The gap sequence must start at 1 and increase to the length of the list.

D The gap sequence determines the efficiency and can be any sequence that ends with 1.

💡 Hint

Think about how the gap affects sorting passes.

The gap sequence affects how quickly the list becomes sorted. It must end with 1 to ensure the list is fully sorted. Different sequences affect performance.

🔧 Debug

advanced

Identify the error in this Shell Sort implementation

What error will this Shell Sort code produce when run?

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

arr = [5, 3, 8, 6, 2]
shell_sort(arr)
print(arr)

A The list will be sorted in ascending order.

B The list will be sorted in descending order.

C The code will raise an IndexError.

D The code will raise a TypeError.

💡 Hint

Check the comparison operator in the inner while loop.

The comparison uses '<' instead of '>' causing the list to be sorted in descending order.

📝 Syntax

advanced

Syntax error in Shell Sort code

Which option contains the correct syntax to fix the error in this Shell Sort snippet? Code snippet: 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

A Replace 'arr[j] = arr[j - gap]' with 'arr[j - gap] = arr[j]'.

B Change 'while' to 'if' in the inner loop.

C Add a colon at the end of the for loop line: for i in range(gap, n):

D Remove the line 'j = i' inside the for loop.

💡 Hint

Check Python syntax for loops.

Python requires a colon at the end of for loop declarations.

🚀 Application

expert

Shell Sort performance on nearly sorted list

Given a nearly sorted list of 1000 elements, which statement about Shell Sort's performance is MOST accurate?

A Shell Sort will perform close to O(n log n) time due to reduced swaps.

B Shell Sort will perform worse than bubble sort on nearly sorted data.

C Shell Sort always performs in O(n^2) time regardless of input.

D Shell Sort is not suitable for nearly sorted lists and will fail to sort.

💡 Hint

Consider how gap insertion sort benefits nearly sorted data.

Shell Sort improves over simple insertion sort by reducing swaps early, making it efficient on nearly sorted data.

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