Sorting algorithms: bubble, insertion and merge
边玩边学
回答这些题目来赚取能量，然后钓鱼探索。无需账号。
给教育者： 面向 Sorting algorithms: bubble, insertion and merge（KS3 Computing，Computer Science）的即用型课程幻灯片, 复习笔记——用在你的课堂上，或将该知识点作为学习者可实时游玩的互动课堂活动来运行。
课程笔记
What is a Sorting Algorithm?
- A sorting algorithm puts the elements of a list into a defined order, usually numerical or lexicographical (alphabetical).
- The output must be in monotonic order – each element is no smaller (or no larger) than the previous one, depending on the required order.
- The output must be a permutation of the input – it contains all the original elements, just rearranged.
- Sorting is important because it makes other operations, like searching, faster and easier.
- Sorting algorithms are often classified by their computational complexity – how the number of steps grows with the size of the list.
Bubble Sort
- Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order.
- Each pass through the list places the next largest (or smallest) element in its final position, like a bubble rising.
- After each pass, the number of comparisons can be reduced by one because the last element is already sorted.
- Bubble sort has O(n²) time complexity in the worst and average cases – it is inefficient for large lists.
- It is a stable sort – equal elements keep their original relative order.
- It is an in-place algorithm – it uses only a small constant amount of extra memory.
Insertion Sort
- Insertion sort builds the sorted list one element at a time by taking each new element and inserting it into its correct position among the already-sorted elements.
- It works like sorting playing cards in your hand – you pick up a card and place it where it belongs.
- For each element, it compares with the elements before it and shifts them right until it finds the correct spot.
- Insertion sort has O(n²) time complexity in the worst case, but O(n) in the best case when the list is already nearly sorted.
- It is stable and in-place.
- It is an online algorithm – it can sort a stream of data as it arrives.
Merge Sort
- Merge sort is a divide-and-conquer algorithm: it splits the list into two halves, recursively sorts each half, then merges the two sorted halves back together.
- The merge step repeatedly compares the front elements of the two halves and places the smaller one into the output.
- Merge sort has O(n log n) time complexity in all cases – it is much faster than bubble or insertion sort for large lists.
- It is stable – equal elements keep their relative order.
- It is not in-place – it requires extra memory proportional to the size of the list (O(n)).
- Merge sort is typically implemented recursively.
Comparing the Sorts
- Bubble and insertion sort are simple but have O(n²) time – they are fine for small lists but slow for large ones.
- Merge sort is more efficient with O(n log n) time, but it uses extra memory.
- Insertion sort can be faster than merge sort for very small lists or nearly sorted lists because it has low overhead.
- Bubble sort is rarely used in practice because it is usually slower than insertion sort for the same input.
- The choice of algorithm depends on factors like list size, whether the list is nearly sorted, and memory constraints.
Working Through an Example
- Consider sorting the list [5, 2, 4, 1, 3] in ascending order.
- Bubble sort first pass: compare 5 and 2 → swap → [2,5,4,1,3]; compare 5 and 4 → swap → [2,4,5,1,3]; compare 5 and 1 → swap → [2,4,1,5,3]; compare 5 and 3 → swap → [2,4,1,3,5]. The 5 is now in place.
- Insertion sort starts with [5] as sorted. Take 2 → insert before 5 → [2,5]. Take 4 → insert between 2 and 5 → [2,4,5]. Continue until all are placed.
- Merge sort splits [5,2,4,1,3] into [5,2] and [4,1,3]. Recursively sort each half, then merge them: [2,5] and [1,3,4] merge to [1,2,3,4,5].
- Counting comparisons and swaps helps compare the efficiency of each algorithm on the same data.
Key Terms
- Comparison sort: a sort that only uses comparisons between elements to determine order.
- Stable sort: preserves the relative order of equal elements.
- In-place sort: uses only O(1) extra memory (or O(log n) in some definitions).
- Time complexity: how the number of operations grows with input size, often expressed in Big O notation.
- Divide-and-conquer: breaking a problem into smaller subproblems, solving them, and combining the results.
幻灯片
练习题
免费预览——60 题中的 8 题。注册即可查看全部。
1.What is the primary purpose of a sorting algorithm?
Easy- ATo arrange elements in a specific order
- BTo search for an element in a list
- CTo count the number of elements
- DTo remove duplicates from a list
2.Which of the following is NOT a common sorting algorithm?
Easy- ABubble sort
- BInsertion sort
- CMerge sort
- DBinary sort
3.A stable sorting algorithm preserves the relative order of equal elements.
EasyTrue or false?
4.Which sorting algorithm works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order?
Medium- ABubble sort
- BInsertion sort
- CMerge sort
- DSelection sort
5.Which sorting algorithm builds a sorted list one element at a time by inserting each new element into its correct position?
Medium- ABubble sort
- BInsertion sort
- CMerge sort
- DQuick sort
6.Which of the following are true about merge sort? (Select all that apply)
Medium- AIt uses a divide-and-conquer approach
- BIt is typically recursive
- CIt is an in-place sorting algorithm
- DIt has a worst-case time complexity of O(n log n)
7.Arrange the steps of a single pass of bubble sort on the list [5, 2, 4, 1] in the correct order.
Medium- Compare 5 and 2, swap them to get [2, 5, 4, 1]
- Compare 5 and 4, swap them to get [2, 4, 5, 1]
- Compare 5 and 1, swap them to get [2, 4, 1, 5]
- The pass ends with the largest element 5 in its correct final position
8.Insertion sort is an 'online' algorithm because it can sort a stream of data as it arrives.
MediumTrue or false?
历年真题
该知识点的历年真题练习即将推出。
即将推出