CMPS 2010 - Search & Sort Arrays

Main() Function

1. Create an integer array with a size of 25. Call your random() function before your do while loop so that, at the beginning of the program, your array will be filled with random numbers.

2. Create a menu using a do-while loop and a switch case, similar to your menu in Lab 7.

   

---

Display Function.

If option '0' is chosen, display the current array. You may use your display function from Lab 7.

Function prototype: void display(int arr[], int size); or void display(int *arr, int size);

---

1. Unique Random Numbers

If option '1' is chosen, fill the array with a new set of numbers and display them. Create a random() function that fills your array with unique numbers within range[5, 50]. No duplicate numbers allowed. (Hint: See linear search algorithm in Ch.8 and see how it works.) You may use the same function parameters as your Lab 7 random function.

Reminder: This is the format for the rand() function: rand % (range) + min

Function prototype: void random(int *arr, int size); or void random(int arr[], int size, int min, int max);

---

2. Search Algorithms

If option '2' is chosen, prompt the user for the number that they want to search for and display the array. Call both linear and binary search functions and output the index position that both algorithms returned. Let the user know if the linear search and the binary search found the number. Your search functions do not print anything to the screen. You have your display function for that. (See Ch. 8 for linear and binary search algorithms.)

1. Create a linear_search function that returns the position of the number that you are trying to find. If the number is not found, the search function must return -1.

   Function prototype: int linear_search(int *arr, int size, int number);

2. Create a binary_search function that returns the position of the number that you are trying to find. If the number is not found, the search function must return -1.

   Function prototype: int binary_search(int *arr, int size, int number);

3. (Skip for now. Come back to this when you have a sorting algorithm that sorts the array in ascending order.) If your linear_search returned a valid index value and your binary_search returned -1, sort the array in ascending order and search the array for the number using both linear_search and binary_search again. The indices they returned must match.

---

3. Sort your array.

