Scribd Logo
Upload

Welcome to Scribd!

  • 5 views

    MDSA Lab Task 10

    Uploaded by

    3916-MUZAMMIL AHMED

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    MDSA Lab Task 10

    Uploaded by

    3916-MUZAMMIL AHMED
    5 views5 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    5 views5 pages

    MDSA Lab Task 10

    Uploaded by

    3916-MUZAMMIL AHMED

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 5

    Lab Task 10

    Data Structures & Algorithms


    By

    Syed Muzammil Ahmed


    (3014-2022)
    Program: BSCS - 4B

    Course/Lab Instructor
    Sir Maaz.

    Faculty of Engineering Sciences and Technology


    Hamdard University, Karachi, Pakistan

    LAB TASK 10
    Task 1:

    Quick Sort :

    #include <iostream>

    using namespace std;

    // Function to swap two elements


    void swap(int* a, int* b) {
    int t = *a; *a = *b;
    *b = t;
    }

    // Partition function int partition(int arr[],


    int low, int high) { int pivot =
    arr[high]; // Pivot element
    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);
    }

    // QuickSort function
    void quickSort(int arr[], int low, int high) {
    if (low < high) { // Partitioning index
    int pi = partition(arr, low, high);

    // Recursively sort elements before and after partition


    quickSort(arr, low, pi - 1); quickSort(arr, pi + 1,
    high);
    }
    }

    // Function to print an array void


    printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
    }
    cout << endl;
    }

    int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    1
    cout << "Unsorted array: ";
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";


    printArray(arr, n);
    return 0;
    }

    Output:

    2
    Task 2:

    Merge Sort:

    #include <iostream>

    using namespace std;

    // Function to merge two subarrays of arr[] void


    merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; int n2 = right - mid;

    // Create temporary arrays


    int* leftArray = new int[n1];
    int* rightArray = new int[n2];

    // Copy data to temporary arrays leftArray[] and rightArray[]


    for (int i = 0; i < n1; i++) leftArray[i] = arr[left + i];
    for (int j = 0; j < n2; j++) rightArray[j] = arr[mid + 1 +
    j];

    // Merge the temporary arrays back into arr[left..right]


    int i = 0, j = 0, k = left; while (i < n1 && j < n2) {
    if (leftArray[i] <= rightArray[j]) {
    arr[k] = leftArray[i]; i++;
    } else {
    arr[k] = rightArray[j];
    j++; } k++;
    }

    // Copy the remaining elements of leftArray[], if there are any


    while (i < n1) { arr[k] = leftArray[i]; i++;
    k++;
    }

    // Copy the remaining elements of rightArray[], if there are any


    while (j < n2) { arr[k] = rightArray[j]; j++;
    k++;
    }

    // Clean up
    delete[] leftArray;
    delete[] rightArray;
    }

    // Function to implement merge sort void


    mergeSort(int arr[], int left, int right) {
    if (left < right) { // Find the middle
    point int mid = left + (right - left) /
    2;

    // Recursively sort first and second halves


    mergeSort(arr, left, mid); mergeSort(arr,
    mid + 1, right);
    3
    // Merge the sorted halves
    merge(arr, left, mid, right);
    }
    }

    // Function to print an array void


    printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
    } cout <<
    endl;
    } int
    main() {
    int arr[] = {12, 11, 13, 5, 6, 7}; int
    arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << "Unsorted array: ";
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);


    cout << "Sorted array: ";
    printArray(arr, arr_size);
    return 0;}
    Output:

    You might also like