Understanding Insertion Sort

What is the basic principle behind the Insertion Sort algorithm?

• Removing duplicates before sorting

• Sorting the entire array at once

• Using a binary search to find positions

• The basic principle behind Insertion Sort is to build a sorted array one element at a time by inserting elements into their correct position.

How does Insertion Sort compare to other sorting algorithms in terms of time complexity?

• Insertion Sort is O(n^2) on average and worst cases, less efficient than O(n log n) algorithms like Merge Sort and Quick Sort.

• Insertion Sort is O(n) in all cases, making it faster than Merge Sort.

• Insertion Sort is more efficient than Quick Sort with a time complexity of O(n^2).

• Insertion Sort has a time complexity of O(log n) in the worst case.

What is the best-case time complexity of the Insertion Sort algorithm?

• O(n^2)

• O(n)

• O(1)

• O(n log n)

Describe the process of how Insertion Sort works with an example.

• Insertion Sort sorts an array by repeatedly taking an element from the unsorted part and inserting it into the correct position in the sorted part.

• Insertion Sort works by repeatedly swapping adjacent elements.

• Insertion Sort sorts the array by selecting the largest element first.

• Insertion Sort sorts by dividing the array into two halves.

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

• O(n^2)

• O(log n)

• O(n log n)

• O(n)

In which scenarios is Insertion Sort particularly efficient?

• Data with many duplicates

• Small datasets, nearly sorted arrays, and mostly ordered data.

• Randomly ordered data

• Large datasets

How does Insertion Sort handle already sorted arrays?

• Insertion Sort is inefficient for sorted arrays and requires multiple passes.

• Insertion Sort rearranges elements even if the array is already sorted.

• Insertion Sort has a time complexity of O(n^2) for sorted arrays.

• Insertion Sort performs efficiently on already sorted arrays with a time complexity of O(n).

What is the space complexity of the Insertion Sort algorithm?

• O(n)

• O(n log n)

• O(n^2)

• O(1)

Can Insertion Sort be implemented recursively? If so, how?

• No, Insertion Sort can only be implemented iteratively.

• Yes, Insertion Sort can be implemented recursively.

• Recursive implementation of Insertion Sort is inefficient and not possible.

• Insertion Sort is not a sorting algorithm.

What are the advantages and disadvantages of using Insertion Sort?

• Complex to implement

• Stable sorting algorithm

• Advantages: Simple to implement, efficient for small or partially sorted datasets. Disadvantages: Inefficient on large lists, with a time complexity of O(n^2) in average and worst cases.

• Fast for large datasets