Implement various sorting and selection algorithms

Assignment Help Data Structure & Algorithms

Reference no: EM132102634

This project has two major goals:

1. The first is to implement various sorting and selection algorithms.

2. The second is to run experiments comparing the performance of certain algorithms, to collect and plot data, and to interpret the results.
All dynamic memory allocation must be done yourself, i.e., using either malloc() and free(), or new() and delete(). You may not use any external libraries to implement any part of this project. The use of string functions, e.g., strcat, strcmp, is allowed.

The World Series is the annual championship series of Major League Baseball in North America, contested since 1903 between the American League champion team and the National League champion team. A mountain of statistics is gathered for each Major League Baseball (MLB) game, player, player position, and team. In this project you will write a program that executes a sequence of commands that operate on MLB game statistics over a number of years. All input data is to be read from standard input (stdin). Of course, you will redirect stdin from an input file. Similarly, your output must be written to stdout, which can be redirected to an output file. Do not use file operations to process files!

You may assume the format of the input data is correct.

The format of the input data is as follows:
• The number of years y (integer) of team game statistics in this data set.
• For year y the following is provided:
- The total number of teams t in MLB for year y.
- For each of the t teams the following statistics are provided in a tab separated list:
∗ The team name (string),
∗ the league, either American League (AL) or National League (NL) (string),
∗ the number of games in which a player has appeared (integer),
∗ the number of official at bats by a batter (integer),
∗ the number of runs,
∗ the number of times a batter hits the ball and reaches bases safely,
∗ the number of times a batter hits the ball and reaches second base,
∗ the number of times a batter hits the ball and reaches third base,
∗ the number of home runs,
∗ the number of runs that score safely,
∗ the number of walks by a batter (four balls during an at bat),
∗ the number of strikeouts by a batter,
∗ the number of times a player has stolen a base,
∗ the number of times a player has been put out attempting to steal a base,
∗ the average number of hits by a batter defined by hits divided by at bats,
∗ the on base percentage,
∗ the slugging percentage, and
∗ the on base percentage plus slugging.

A structure structmlb stats in §1.1, and in a file named defns.h, have been provided for your use. Upon reading the value of y, you must dynamically allocate an array of struct annual stats of size y, i.e., to hold statistics for each year. Then you initialize the array with the data for each year that follows. Once the data is read and the structure holding the annual statistics structure is initialized, a sequence of commands to be processed follows. The input continues with:

