Stable vs. Non-Stable Sorting
Prerequisites, Goals, and Outcomes
Prerequisites: Students should have mastered the following prerequisite skills.
; Sorting - Knowledge of selection sort and quicksort
; Complexity - Knowledge of basic asymptotic analysis and Big-Oh notation Goals: This assignment is designed to reinforce the student's understanding of basic and fast sorting algorithms and complexity.
Outcomes: Students successfully completing this assignment would master the following outcomes.
; Understand selection sort and quicksort
; Understand the difference between stable and non-stable sorting algorithms Background
A stable sort is a sort algorithm that performs the same amount of work regardless of the data being sorted. The amount of work a non-stable sort performs, on the other hand, can
vary significantly depending on the arrangement of data. This translates to stable sorts having identical best case, worst case, and average case complexity. The worst case complexity of a non-stable sort can be an entirely different runtime class than its best or average case.
The program to be completed for this assessment demonstrates the runtime differences between a stable and non-stable sort. The stable sort examined in this assessment is selection sort and the non-stable algorithm examined in this assessment is quicksort. Each algorithm is encapsulated in a corresponding class. Method init of these classes
populates an array. This function populates the array with data that triggers either the average or worst case of the algorithm. For the stable sort algorithm, selection sort, the average and worst case are identical. The quicksort algorithm, on the other hand, has distinct worst and average cases. A supplied main routine repeatedly initializes and sorts these arrays to demonstrate the differences between the stable and non-stable sort algorithms. The correct implementation of method init requires the generation of random numbers.
Use the rand library function to generate a random integer.
Note to Viusal C++ users: The default stack size in Visual C++ is 1 MB. To execute your solution, you should increase the stack size in your system.
To increase the stack to 10 Mb:
1. On menu Project, select the project Properties.
2. Expand Configuration Properties.
3. Expand Linker.
4. Select System.
5. On Stack Reserve Size, write 10485760.
6. On Stack Commit Size, write 10485760.
Following is a list of files needed to complete this assessment.
; handout-files.zip contains all of the following necessary files:
o main.cpp - This file contains the main routine.
o sort.h - This declares a sort class.
o sort.cpp - This defines class sort.
o quicksort.h - This declares a quicksort class.
o quicksort.cpp - This defines class quicksort.
o selectionsort.h - This declares a selection sort class.
o selectionsort.cpp - This defines class selectionsort.
To complete this assessment, you need to complete the init methods of class quicksort
and class selectionsort.
To begin, verify the files needed for this assessment.
1. Extract the archive to retrieve the files needed to complete this assessment. Following is an ordered list of steps that serves as a guide to completing this assessment.
Work and test incrementally. Save often.
1. Begin by making sure you understand what makes selection sort a stable sort
algorithm and what makes quicksort a non-stable sort algorithm. Specifically, find
out what ordering of data causes the quicksort algorithm to degrade from an O(n
2log(n)) algorithm to an O(n) algorithm.
2. Next, complete the implementation of method init for class selectionsort.
Since this algorithm is stable, this implementation should be the same for the worst
and average case. The implementation should populate the inherited numbers array
with data that, when sorted, triggers the average case.
3. Then, finish the implementation of method init for class quicksort. Since this
algorithm is non-stable, this method should populate the inherited numbers array
with different data to trigger the worst and average cases. Test your implementation
main.cpp. The times reported for the worst by compiling and running the supplied
case of the quicksort should be relatively close to the times reported for the average
case of the selection sort.
Submit only the following.
1. - finished version of class quicksort quicksort.cpp
2. selectionsort.cpp - finished version of class selectionsort