The bubble sort isalso known as the ripple sort. One implementation of this sorting technique is to recurrently move the largest element to the largest index position of the array. Suppose we have an array with the following values: 8, 3,5, 7, and 2. We begin from the left, comparing two numbers at a time and swapping if the left number is bigger than the one on the right, till we reach the end of the array. One pass will put the largest number in the rightmost spot. We start again from the left repeating the above procedure. You will note that we can now stop one before the rightmost digit (Why?). You will need 4 such passes in this example as shown below.
Starting:
8 3 5 7 2
Use all 5 elements:
8> 3, so swap: 3 8 5 7 2
8> 5, so swap: 3 5 87 2
8>7, so swap: 3 5 78 2
8> 2, so swap: 3 5 7 2 8
3 5 7 2 [8]
Now use first 4 elements:
3 not > 5, no swap
5 not >7, no swap
7> 2, so swap: 3 5 2 7 [8]
3 5 2 [78]
3 elements:
3 not > 5, no swap
5 > 2, so swap: 3 2 5 [78]
3 2 [5 78]
2 elements:
3 > 2, so swap: 2 3 [5 78]
2 [3 5 78]
1 element:
nothing to do
[2 3 5 78]
This is how we use Bubble sort/ ripple sort. The keyword 'bubble' in bubble sort usually refers to elements beingaerated to the top of the array, in this case the large elements are rippled to the right!
Specific Instructions:
Write a program that uses the above outlined bubblesort/ripplesort to sortdata of size n. Your program will be reading the values of n from a file. The first number in the data set will indicate the size of the data set.You will be using a two dimensional dynamic array to store the stepwise results of the sort. The starting dimensions of the array will be n by n. When needed, the array should be resized to grow and a message ‘Array Resized’ should be sent to the screen. Your program should consist of at least two modules. One module will implement a class to represent Sorter. Following good object oriented programming practices, keep the data members private. If needed, accessor functions should be declared to set and get the private data. A Sorter object should be able to populate and process itself! Write a test program that illustrates the use of your Sorter class and displays the output for the given input file.
File input/output and operator overloading have to be attempted.So input should be read from a file using overloaded input operator and output should go both to the screen and file (overloading output operator is optional).
Include all the source code (well documented) and input/output files/screenshots.
Input File:
4 72 6 5
5 46 78 1
12 22 33 19 45 30 5
0 14 5 34 90 11
Sample Output (beginning part):
n = 4
7 2 6 5
2 6 5 7
2 5 6 7
2 5 6 7
n = 5
Array Resized
….