AP CSA selection insertion and merge sort key terms

Selection sort definition?

A sorting algorithm that repeatedly selects the smallest or largest element from the unsorted portion and moves it to the sorted portion.

Insertion sort process?

Inserts each element into its correct position in a sorted sublist. Works by comparing and shifting elements until the correct spot is found.

True or false: Merge sort is an in-place sorting algorithm.

False. Merge sort requires additional space for merging, making it not in-place.

Best case time complexity of insertion sort?

O(n) when the array is already sorted. Efficiency improves with nearly sorted data.

Compare selection sort and insertion sort.

- Selection sort: O(n^2) worst case. - Insertion sort: O(n^2) worst case, but O(n) best case. - Insertion often faster for small or partially sorted arrays.

Fill in the blank: Merge sort divides the array into ____ parts.

Two parts, recursively sorts them, and then merges the sorted parts.

What is the worst case time complexity of merge sort?

O(n log n) due to the divide and conquer approach.

Example of insertion sort on: [5, 2, 4, 6, 1, 3]

Steps: 2 starts at index 1. 5 and 2 are compared. Shift 5, insert 2. Continue with 4, 6, 1, 3.

True or false: Selection sort is more efficient than insertion sort.

False. Insertion sort performs better on average for small datasets.

Define stable sorting algorithm.

A stable sorting algorithm maintains the relative order of records with equal keys. Both insertion and merge sort are stable.

What is selection sort?

A sorting algorithm that repeatedly selects the smallest element from the unsorted portion and moves it to the sorted portion.

True or False: Selection sort is efficient for large datasets.

False - It has an average and worst-case time complexity of O(n²), making it inefficient for large datasets.

Describe the main process of insertion sort.

Insertion sort builds a sorted array one element at a time by repeatedly taking an unsorted element and finding its correct position in the sorted part.

Selection sort vs. Insertion sort: Efficiency

Selection sort: O(n²) in all cases Insertion sort: O(n) best case (nearly sorted), O(n²) worst case.

How does selection sort find the minimum element?

It iterates through the entire unsorted array, comparing elements to find the smallest one.

Fill in the blank: The ___ of insertion sort is based on the idea of building a sorted array incrementally.

key concept

What happens in each pass of insertion sort?

An element is picked and compared with sorted elements, and it is placed in the correct position.

True or False: Insertion sort is typically faster than selection sort for small arrays.

True - Due to lower overhead and better performance on partially sorted data.

Explain the swap process in selection sort.

Every time the minimum is found, the algorithm swaps it with the first unsorted element.

Key characteristic of insertion sort:

Efficient for small or nearly sorted datasets. It has low overhead.

What are the steps in selection sort?

1. Start with the full array 2. Find the minimum 3. Swap minimum with the first unsorted element 4. Repeat until sorted.

Insertion sort working example: Sort [5, 2, 4, 6, 1, 3].

1. [2, 5, 4, 6, 1, 3] after first pass 2. [2, 4, 5, 6, 1, 3] after second pass 3. [1, 2, 4, 5, 6, 3] after last pass.

What is merge sort?

A divide-and-conquer sorting algorithm that divides an array into halves, sorts each half, and merges them back together.

How does merge sort work?

1. Divide the array into two halves. 2. Recursively sort each half. 3. Merge the sorted halves back together.

What is the time complexity of merge sort?

O(n log n) in all cases (best, average, worst). It is efficient for large datasets.

True or false: Merge sort is an in-place sorting algorithm.

False. Merge sort requires additional space for the temporary arrays used during merging.

Fill in the blank: Merge sort is a __________ algorithm.

Stable. It maintains the relative order of equal elements.

What is the main advantage of merge sort over others?

Merge sort is particularly efficient for large lists and linked lists.

True or false: Merge sort can be implemented iteratively.

True. Merge sort can be implemented using both recursive and iterative approaches.

Compare merge sort and quicksort.

- Merge sort: Stable, O(n log n), uses extra space. - Quicksort: Unstable, O(n log n) average, O(n^2) worst, in-place.

What is the merging process in merge sort?

Combining two sorted arrays into one sorted array, by comparing elements one by one.

How does merge sort handle large datasets?

It efficiently divides data into smaller chunks, sorts them, and merges them, minimizing comparisons.

Provide a simple example of merge sort.

Array: [38, 27, 43, 3, 9, 82, 10]. 1. Divide: [38, 27, 43] & [3, 9, 82, 10]. 2. Sort: [27, 38, 43] & [3, 9, 10, 82]. 3. Merge: [3, 9, 10, 27, 38, 43, 82].

What is the space complexity of merge sort?

O(n) due to the temporary arrays used for merging elements.