[go: up one dir, main page]

0% found this document useful (0 votes)
7 views10 pages

Experiment No 2

The document contains two C programs that implement the Quick Sort and Merge Sort algorithms. The Quick Sort program sorts an array of integers by partitioning it based on a pivot, while the Merge Sort program recursively divides the array into halves and merges them back in sorted order. Both programs include examples of original and sorted arrays as output.

Uploaded by

Yashvi Bari
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
0% found this document useful (0 votes)
7 views10 pages

Experiment No 2

The document contains two C programs that implement the Quick Sort and Merge Sort algorithms. The Quick Sort program sorts an array of integers by partitioning it based on a pivot, while the Merge Sort program recursively divides the array into halves and merges them back in sorted order. Both programs include examples of original and sorted arrays as output.

Uploaded by

Yashvi Bari
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/ 10

Experiment No 2

Aim: Program to implement Quick Sort and Merge Sort


Lab Outcome: LO1,LO2,LO3
Program :
/* Program to perform quick sort */
// C program to implement Quick
Sort Algorithm
#include <stdio.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function
implementation
int partition(int arr[], int low,
int high) {
// initialize pivot to be the first
element
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
// condition 1: find the first
element greater
than
// the pivot (from starting)
while (arr[i] <= pivot && i <= high
- 1) {

i++;
}
// condition 2: find the first
element smaller
than
// the pivot (from last)
while (arr[j] > pivot && j >= low +
1) {
j--;
}
if (i < j) {
swap(&arr[i], &arr[j]);
}
}
swap(&arr[low], &arr[j]);
return j;
}
void quickSort(int arr[], int low,
int high) {
if (low < high) {
// call Partition function to find
Partition
Index
int partitionIndex = partition(arr,
low, high);
// Recursively call quickSort() for
left and
right
// half based on partition Index
quickSort(arr, low, partitionIndex
- 1);
quickSort(arr, partitionIndex + 1,
high);
}
}
int main() {
int arr[] = { 19, 7, 15, 12, 16,
18, 4, 11, 13 };
int n = sizeof(arr) /
sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);

}
// calling quickSort() to sort the
given array
quickSort(arr, 0, n - 1);
printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output:

Original array: 19 7 15 12 16 18 4
11 13
Sorted array: 4 7 11 12 13 15 16 18
19
/* Program to perform merge sort */
#include <stdio.h>

// Function to merge two


halves of an array
void merge(int arr[], int
left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;

// Create temporary
arrays
int leftArr[n1],
rightArr[n2];

// Copy data to
temporary arrays leftArr[]
and rightArr[]
for (i = 0; i < n1; i++)
leftArr[i] =
arr[left + i];
for (j = 0; j < n2; j++)
rightArr[j] =
arr[mid + 1 + j];

// Merge the temp arrays


back into arr[left...right]
i = 0; // Initial index
of first subarray
j = 0; // Initial index
of second subarray
k = left; // Initial
index of merged subarray

while (i < n1 && j < n2)


{
if (leftArr[i] <=
rightArr[j]) {
arr[k] =
leftArr[i];
i++;
} else {
arr[k] =
rightArr[j];
j++;
}
k++;
}

// Copy the remaining


elements of leftArr[], if
any
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}

// Copy the remaining


elements of rightArr[], if
any
while (j < n2) {
arr[k] =
rightArr[j];
j++;
k++;
}
}

// Function to implement
Merge Sort
void mergeSort(int arr[],
int left, int right) {
if (left < right) {
int mid = left +
(right - left) / 2; //
Avoids overflow for large
values

// Recursively sort
the first and second halves
mergeSort(arr, left,
mid);
mergeSort(arr, mid +
1, right);

// 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++)
printf("%d ",
arr[i]);
printf("\n");
}

// Main function
int main() {
int arr[] = {12, 11, 13,
5, 6, 7};
int size = sizeof(arr) /
sizeof(arr[0]);

printf("Original array:
\n");
printArray(arr, size);

mergeSort(arr, 0, size -
1);

printf("Sorted array:
\n");
printArray(arr, size);

return 0;
}

Output:
Original array:
12 11 13 5 6 7
Sorted array:
5 6 7 11 12 13

Conclusion:- Thus I had implemented program for quick sort


and merge sort

You might also like