Insertion Sort Practice Quiz and Flashcards

10 Questions

What is the purpose of the given algorithm?

To perform a pivot operation on a list of data

What does the 'pivot_index' represent in the algorithm?

The index of the element around which the data is pivoted

What conditions trigger the swapping of elements in the algorithm?

When 'too_big_index' is less than 'too_small_index'

How does the algorithm handle cases where 'too_small_index' is greater than 'too_big_index'?

It loops back to the beginning to reevaluate the data

What is the significance of the 'data[pivot]' element in the algorithm?

It serves as the reference point for comparison during the pivoting process

Explain the role of the 'too_big_index' in the algorithm.

It points to an element larger than the pivot element

What is the purpose of the '--' notation in the algorithm instructions?

To decrement the index value

How are the elements rearranged in the algorithm?

By swapping elements based on their values relative to the pivot element

What happens if the 'data[too_big_index]' is less than or equal to 'data[pivot]'?

The algorithm proceeds to the next step without any swapping

Describe the iterative nature of the algorithm.

It repeats the process of comparing and swapping until the data is correctly sorted

Study Notes

Insertion Sort

Insertion Sort is a sorting algorithm that works by dividing the input array into a sorted and an unsorted region.
Each iteration, the algorithm takes the next element from the unsorted region and inserts it into the correct position in the sorted region.
The algorithm compares the new element with each of the elements already in the sorted region, from right to left.
The cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table.

Insertion Sort Algorithm

The algorithm starts by considering the first element of the array as the sorted region.
For each subsequent element, the algorithm finds the correct position in the sorted region to insert the element.
The algorithm shifts the elements in the sorted region to make room for the new element.
The algorithm repeats this process until the entire array is sorted.

Insertion Sort Example

To insert 12, we need to make room for it by moving first 36 and then 24.
The input array is 5 2 4 6 1 3.
At each iteration, the array is divided into two sub-arrays: a left sub-array (sorted) and a right sub-array (unsorted).

Insertion Sort Code

The C code for Insertion Sort is provided, which includes the following steps:
- Initialize an array of size n.
- Prompt the user to enter the number of elements and the elements themselves.
- Implement the Insertion Sort algorithm.
- Print the sorted list in ascending order.

Quicksort

Quicksort is a divide-and-conquer algorithm that works by selecting a pivot element and partitioning the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
The algorithm recursively applies Quicksort to the sub-arrays until the entire array is sorted.

Quicksort Steps

Step 1: Select a pivot element (arbitrary).
Step 2: Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
Step 3: If the left element belongs to the LEFT group, increment the left index. If the right element belongs to the RIGHT group, decrement the right index.
Step 4: Repeat Step 3 until the left index meets the right index.
Step 5: Swap the pivot element with the element at the final right index.
Step 6: Recursively apply Quicksort to the left and right sub-arrays.

Quicksort Example

The input array is 26 33 35 29 19 12 22.
The pivot element is 26.
The algorithm partitions the array into two sub-arrays: LEFT (19 12 22) and RIGHT (33 35 29).
The algorithm recursively applies Quicksort to the sub-arrays until the entire array is sorted.

Insertion Sort Algorithm Practice