Shell Sort Algorithm in DSA Javascript - 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 first, then reducing the gap between elements to be compared. This helps move elements closer to their correct position faster.

intermediate

How does Shell Sort choose the gap values during sorting?

Shell Sort starts with a large gap, usually half the array length, and keeps reducing it by dividing by 2 until the gap is 1, where it performs a final insertion sort.

intermediate

Why is Shell Sort faster than simple Insertion Sort on large arrays?

Because it moves elements over large gaps early on, it reduces the total number of shifts needed in the final insertion sort step, making it faster on bigger lists.

advanced

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

The worst-case time complexity depends on the gap sequence, but commonly it is around O(n²). Some gap sequences can improve it to about O(n^(3/2)) or better.

beginner

Show the first gap and the next gap used in Shell Sort for an array of length 8.

First gap: 4 (8 divided by 2). Next gap: 2 (4 divided by 2). Then gap reduces to 1 for final insertion sort.

What is the initial gap value in Shell Sort for an array of size 10?

A 1

B 2

C 10

D 5

The initial gap is usually half the array size, so 10 / 2 = 5.

Which sorting algorithm is Shell Sort an improved version of?

A Bubble Sort

B Insertion Sort

C Selection Sort

D Merge Sort

Shell Sort improves Insertion Sort by allowing exchanges of far apart elements.

What happens when the gap in Shell Sort reaches 1?

A A final insertion sort is performed

B The algorithm stops

C The array is reversed

D The gap resets to the array length

When gap is 1, Shell Sort performs a final insertion sort to finish sorting.

Which of these is true about Shell Sort's time complexity?

A Depends on gap sequence

B Always O(n²)

C Always O(n log n)

D Always O(n)

Shell Sort's time depends on the gap sequence used.

Shell Sort is best described as:

A A non-comparison sorting algorithm

B A divide and conquer algorithm

C A comparison-based sorting algorithm

D A recursive sorting algorithm

Shell Sort compares and swaps elements, so it is comparison-based.

Explain how Shell Sort improves the efficiency of insertion sort using gap sequences.

Think about how moving elements far apart early helps sorting.

Describe the role of the gap sequence in the Shell Sort algorithm and its impact on performance.

Consider how changing gaps changes sorting steps.