OBJECTIVES
Learn to load and parse CSV files. Implement various sorting and search algorithms. Utilize recursion to solve problems. Clone arrays into new lists.
You will be loading in a CSV file that contains unsorted data and you can store that information in a List (each item is a string). The user will be able to sort that data using the different sorting algorithms that we covered in the lecture: Bubble, Merge. Search a sorted list with a binary search algorithm.

Topics Covered
Cloning, bubble sort, merge sort, binary search, CSV, Split, File loading

PART 3-1
Project Setup
• Create a console application
• Add the inputFile.csv file to your console app. o Right-click the console application project
o Select Add->Existing Item…
o Navigate to where the file is stored on your hard drive
o Double-click to add to your project.
o Select the file in your Solution Explorer
o Open the Properties tab
o Set these properties
▪ Build Action is None
▪ Copy to Output Directory is Copy Always

PART 3-2
Load the file
Open and read the line from the inputFile.csv file. The line in the file contains a list of comic book titles separated by commas. Split the string and store each title in a List of strings.

PART 3-3
Bubble Sort
Implement the Bubble sort algorithm. You want to keep the original list unsorted so make sure to clone the original list each time you call the Bubble sort.
Here is the Wikipedia pseudocode:
procedure bubbleSort(A : list of sortable items)
n := length(A) repeat swapped :=
false
for i := 1 to n – 1 inclusive do
if A[i – 1] > A[i] then
swap(A[i – 1], A[i])
swapped = true end if
end for n := n – 1 until not
swapped end procedure
Turn this into C# code. NOTE: swap is a method you must create. See the lectures slides for how to swap 2 items in a list.

PART 3-4
Binary Search
Implement the Binary Search algorithm (use a recursive approach).
1. Clone the original list and sort the cloned list (call Sort on the list).
2. Loop over the sorted list.
3. Call your binary search method to search the sorted list for each title in the sorted list. HINT: the index returned from your binary search should match the index.
Show the search title, the index and the index returned by your binary search method.

PART 3-5
Merge Sort
Implement the Merge sort algorithm. You want to keep the original list unsorted so make sure to clone the original list each time you call the Merge sort.
Here is the Wikipedia pseudocode:
function merge_sort(list m) is
// Base case. A list of zero or one elements is sorted, by definition.
if length of m ≤ 1 then return m
// Recursive case. First, divide the list into equal-sized sublists
// consisting of the first half and second half of the list.
// This assumes lists start at index 0.
var left := empty list var
right := empty list for each x
with index i in m do if i <
(length of m)/2 then
add x to left else
add x to right
// Recursively sort both sublists.
left := merge_sort(left)
right := merge_sort(right)
// Then merge the now-sorted sublists.
return merge(left, right)

function merge(left, right) is
var result := empty list
while left is not empty and right is not empty
do if first(left) ≤ first(right) then
add first(left) to result
left := rest(left) //remove the first item
else
add first(right) to result
right := rest(right) //remove the first item
// Either left or right may have elements left; consume them.
// (Only one of the following loops will actually be entered.)
while left is not empty do
append first(left) to result
left := rest(left) while right is
not empty do append
first(right) to result right
:= rest(right) return result

PART 3-6
The Menu
Show a menu to the user so they can select one of the algorithms (bubble, merge and binary search) as well as Exit. (Maybe use the ReadChoice method you created in the first lab?) After calling any of the sorting methods, you should display the unsorted list along with the sorted list.
1. Bubble Sort
2. Merge Sort
3. Binary Search
4. Exit