LAB 09A - SORTING DATA

Concepts

Sorting is the process of organizing the elements of a list in a specific order. Arrays provide an efficient way to temporarily store in memory all the elements that need to be sorted. There are many sorting algorithms, each of them with their particular strengths and weakness, resulting in possibly different execution times for the same input. In this lab you are to write an implementation for one sorting algorithm. You can choose any algorithm you want, or use the selection sort algorithm described next.

Selection Sort

The selection sort is one of the most simple algorithms used for sorting. It divides the list of input values into two parts: one with values that are already sorted on the left side and another with the remaining (to be sorted) values on the right side. The algorithm works by constantly adding values from the right side to the left side in the correct order. This is done by finding the smallest (or largest, depending on sorting order) value of the right side list and moving (if needed) that value to the left side list at each iteration. The pseudocode below shows an implementation for the selection sort algorithm for sorting in increasing order.

Let a = array containing the values
Let n = # of elements
Let i = 0
Repeat
    Find the array element with the min value among a[i] ... a[n-1]
    Swap this element with a[i]
    Increment i by 1
Until i is (size - 1)
        

Instructions

Create a new Visual Studio empty project (Lab09A is a good name) and add a new main.cpp source code to it. After your project is created, go to its folder using Windows Explorer and create a new subfolder called data. Copy this data2sort.txt file into the data folder. This file contains 100 integer values randomly generated from 0 to 999. Your task is to read this data file into an array, and then sort all of its values using an algorithm (e.g., selection sort) of your choice. We suggest you print your array before and after the sorting procedure, to verify the algorithm does what you think it does.

Hints

To help structure your solution, we advise you to create the following functions.

// reads the input file into an array
// returns true (no I/O errors) or false (I/O errrors)
bool ReadData(string fileName, int array[], int size);

// swaps element a with b, both passed by reference
void Swap(int &a, int &b); 

// implements the selection sort (or use a different algorithm) 
void SelectionSort(int array[], int size); 

// prints the array passed to the function
void Print(int array[], int size);
        

Lab 09A2 (2 points extra credit)

Lab 09A will be due with Homework 9; Lab 09A2 is optional and worth two points extra credit on Homework 9.

Create a new Visual Studio empty project (Lab09A2 is a good name) and add a new main.cpp source code file to it. You must create a new empty project for Lab09A2 (if you choose to do this extra credit). That is, you should not augment Lab09A main.cpp with your solution for Lab09A2. (You are welcome, however, to begin Lab09A2 by copying your main.cpp file from Lab09A to the main.cpp file for Lab09A2.)

Your Lab09A reads in a data file to a 1D array, and sorts the data in the file in increasing order. Your Lab09A2 project should create a 2D array, such that the 1st row of the array is the data file contents sorted into increasing order and the 2nd row of the 2D array is the data file contents sorted into decreasing order.

No hints (as this is extra credit baby!). Be sure to print your 2D array with appropriate titles (e.g., "1st row sorted in increasing order follows").