• The number of commands c (integer).
• c commands following the format given in §1.2. Each of the c commands must be processed as described in §1.2.
For each team, the structure mlb stats contains numerous fields associated with each given team in a given year. The structure annual stats holds team statistics for all teams in a given year. The data for this project is taken from the statistics pages for Teams on the Major League Baseball (MLB) site.
#define TEAM_NAME_LEN 50 // Maximum team name string length
#define LEAGUE_NAME 3 // Maximum league name string length,
struct mlb_stats{
char Team[ TEAM_NAME_LEN ]; // Name of the MLB team
char League[ LEAGUE_NAME ]; // American or National league, AL or NL
int G; // Number of games
int AB; // Number of official at bats by a batter
int R; // The number of times a baserunner safely reaches home plate
int H; // The number of hits
int B2; // The number of times a batter hits the ball and reaches second base
int B3; // The number of times a batter hits the ball and reaches third base
int HR; // The number of home runs
int RBI; // The number of runs that score safely
int BB; // The number of walks by a batter
int SO; // The number of strikeouts by a batter
int SB; // The number of times a player has stolen a base
int CS; // The number of times a player has been put out attempting to steal a base
float AVG; // The average number of hits by a batter
float OBP; // The on base percentage
float SLG; // Slugging percentage
float OPS; // The on base percentage plus slugging };
struct annual_stats{
int year;
intno_teams; // Number of teams in the given year
struct mlb_stats *stats; // Array size of statistics depends on number of teams in the given year };
There are six (6) commands to implement. The syntax of valid commands is:
• isort year field order, use the Insertion sort algorithm to sort team data for the given year on the given field in the given order. The output is a list of team name, and field name, with appropriate headers on the list.
- If the year given is not one of the years that is part of the input data, then output the error message: Error: no such year.
- The field may be any field of struct mlb stats. This structure contains fields of strings, integers, and ?oating point numbers. Hence the Insertion sort algorithm should be able to sort any of these types.
- The order may be either incr for increasing order, and decr for decreasing order. If there are multiple fields with the same field value, then they should be sorted in alphabetic order by team name.
• msort year field order, use the Mergesort algorithm to sort team data for the given year on the given field in the given order. Your Mergesort algorithm should allocate and deallocate a separate array for the Merge step, for each level of recursion except the base case. See the command isort for a description of the year, field, and order, as well as the format of the output.
• ifind year field select, first uses Insertion sort to sort the team data for the given year on the given field in increasing order. Then, a selection is made based on select. Valid select for the selection include:
- max, prints the maximum value for the given field in the given year, along with the team name achieving the maximum.
- min, prints the minimum value for the given field in the given year, along with the team name achieving the minimum.
- average, prints the average value for the given field in the given year over all teams. Only an integer or ?oating point field will be given for this item.
- median, prints the median value for the given field in the given year over all teams. Here, "median" refers to the lower median, i.e., the element at position b(n+1)/2c, where n is the total number of elements.
In all cases, if there is more than one team satisfying the selection criteria, output all of them. Similarly, if there are no teams satisfying the selection criteria output the message to that effect.
• mfind year field item, first uses Mergesort to sort the team data for the given year on the given field in increasing order. See the command ifind for a description of the year, field, and item, as well as the format of the output.
• isort range start-year end-year field order, use the Insertion sort algorithm to sort team data for the range of years starting with start-year and ending with end-year, on the given field in the given order. There are two differences between this command and isort for a single year.
- The sort is to be performed using data for all years in the given range. You may assume that start-year < end-year and that all years exist in the input data provided.
- Add the year as part of the output for clarity.

• msort range start-year end-year field order, use the Mergesort algorithm to sort team data for the range of years starting with start-year and ending with end-year, on the given field in the given order. See the command isort on a range of years for a description of the start-year, end-year, field, and order, as well as the format of the output.

Consider the following valid example command sequence. Comments will not be part of the input, and are only included here for clarification.
6 // A total of 6 commands follow
isort 2018 RBI decr // Insertion sort 2018 data on RBI in decreasing order
msort 2018 HR decr // Quicksort 2015 data on home runs in decreasing order
ifind 2018 AB max // Return the team(s) with maximum AB after Insertion sorting 2018 data
ifind 2018 SLG average // Return team(s) with the average SLG after Insertion sorting 2018 data
mfind 2018 SO min // Return team(s) with fewest SO after Mergesorting 2018 data
msort range 2014 2018 BB incr // Mergesort 2014-2018 data on BB in increasing order
PROGRAM MUST BE WRITEN IN C/C++

Reference no: EM132102634

Questions Cloud

What recourse would joan have against paul : Paul, a third year university student, was in the habit of selling his used textbooks at the conclusion of each term. What recourse would Joan have against Paul

What are some of the methods used to ensure consistency : Review two examples, one of a company using multiple brands, and one of a company having multiple products under the same brand, and then explain.

What can the united states learn from germany : Answer advantages and disadvantages of Germany Universal Healthcare compared to the U.S. What can the United States learn from Germany regarding healthcare?

Discuss which tool you would select to implement : Identify three (3) factors you would recommend be used to select a location for a business in order to provide it with a competitive advantage.

Implement various sorting and selection algorithms : Implement various sorting and selection algorithms - comparing the performance of certain algorithms, to collect and plot data, and to interpret the results

Accessories to upscale boutiques in high fashion markets : James's designer gowns and accessories to upscale boutiques in high fashion markets.

How you will address jims recent performance issues : Imagine you work at a company and it is time for an employee named Jim's annual review. Explain how you will address Jim's recent performance issues.

Conspiracy of large flat screen televisions-computer monitor : Three major electronics manufacturers agreed to plead guilty to a price fixing conspiracy of large flat screen televisions and computer monitors.

How does the business measure quality : Think of Wal-Mart, Dunkin Donuts, Starbucks, and Wal-Greens. Pick one of these businesses and assess their customer relationship management (CRM) strategy.

User Account

All Pages