Title: Sorting Defining Features Matrix
Author: Kate Deibel
Date: March 30, 2004
Technique: Defining Features Matrix
Before Class Preparation Time: MEDIUM
Class Completion Time: LOW
In-Class Analysis Time: LOW
Out-Of-Class Analysis Time: LOW
Assessment Goals:
- Develop analytic skills
- Improve memory skills
- Learn terms and facts of this subject
- Learn concepts and theories of this subject
Topics:
- Sorting
- Algorithms
- Efficiency
- Complexity
- Stable sorts
- In-place sorts
Purpose:
This exercise gives instructors the chance to find out if students understand the similarities and differences between various sorting algorithms.
Activity:
Fill out the following matrix. This matrix lists various sorting algorithms and it's your job to decide if these algorithms possess various properties. Assume that your are assorting arrays, not linked lists. Please complete the table with '+' or '-' labels.
|
|
O(n log n running time)
|
Best-case performance: O(n)
|
Stable
|
In-place
|
|
Selection Sort
|
|
|
|
|
|
Insertion Sort
|
|
|
|
|
|
Merge Sort
|
|
|
|
|
|
Quick Sort
|
|
|
|
|
|
Heap Sort
|
|
|
|
|
Solution:
|
|
O(n log n running time)
|
Best-case performance: O(n)
|
Stable
|
In-place
|
|
Selection Sort
|
-
|
-
|
+
|
+
|
|
Insertion Sort
|
-
|
+
|
+
|
+
|
|
Merge Sort
|
+
|
-
|
+
|
-
|
|
Quick Sort
|
-
|
-
|
-
|
+
|
|
Heap Sort
|
+
|
-
|
-
|
+
|
Instructor Responses:
- Lecture
- Next Day Summary
- Class Discussion
- Small Group Discussions
- Homework
Response Analysis:
The following must be done out of class:
- In a first pass, mark and count the number of incorrect answers. Also, mark any answers that you find surprising.
- For each question that has a significant (your judgement call) of incorrect answers, do the following:
- Look through the answers to these questions.
- Attempt to identify the nature of the most common errors that are made.
- Discuss these errors in class, using the common mistakes that you identified .
In-class feedback can be done by having students write or say out loud their own answers, but caution must be taken to avoid embarassing or ridiculing a student for making mistakes.
Variant Uses of Activity:
- Have students write short explanations for their answers in the matrix.
- Have students work in groups to complete this activity. The instructor may want to circulate throughout the groups to ensure that each group is making progress. After the groups have completed their matrix, the instructor can ask for volunteers for each item. Be sure to ask for explanations as to why they assigned a plus or minus to each column.
- Have students work individually on their problems and form a small group to discuss their answers.
Device-Enabled: Has Been Enabled
Related Topics: