Shell Sort Algorithm in DSA Python - Build from Scratch

Shell Sort Algorithm

📖 Scenario: You are working as a software developer for a company that needs to sort lists of numbers efficiently. Shell Sort is a good choice because it improves on simple sorting methods by comparing elements far apart first.

🎯 Goal: Build a Python program that sorts a list of numbers using the Shell Sort algorithm step-by-step.

📋 What You'll Learn

Create a list called numbers with the exact values [23, 12, 1, 8, 34, 54, 2, 3].

Create a variable called gap and set it to half the length of numbers using integer division.

Implement the Shell Sort logic using a while loop that runs while gap > 0 and a nested for loop to compare and swap elements.

Print the sorted numbers list after the sorting is complete.

💡 Why This Matters

🌍 Real World

Shell Sort is used in situations where a simple but efficient sorting method is needed for medium-sized lists, such as sorting records in small databases or organizing data in embedded systems.

💼 Career

Understanding Shell Sort helps in grasping how sorting algorithms improve performance by reducing comparisons and swaps, a key skill for software developers working with data processing and optimization.

1

Create the list of numbers

Create a list called numbers with these exact values: [23, 12, 1, 8, 34, 54, 2, 3].

DSA Python

# Create the list called numbers with the given values
# Your code here

Hint

Use square brackets [] to create a list and separate numbers with commas.

2

Set the initial gap value

Create a variable called gap and set it to half the length of numbers using integer division //.

DSA Python

numbers = [23, 12, 1, 8, 34, 54, 2, 3]
# Set gap to half the length of numbers using integer division
# Your code here

Hint

Use len(numbers) to get the list length and // 2 to divide by 2 without decimals.

3

Implement the Shell Sort logic

Write a while loop that runs while gap > 0. Inside it, use a for loop with variable i from gap to len(numbers). Inside the for loop, set temp = numbers[i] and j = i. Then use a while loop that runs while j >= gap and numbers[j - gap] > temp. Inside this inner loop, set numbers[j] = numbers[j - gap] and decrease j by gap. After the inner loop, set numbers[j] = temp. After the for loop, update gap = gap // 2.

DSA Python

numbers = [23, 12, 1, 8, 34, 54, 2, 3]
gap = len(numbers) // 2
# Implement the Shell Sort loops and logic below
# Your code here

Hint

Follow the Shell Sort steps carefully: reduce gap, compare and shift elements, then insert.

4

Print the sorted list

Write a print statement to display the sorted numbers list.

DSA Python

numbers = [23, 12, 1, 8, 34, 54, 2, 3]
gap = len(numbers) // 2

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

# Print the sorted numbers list
# Your code here

Hint

Use print(numbers) to show the sorted list.

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