Insertion Sort Practice Quiz and Flashcards

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.

Description

Test your understanding of the Insertion Sort algorithm by sorting a set of cards using the insertion technique. Learn to compare and insert cards in the correct position to achieve a sorted arrangement. Practice inserting cards like 12 by making room for it through moving other cards like 36 and 24.