C++ MOVIES CLAS5 You should already have an insertionsort) and binarysearch) fun

Question

C++

MOVIES CLAS5 You should already have an insertionsort) and binarysearch) function in this program (written for program 6) .Modify the add movle functions & edit movie function so that they no longer sort or search (which means duplicate movie titles will be allowed) If you do not do this then your program will take a long, long, long time to do testing. You wlill create 9 new functions, All of the following functions except for algorithmEfficlency) should be made private. ?linearSearch-This function should search for particular movie title to see if it is in the list. It should return-1 if the Movie title could not be found. Renember that Movie titles are of data type Text. Use the linear search algarithrn to implement this function. o bubbleSort This function should sort the UnkedList of Movies in ascending order by Movie title. This function will call a function calle algorithm to implement this function. d swap in the linkedList class to swap values in the linked list when necessary. Use the bubble sort o insertionSortDescending This function should be the same as insertionSort except it will sort the LinkedList of Movies in descending order by Movie title instead of ascending order o selectionsort- This function should sort the LinkedList of Movies in ascending order by Movie title. This function will call a function called swap in the linkedList class to swap values in the linked list when necessary. Use the selection sort algorithm to implement this function. o mergeSort & erge These two functions work together to implement the merge sort alporithm, which should sart the UnkedList of Movies In ascending order by Movie title. The mergesort function is a recursive function which calls the merge function. The merge function dynamically allocates a new linked list of Movie pointers to use as the merged linked list. At some polnt in the merge function you will need to replace a node...you will do this by deleting the node (deleteNode) at a particular position and then inserting a new node (insertNode function) at a particular position. o quickSort & partition These two furictions work together to inplement the quick sort algorithrn, which should sart the Unkedist of Movies in ascending order by Movie title. The quicksort function is a recursive function which calls the partition function. The partition function will use a plvot string (c-string). The partition function will call a function called s wap In the linked List class to swap values In the linked list when necessary, algorithmAnalysis- This is the "driver" function that will call all of these other functions to test the efficiency of each one. Here is the pseudocode for this function below: o 1. Start timer Call linearsearch sending a temporary Text string or not) Stop timer Print out total time for this algorithm with a c-string named "Llama" to it. don't care if It finds this 2. Start timer Call binarySearch sending a temporary Text with a c-string named Llama" to it Stop timer Print out total time for this algorithm 3. Call insertionsortDescending() to put linked list in opposite orden Start timer Call bubbleSort) Stop timer Print out total time for this algorithm 4. Call InsertionSortDescending) to put linked list In opposite order Start timer Call selectionSart) Stop timer Print out total time for this algorithm 5. Call InsertionSortDescending) to putlinked list in opposite order Start timer Call insertionSort) Stop timer Print out total time for this algorithm 6. Start timer Stop timer Print out total time for this algorithn 7. Start timer Call mergesort() sending 0 and the length of the linked list (# of nodes) minus 1 to the function Stop timer Print out total time for this algorlthm 8. Start time Call quickSortl) sending 0 and the length of the linked list (# of nodes) minus 1 to the function

Explanation / Answer

#include <algorithm>
#include <chrono>
#include <iostream>
using namespace std;
using namespace std::chrono;

int linersearch(int arr[], int n, int x)
{
    int i;
    for (i=0; i<n; i++)
        if (arr[i] == x)
         return i;
    return -1;
}
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)    

       // Last i elements are already in place
       for (j = 0; j < n-i-1; j++)
           if (arr[j] > arr[j+1])
              swap(&arr[j], &arr[j+1]);
}
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;

       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}

void selectionSort(int arr[], int n)
{
    int i, j, min_idx;

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;

        // Swap the found minimum element with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    /* create temp arrays */
    int L[n1], R[n2];

    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy the remaining elements of L[], if there
       are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);

        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
int main()
{

    int arr[] = {64, 34, 25, 12, 22, 11, 90,64, 34, 25, 12, 220, 11, 90,64, 34, 25, 120, 232, 181, 90,64, 340, 250, 127, 22, 114, 970,674, 374, 275, 172, 292, 119, 970,647, 349, 245, 152, 252, 161, 90,64, 314, 254, 12, 22, 101, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x=22;
    auto start = high_resolution_clock::now();

    // Call the function, here sort()
    linersearch(arr,n,x);

    // Get ending timepoint
    auto stop = high_resolution_clock::now();
    auto duration_liner = duration_cast<microseconds>(stop - start);
    cout << "Time taken by function linersearch: " << duration_liner.count() << " microseconds" << endl;


    start = high_resolution_clock::now();

    // Call the function, here sort()
    bubbleSort(arr,n);
    stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken by function bubbleSort: " << duration.count() << " microseconds" << endl;
    start = high_resolution_clock::now();

    // Call the function, here sort()
    insertionSort(arr,n);
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken by function insertionSort: " << duration.count() << " microseconds" << endl;
    start = high_resolution_clock::now();

    // Call the function, here sort()
    selectionSort(arr,n);
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken by function selectionSort: " << duration.count() << " microseconds" << endl;
    start = high_resolution_clock::now();

    // Call the function, here sort()
    mergeSort(arr,0,n-1);
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken by function mergeSort: " << duration.count() << " microseconds" << endl;
    start = high_resolution_clock::now();

    // Call the function, here sort()
    quickSort(arr,0,n-1);
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken by function quickSort: " << duration.count() << " microseconds" << endl;
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.