Question
I already did quick_sort I just need help with merge_sort. Run this program in C++ please! Write two short programs that implement the Quicksort and
I already did quick_sort I just need help with merge_sort. Run this program in C++ please!
Write two short programs that implement the Quicksort and Merge Sort algorithms. Each of these programs will read up to 1000 integers, sort them, and then print them in a formatted fashion.
1. Initial Setup Log in to Unix. Run the setup script for Assignment 3 by typing: setup 3
2. Input Each program you write should read from standard input using input redirection. Input files for this assignment will contain a series of integers separated by whitespace.
3. Files We Give You The setup script will create the directory Assign3 under your csci241 directory. It will copy a makefile named makefile to the assignment directory and will also create symbolic links to a number of sample data files that you can use to test your programs. You should assume that we will test your programs using data files other than the ones supplied as part of this assignment. Using the makefile we give you, you can build one specific program or build all three programs. To build a single specific program, run the command make followed by the target name for the program that you want to build (quick_sort or merge_sort). For example: z123456@turing:~$ make merge_sort To build both programs, run the command make all or just make. Running the command make clean will remove all of the object and executable files created by the make command. The data files are named random6.txt, random8.txt, random16.txt, etc., with the numeric part of the file name specifying the number of random values that the file contains.
4. Files You Must Write You will write two files for this assignment: quick_sort.cpp - This file should contain your solution that uses the quicksort algorithm. merge_sort.cpp - This file should contain your solution that uses the merge sort algorithm. The two files will obviously contain a great deal of identical code.
5. Output The output should print 8 sorted numbers per line (of course the last line may have less than 8 numbers), nicely aligned in columns. Numbers should be right-aligned. Use the setw manipulator to print numberswith a width of 8 characters, padded with leading spaces. Print a newline character ( ) at the end of each line. The output should
look like this:
z123456@turing:~/csci241/Assign3$ ./quick_sort < random6.txt
19 61 75 88 90 98
z123456@turing:~/csci241/Assign1$
z123456@turing:~/csci241/Assign3$ ./merge_sort < random16.txt
7 15 15 20 30 37 42 52
53 56 58 63 65 74 78 89
z123456@turing:~/csci241/Assign1$
z123456@turing:~/csci241/Assign3$ ./quick_sort < random25.txt
1 23 106 127 147 148 157 208
239 265 282 483 561 576 579 677
753 853 879 911 945 959 965 978
982
959 965 978 982 z123456@turing:~/csci241/Assign3$
Merge sort algorithm:
procedure merge(array : list of items to merge, start : first element of first sublist, mid : last element of first sublist, end : last element of second sublist) temp : temporary array of size (end - start + 1) i start j mid + 1 k 0 while i <= mid and j <= end if array[i] < array[j] temp[k] array[i] i i + 1 else temp[k] array[j] j j + 1 end if k k + 1 end while while i <= mid temp[k] array[i] i i + 1 k k + 1 end while while j <= end temp[k] array[j] j j + 1 k k + 1 end while Copy elements of temp back into array end procedure
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started