Sort a list of strings using Bubble, Merge and Radix sortand write a time complexity analysis
Lab0x01-Radix Sort Sunday, September 12, 2021 9:13 PM Deadline: Tuesday 9/21 11:59pm Overview For this lab you will implement a radix sort function that sorts a list of strings (text), along with a simple (bubble, insertion) and efficient (quick or merg) sort, and run time tests. Discuss the results. Notes/Videos Be sure to watch the videos here: Radix Sort · Implement Radix Sort Algorithm · Your function should take at least these parameters · List of strings · possibly listLength as well, if using, for example, C · width · number of characters in each string · minCharacter · the minimum byte-value or ascii character to use as a letter · typically this will be 'A' (65), 'a' (97) or [space] (32) · tip: · see https://www.ascii-code.com/ · radix number · the number of characters in the alphabet to use · typically this will be · something small, around 5, for testing · 26 (for all upper or lowercase letters) to go with 'a' or 'A' above · or 95 (for all printable ascii characters) · or perhaps 128 256 for all possible 7 or 8 bit values in a byte · NOTE: · The purpose of minByte and radix number is so you can run and show the unsorted/intermediate/sorted lists for small lists, small strings, and small alphabet. This will demonstratet that your algorithm is working properly before testing large lists with wide strings and full alphabets. · demo flag · a 0 or 1 to indicate whether your function should print intermediate lists and bucket counts/indices. · Tips: · Don't swap whole strings around, make an array of pointers or indices and swap those instead · Indices are progrably easier than pointers. See the Tips page for a video suggesting an easy way to handle your string list wit a global 2D array of characters, along with array(s) of indices that provide the sort order. · Create a function to generate test input lists · Should take parameters: · N - length of list · W - width (size of strings · TIP: remember, if using C, that strings need an additional zero byte ("null terminator"), so you need a 2D char array that is W+1 columns. · minCharacter · the lowest/first asci character you want to use for generating strings · alphabetSize · same as radix number above, typically something small for testing, 26 for full alphabet (with 'a' or 'A' as min char), 95 for all printable characters (with [space[ as min char), or 128 or 256. · For simplicity, generate strings that are all the full width, using only the characters determined by your min character and alphabet size. · For example, if N=6, W=4, minChar='A', and alphabetSize = 3 (radix number), y ou might generate a list like this ABBA CBCA BACC CBCB BBCA CCAC · Tip: · characters are just integers in 0..255 range (usually 32..126 for printable ascii) · in C, you want: randomChar = rand() % alphabetSize + minChar; · % in C is the modulo operator (remainder after int division) · Create other utility functions · As needed to display lists, buckets. · Come up with your own way to have your algorithm show/display what it is doing in a reasonably clear way. · Create other sort functions · a version of merge or quick sort · should work on same type of input list of strings as your radix sort · bubble or insertion or other simple sort · should work on same type of input list os strings as your radix sort · Tip: · the same tips apply to these as for radix sort · see Tips page · Verification/Demo Tests · Run a few tests on short lists with small alphabets and small strings, with the demo flag of your function set to true (1). · Good demo parameters would probably be something like the following (not too small, not too big): · list length around 8 to 12 · width 3 · radix number (alphabet size) 5 · Demo should clearly show the unsorted list, then each intermediate stage of the radix sort. Use dashe lines or some other indicator to show each "bucket". · Discuss with me and classmates in the discord about how this might look. · Get screenshots to show these tests. · Shrink down your font size in your terminal, so as to catch as much in one screenshot as possible. · Alternatively make a short video · Run your algorithm and explain the demo. You can do larger demos this way, as it is possible to quickly scroll through intermediate lists. · Run time tests · For this lab (and going forward) make sure you set up a framework for time-testing that lets you measure extremely small times. · See pseudocode here: More Detailed Time Testing Framework · Run your time tests with a string size (width) of 25. · Create the usual table of data for each algorithm · Columns: · Input size (just start at 1 and double for each row) · get as high as you can for each algorithm · Average Runtime · Doubling Ratio (experimental) · Doubling Ratio (expected/theoretical) · Writeup · Header · Name, date, lab number, title, the usual · links to · vido if you made one · source code repo if applicable (easiest way to share source with me) · list other files you may have uploaded to dropbox (such as source files) · Results · Show your tables · Discussion Questions · Anything you want to point out about the demo/verification test? · Explain in your own words why radix sort runs in linear time. · Note anything anomolous in your results that might reflect a problem in your algoritm functions or testing procedures · Are there values of N where your simple sort outperforms the others? · At what value(s) of N do your efficient sort radix sorts overtake the simple sort? · At what vlaue of N does radix overtake your efficient sort? · If it never does… discuss! Bug? Couldn't test large enough N? · What is the largest sort you could handle with each algorithm? · Was memory or time the deciding factor (may be different for each)? · What is it that limits the speed of comparison sorts? What information do they fail to take advantage of? · Demo/Verfication Tests · Present and explain your screenshots. · Discuss anything that might be wrong or anomalous. · If your program has bugs, you get more credit by showing that you at least understand that it is doing something wrong, even if you didn't have time to fix it. Example of what "demo" output would look like: After Sorting on 4th digit: -------[A] 3 ABBA CBCA BBCA -------[B] 1 CBCB -------[C] 2 BACC CCAC ------- After Sort on 3th digit: ------[A] 1 CCAC ------[B] 1 ABBA ------[C] 4 CBCA BBCA CBCB BACC ------ After Sort on 2th digit: …and so on…