Lab 5 ? Sorting Algorithms June 12, 2012 This lab will demonstrate the usage of
ID: 3645452 • Letter: L
Question
Lab 5 ? Sorting Algorithms
June 12, 2012
This lab will demonstrate the usage of sorting algorithms. While many different types exist, we will focus on the bubble sort. The bubble sort is also known as the sinking sort. It functions by repeatedly comparing adjacent items and swapping them if they are in the incorrect order. The algorithm keeps checking through all items until no swaps are made. At that point, all items will be in order (ascending or descending). If you are sorting a very large amount of items, more efficient sorting algorithms such as insertion sort or quick sort should be used. See the output of the finished program below.
should using classes and objects
1. Create a new project for lab 5. Use the same setup as the previous labs.
2. The first step will be to declare a global array to hold a random list of numbers. Then create a function to fill the array with random values. You can pick the size of the array and also the range of values. The function to fill the array should have three input arguments: the name of the array to fill, the range of random values (the max value), and the size of the array.
3. Use a FOR loop to fill each element of the array with a random number.
4. In your main function display a message and also the array of random numbers.
5. Next, write a function that uses the bubble sort algorithm to sort the numbers from smallest to largest. The following psuedocode will help you with this:
While there was a swap
Clear the swap flag
For each pair in list
If the pair is in the wrong order
Swap the pair
Set the swap flag
End if
End for
End while
6. The swapping will need a temporary variable to hold one of the values during swapping declare it locally as an INT. Also, you will need to declare a local BOOL to hold the swapping flag.
7. Test your bubble sort (ascending values) function by adding a call to it in your main function. Display a message stating that it is the sorted results and then display the sorted array.
8. Repeat the above steps to create a function to sort the random numbers in descending order as well. Make sure to call your random number filling function after the bubble sort from smallest to largest to reset the array to randomly ordered data.
Extra Credit (up to 15 points)
Implement another sorting algorithm in your code. Make sure to start with randomly ordered data. Display the randomly ordered data, sort it, then display the results. Check on Wikipedia or other internet sources about different sorting algorithms. Also include a brief discussion about the sorting algorithm you chose. Discuss how it works, and how it is better/worse than the bubble sort.
Lab Hints:
Passing an array by reference to a function, note that there is no number inside the ?[ ]?, the size of the array is in this case the third input argument:
void FillList(int list[], int range, int size)
Random numbers review ? include <time.h>, seed the random values by using ?srand(time(NULL))?, and get a random number by using ?list[i] = rand() % range?. In this case the numbers will be from zero to range.
Explanation / Answer
Quick Sort Implementation #include #include #include #include int Partition(int low,int high,int arr[]); void Quick_sort(int low,int high,int arr[]); void main() { int *a,n,low,high,i; clrscr(); coutRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.