From 0 to 1 Data Structures & Algorithms in Java - Insertion Sort

The video tutorial explains insertion sort, a sorting algorithm that builds a sorted list one element at a time by comparing and inserting elements into their correct positions. It highlights the advantages of insertion sort over bubble sort, such as fewer comparisons and swaps, and its adaptive nature. The tutorial includes a detailed example of sorting a list, a code implementation, and a discussion on the algorithm's complexity and benefits.

What is the initial assumption made in insertion sort?

• The list is sorted in descending order.

• The list is completely unsorted.

• The sublist of size one is sorted.

• The entire list is sorted.

In the insertion sort example, what happens when an element is not in the correct position?

• It is swapped with the adjacent element.

• It is removed from the list.

• It is moved to the end of the list.

• It is left in its current position.

What is the purpose of the inner loop in the insertion sort implementation?

• To reverse the order of the list.

• To merge two sorted lists.

• To remove duplicates from the list.

• To find the correct position for the current element.

When does the worst-case scenario occur for insertion sort?

• When the list is empty.

• When the list is already sorted.

• When the list is sorted in reverse order.

• When the list contains duplicate elements.

What is the time complexity of insertion sort in the worst case?

• O(n log n)

• O(n^2)

• O(n)

• O(log n)

How does insertion sort compare to bubble sort in terms of comparisons?

• Insertion sort makes more comparisons.

• Both make the same number of comparisons.

• Bubble sort makes fewer comparisons.

• Insertion sort makes fewer comparisons.

Why is insertion sort considered a stable sorting algorithm?

• It maintains the relative order of equal elements.

• It uses extra space to sort the list.

• It sorts elements in reverse order.

• It requires additional passes to ensure sorting.

What advantage does insertion sort have over bubble sort in nearly sorted lists?

• It requires more swaps.

• It completes sorting more quickly.

• It uses more memory.

• It is less adaptive.

Which sorting method is often used in conjunction with faster algorithms for smaller datasets?

• Insertion sort

• Selection sort

• Merge sort

• Bubble sort

What is a key difference between insertion sort and bubble sort regarding their operation?

• Insertion sort requires an additional pass over the list.

• Bubble sort can break early if the list is sorted.

• Bubble sort uses less memory.

• Insertion sort can break early if the list is sorted.