Sorting Algorithms — Algorithms Übungsblatt

Grades 11–12 / College Mittlerer Schwierigkeitsgrad 10 Aufgaben

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.

Geübte Fähigkeiten

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

Name: Datum: Stunde:

Übungsblatt: Sorting Algorithms

Anleitung: Löse jede Aufgabe sorgfältig. Zeige deine Arbeit klar. Schreibe deine endgültige Antwort in das vorgesehene Feld oder wie angewiesen auf ein separates Blatt.

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 — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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

Sorting Algorithms — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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

Sorting Algorithms — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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

Lösungsschlüssel

1.

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

Endgültige Antwort: C
2.

Endgültige Antwort: 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.

Endgültige Antwort: 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.

Endgültige Antwort: B

Lösungsschlüssel (Fortsetzung)

5.

Endgültige Antwort: 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.

Endgültige Antwort: 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.

Endgültige Antwort: C
8.

Endgültige Antwort: 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.

Lösungsschlüssel (Fortsetzung)

9.

Endgültige Antwort: 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)$ .

Endgültige Antwort: B

PDF herunterladen

Häufige Fehler, die es zu vermeiden gilt

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

Erstelle dein eigenes Arbeitsblatt

Möchtest du neue sorting algorithms-Aufgaben in deiner gewünschten Schwierigkeit? Nutze WorksheetSmith, um in Sekunden ein individuelles, druckfertiges PDF zu erstellen.

Individuelles Sorting Algorithms-Arbeitsblatt erstellen

Zuletzt aktualisiert: 2026

Die WorksheetSmith-Arbeitsblatt-App öffnen