Bev Facey Community High

CSE 3110: Iterative Algorithm 1

Students learn a number of standard iterative data processing algorithms useful for working with data structures such as arrays. These include an iterative version of the binary search, the three basic sorts—exchange (bubble), insertion and selection, and a simple merge. In the process, they learn when and where to apply these algorithms.

• Prerequisite: CSE2120: Data Structures 1

Theory

1. Create a slideshow, essay, or other artifact about sorting algorithms, including:
   • describing and representing the following search algorithms:
     • linear search
     • binary search
   • comparing and contrasting how linear and binary searches manipulate data
   • comparing and contrasting the data structures required and the computational efficiencies of linear and binary searches
   • describing and representing the following sorting algorithms:
     • exchange sort; e.g., bubble sort, cocktail sort, gnome sort, comb sort
     • selection sort; e.g., selection sort, strand sort
     • insertion sort; e.g., insertion sort, library sort
   • comparing and contrasting how different classes of sorts manipulate data
   • comparing and contrasting the data structures required and the computational efficiencies of different classes of sorts
   • describing and representing simple iterative merge algorithms

Coding

This can be done in any standard programming language. Submit your program file(s).

Design a program that takes as input a .txt file with a list of numbers, and correctly sorts the list with the following algorithms:

• Exchange (bubble)
• Insertion
• Selection
• Merge

After sorting the list, the program should produce each correctly sorted list in a labelled .txt file, one for each type of sort. The time taken to execute each sorting algorithm should also be recorded and produced as an output. How this is outputted is your choice. Some suggestions are a console, GUI, and .txt output, but other options are acceptable as well.

Sample input: 6843, 6505, 3009, 3354, 5153, 5292, 9302, 7438, 1981, 1402, 9843, 3648, 2789, 5154, 8264, 4146, 8391, 3034, 1094, 9440, 7059, 9783, 5443, 5659, 7585, 1564, 9640, 9299, 2561, 8947, 956, 4192, 5466, 3053, 7439, 5531, 2574, 848, 6911, 3894, 6972, 4908, 5840, 8897, 4312, 1535, 6107, 9805, 6724, 2382, 528, 9042, 144, 2118, 3211, 5979, 2159, 505, 3855, 7032, 8012, 3766, 2844, 4182, 4620, 1284, 5756, 1344, 6917, 573, 5557, 7394, 386, 8498, 9197, 4129, 3357, 6964, 5815, 6705, 4236, 1295, 6518, 8575, 2978, 4923, 1892, 5453, 3583, 363, 4935, 7574, 483, 3500, 1084, 927, 4763, 2582, 2800, 2211

Sample output: 144, 363, 386, 483, 505, 528, 573, 848, 927, 956, 1084, 1094, 1284, 1295, 1344, 1402, 1535, 1564, 1892, 1981, 2118, 2159, 2211, 2382, 2561, 2574, 2582, 2789, 2800, 2844, 2978, 3009, 3034, 3053, 3211, 3354, 3357, 3500, 3583, 3648, 3766, 3855, 3894, 4129, 4146, 4182, 4192, 4236, 4312, 4620, 4763, 4908, 4923, 4935, 5153, 5154, 5292, 5443, 5453, 5466, 5531, 5557, 5659, 5756, 5815, 5840, 5979, 6107, 6505, 6518, 6705, 6724, 6843, 6911, 6917, 6964, 6972, 7032, 7059, 7394, 7438, 7439, 7574, 7585, 8012, 8264, 8391, 8498, 8575, 8897, 8947, 9042, 9197, 9299, 9302, 9440, 9640, 9783, 9805, 9843

This site is open source. Improve this page.