If option '3' is chosen, print the current array, the ascending bubble sorted array, descending bubble sorted array, ascending selection sorted array, & descending selection sorted array in this order. Your sort functions do not print anything to the screen. You have your display function for that. (See Ch. 8 for bubble and selection sort algorithms. See Gordon's bubble sort algorithm.)

1. Create a bubble sort function that sorts the array in ascending order.

   Function Prototype: void bubblesort_Asc(int *arr, int size);

2. Create a selection sort function that sorts the array in ascending order.

   Function Prototype: void selectsort_Asc(int *arr, int size);

3. Create a bubble sort function that sorts the array in descending order.

   Function Prototype: void bubblesort_Desc(int *arr, int size);

4. Create a selection sort function that sorts the array in descending order.

   Function Prototype: void selectsort_Desc(int *arr, int size);

---

4. Search & Sort Facts

If option '4' is chosen, print the correct answers to the following statements:

1. Linear Search [does | does not] require the data to be ordered.
2. Linear Search has a worst case time complextiy of [O(n) | O(n^2) | O(log n)].
3. Binary Search [does | does not] require the data to be ordered.
4. Binary Search has a worst case time complextiy of [O(n) | O(n^2) | O(log n)].
5. [Linear | Binary Search] is better than [Linear | Binary] Search when the data is not ordered.
6. [Linear | Binary Search] is better than [Linear | Binary] Search when the data is ordered.
7. The bubble sort is [efficient | inefficient] for large arrays.
8. The [bubble | selection] sort moves items by one element at a time.
9. The [bubble | selection] sort moves items immediately to their final position in the array.

Copy Code

    cout << "Search & Sort Facts:\n";
    cout << "1. Linear Search [does | does not] require the data to be ordered.\n";
    cout << "2. Linear Search has a worst case time complextiy of [O(n) | O(n^2) | O(log n)].\n";
    cout << "3. Binary Search [does | does not] require the data to be ordered.\n";
    cout << "4. Binary Search has a worst case time complextiy of [O(n) | O(n^2) | O(log n)].\n";
    cout << "5. [Linear | Binary] Search is better than [Linear | Binary] Search when the data is not ordered.\n";
    cout << "6. [Linear | Binary] Search is better than [Linear | Binary] Search when the data is ordered.\n";
    cout << "7. The Bubble Sort is [efficient | inefficient] for large arrays.\n";
    cout << "8. The [Bubble | Selection] Sort moves items by one element at a time.\n";
    cout << "9. The [Bubble | Selection] Sort moves items immediately to their final position in the array.\n";
                            
                            

 Answers 
    1. does not
    2. O(n)
    3. does
    4. O(log n)
    5. Linear, Binary
    6. Binary, Linear
    7. inefficient
    8. Bubble
    9. Selection
                        

---

5. Modify your array. (Choose 2 or More)

You will have to make a decision which search algorithm you want to use and if you need to sort the array before searching. You may write a function for each of the operations below.

Note: It is optional to create a case '9' that allows you to toggle doing a linear or a binary search for cases '5'-'8', if you wish to implement the tasks below using both searches. When option '9' is selected, your menu will update so that it says "Binary Search for 5-8" or "Linear Search for 5-8". You can do this by adding the following codes to the right parts of your program:

    //If-Else Shorthand: (condition) ? True case:False case
    cout << "9. " << ((flag) ? "Linear":"Binary") <<" Search for 5-8\n"; //flag's default value is set to True

    //Toggle
    case '9':
        flag = !flag; //Makes False to True & True to False when '9' is selected
        break;
                        

Replace

If option '5' is selected, display the current array, ask the user what number they want to replace and what number to replace it with, and display the new array. The number they want to replace must exist in the array. Also, the number they want to enter in the array must be unique.

Swap

If option '6' is selected, display the current array, ask the user for two numbers to swap, and display the new array. The numbers they entered must exist in the array. The numbers they entered can't be the same.

Insert & Shift

If option '7' is selected, display the current array, ask the user for a number to be inserted and the index where it will be placed, and display the new array. The number inserted must be unique. The index entered must be a valid index. Starting from the index the user entered, the elements in the array must shift 1 index position more than their previous index. There won't be room for a 26th number in the array, so the element that used to be in index 24 will be gone.

Delete & Shift

If option '8' is selected, display the current array, ask the user for a number to be deleted, and display the new array. The number to be deleted must exist. Starting from the index of the deleted number, the elements in the array must shift 1 index position less than their previous index. There will be room for a new 25th number, so you must generate a new element in index 24. This new number must be unique.

---

6. Ascending Even & Descending Odd

If option 'a' is chosen, display the current array and display the newly arranged array. You must first separate the evens and the odds of the array. Then, you must arrange the evens in ascending order and the odds in descending order. Finally, put them back into a single array, with the ascending evens in the front and the descending odds in the back. (You may create a function for this or you can do it in your main() function.)

Try it on your own before you take a peek at a possible solution below.

 Possible Psuedocode for Ascending Even & Descending Odd 

    void even_odd(int *arr, int size) {
        //Create int array even[size], int array odd[size]
        //Set even_idx to 0, odd_idx to 0, tmp_idx to 0
        //FOR each idx of arr
            //Compute remainder as arr[idx] mod 2
            //IF 'remainder' is 0
                //Set even[even_idx] to arr[idx]
                //INCREMENT even_idx
            //ELSE
                //Set odd[odd_idx] to arr[idx]
                //INCREMENT odd_idx
            //END IF
        //END FOR
        //CALL bubblesort_asc with even, even_idx
        //CALL bubblesort_desc with odd, odd_idx 
        //FOR each idx of even
            //Set arr[tmp_idx] to even[idx]
            //INCREMENT tmp_idx
        //END FOR
        //FOR each idx of odd
            //Set arr[tmp_idx] to odd[idx]
            //INCREMENT tmp_idx
        //END FOR
    }