Sorting Algorithms — Fiche d'exercices de Algorithms

Grades 11–12 / College Difficulté moyenne 10 problèmes

Sorting arranges elements in order (ascending or descending). Different algorithms trade off simplicity, speed, and memory. Stability means equal elements keep their relative order after sorting.

Bubble sort repeatedly swaps adjacent out-of-order pairs — O(n²) time, simple but slow. Selection sort finds minimum and swaps — also O(n²). Merge sort divides, sorts halves, merges — O(n log n), stable, uses extra memory.

Quicksort picks a pivot, partitions smaller/larger — average O(n log n), in-place variants common. For small or nearly sorted data, simpler algorithms may suffice; for large data, O(n log n) is preferred.

Compétences travaillées

Tracing simple sorts on small arrays
Comparing time complexities
Understanding stable vs. unstable sorts
Choosing appropriate sorting algorithm

Nom : Date : Période :

Fiche d'exercices : Sorting Algorithms

Consignes : Résous chaque problème avec soin. Montre clairement tout ton travail. Écris ta réponse finale dans l'espace prévu ou sur une feuille séparée comme indiqué.

1.**Multiple Choice:** Which of the following sorting algorithms has the best average-case time complexity?
1. A. Bubble Sort
2. B. Insertion Sort
3. C. Merge Sort
4. D. Selection Sort

Sorting Algorithms — Fiche d'exercices (suite)

2.**Short Answer:** What is the worst-case time complexity of Quick Sort, and what condition causes it?
3.**Free Response:** Trace the execution of Merge Sort on the following array: $[38, 27, 43, 3, 9, 82, 10]$ . Show each recursive split and the merge steps.

Sorting Algorithms — Fiche d'exercices (suite)

4.**Multiple Choice:** Which sorting algorithm works by repeatedly swapping adjacent elements if they are in the wrong order?
1. A. Merge Sort
2. B. Bubble Sort
3. C. Quick Sort
4. D. Heap Sort

Sorting Algorithms — Fiche d'exercices (suite)

5.**Short Answer:** Explain why Insertion Sort is efficient for nearly sorted data. What is its best-case time complexity?

Sorting Algorithms — Fiche d'exercices (suite)

6.**Free Response:** Perform one complete pass of Bubble Sort on the array $[5, 1, 4, 2, 8]$ , showing the array after each swap. Then state whether the array is fully sorted after that pass.

Sorting Algorithms — Fiche d'exercices (suite)

7.**Multiple Choice:** Which of the following is **not** an in-place sorting algorithm?
1. A. Quick Sort
2. B. Heap Sort
3. C. Merge Sort
4. D. Insertion Sort

Sorting Algorithms — Fiche d'exercices (suite)

8.**Short Answer:** What is the key property of a heap that makes Heap Sort possible? Briefly describe how Heap Sort works.

Sorting Algorithms — Fiche d'exercices (suite)

9.**Free Response:** Given the array $[64, 34, 25, 12, 22, 11, 90]$ , show the result after each pass of Selection Sort. How many passes are needed to fully sort the array?

Sorting Algorithms — Fiche d'exercices (suite)

10.**Multiple Choice:** Which sorting algorithm has a worst-case time complexity of $O(n^2)$ but an average-case of $O(n \log n)$ ?
1. A. Merge Sort
2. B. Quick Sort
3. C. Heap Sort
4. D. Bubble Sort

Corrigé

1.

Merge Sort has average-case $O(n \log n)$ ; Bubble, Insertion, and Selection are $O(n^2)$ .

Réponse finale : C
2.

Réponse finale : Worst-case time complexity is $O(n^2)$ . This occurs when the pivot chosen is always the smallest or largest element (e.g., already sorted or reverse-sorted array with poor pivot selection).
3.

Réponse finale : Split: $[38,27,43,3]$ and $[9,82,10]$ ; Further splits until single elements: ; $[38,27]$ , $[43,3]$ , $[9,82]$ , $[10]$ ; Merge $[38,27] \rightarrow [27,38]$ ; $[43,3] \rightarrow [3,43]$ ; $[9,82] \rightarrow [9,82]$ ; Merge $[27,38]$ and $[3,43] \rightarrow [3,27,38,43]$ ; Merge $[9,82]$ and $[10] \rightarrow [9,10,82]$ ; Final merge: $[3,27,38,43]$ and $[9,10,82] \rightarrow [3,9,10,27,38,43,82]$
4.

Bubble Sort repeatedly swaps adjacent elements if they are out of order.

Réponse finale : B

Corrigé (suite)

5.

Réponse finale : Insertion Sort is efficient for nearly sorted data because it only makes a few comparisons and shifts; best-case time complexity is $O(n)$ (already sorted).
6.

Réponse finale : Pass 1: ; Compare 5 and 1: swap $\rightarrow [1,5,4,2,8]$ ; Compare 5 and 4: swap $\rightarrow [1,4,5,2,8]$ ; Compare 5 and 2: swap $\rightarrow [1,4,2,5,8]$ ; Compare 5 and 8: no swap ; Array after pass: $[1,4,2,5,8]$ . Not fully sorted (4 and 2 are out of order).
7.

Merge Sort requires $O(n)$ extra space, so it is not in-place.

Réponse finale : C
8.

Réponse finale : A heap is a complete binary tree where each parent is greater (max-heap) or smaller (min-heap) than its children. Heap Sort builds a max-heap, then repeatedly swaps the root with the last element and reheapifies the reduced heap.

Corrigé (suite)

9.

Réponse finale : Pass 1: $[11,34,25,12,22,64,90]$ ; Pass 2: $[11,12,25,34,22,64,90]$ ; Pass 3: $[11,12,22,34,25,64,90]$ ; Pass 4: $[11,12,22,25,34,64,90]$ ; Pass 5: $[11,12,22,25,34,64,90]$ (no change) ; 6 passes are needed (for $n=7$ , Selection Sort requires $n-1=6$ passes).
10.

Quick Sort has worst-case $O(n^2)$ but average-case $O(n \log n)$ .

Réponse finale : B

Télécharger le PDF

Erreurs fréquentes à éviter

Assuming bubble sort is O(n) with early exit always
Confusing merge sort space complexity
Incorrect pivot partition in quicksort traces
Thinking all O(n²) sorts behave identically in practice

Générez la vôtre

Vous voulez un nouvel ensemble de problèmes de sorting algorithms à la difficulté de votre choix ? Utilisez WorksheetSmith pour compiler un PDF personnalisé prêt à imprimer en quelques secondes.

Générer une fiche personnalisée sur Sorting Algorithms

Dernière mise à jour : 2026

Ouvrir l'application de fiches WorksheetSmith