Scribd
Upload
19 views5 pages

MDSA Lab Task 10

Uploaded by

3916-MUZAMMIL AHMED
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views5 pages

MDSA Lab Task 10

Uploaded by

3916-MUZAMMIL AHMED
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 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