DOC

# optional exercise 5

By Alan Hart,2014-10-17 11:47
10 views 0
optional exercise 5

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.

Description

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.

4. Select System.

5. On Stack Reserve Size, write 10485760.

6. On Stack Commit Size, write 10485760.

Files

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.

Submission

Submit only the following.

1. - finished version of class quicksort quicksort.cpp

2. selectionsort.cpp - finished version of class selectionsort

Report this document

For any questions or suggestions please email
cust-service@docsford.com