Shell Sort Algorithm in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Shell Sort Algorithm?

Shell Sort improves insertion sort by comparing elements far apart and reducing the gap over time, making the list more sorted before a final insertion sort pass.

intermediate

How does Shell Sort choose the gap sequence?

Shell Sort starts with a large gap and reduces it each iteration, commonly by dividing the gap by 2 until it reaches 1.

intermediate

What is the time complexity of Shell Sort in the worst case?

The worst-case time complexity depends on the gap sequence but is generally around O(n²). Some sequences can improve it to about O(n log² n).

beginner

Why is Shell Sort faster than simple insertion sort on large lists?

Because it moves elements over large gaps early on, reducing the total number of shifts needed in the final insertion sort phase.

beginner

Show the first gap and the next gap values for an array of size 10 using Shell Sort's common gap sequence.

First gap: 5 (10/2), next gap: 2 (5/2), then 1 (final insertion sort).

What does Shell Sort primarily improve compared to insertion sort?

A It compares elements far apart first

B It uses recursion

C It uses extra memory

D It sorts only even indexed elements

Shell Sort compares elements far apart to reduce disorder before finishing with insertion sort.

What is the final gap value in Shell Sort before the algorithm finishes?

A 0

B Array size

C 1

D 2

The final gap is always 1, which means a normal insertion sort pass.

Which of these is a common way to reduce the gap in Shell Sort?

A Subtract 1 from gap

B Multiply gap by 2

C Add 1 to gap

D Divide gap by 2

The gap is commonly divided by 2 each iteration.

What type of sorting algorithm is Shell Sort?

A Counting sort

B Comparison-based

C Non-comparison-based

D Bucket sort

Shell Sort is a comparison-based sorting algorithm.

Which of these best describes the space complexity of Shell Sort?

A O(1)

B O(log n)

C O(n)

D O(n²)

Shell Sort sorts in place and uses constant extra space.

Explain how Shell Sort works step-by-step on an unsorted array.

Think about sorting elements far apart first, then closer.

Describe the advantages and disadvantages of Shell Sort compared to simple insertion sort.

Consider speed and complexity trade-offs.