Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 6
DATE EX.
NO: 3: Implementation of Merge Sort and
Quick Sort
3A. Merge Sort
AIM: To write a program to implement merge sort.
ALGORITHM:
1. If the list has only one element, return the list and terminate.
2. Split the list into two halves that are as equal in length as possible
3. Using recursion, sort both lists using merge sort.
4. Merge the two sorted lists and return the result.
5. Stop the program.
PROGRAM :
#include<iostream> using namespace std; void swapping(int &a, int &b) { //swap the content of a and b int temp; temp = a; a = b; b = temp; } void display(int *array, int size) { for(int i = 0; i<size; i++) cout << array[i] << " "; cout << endl; } void merge(int *array, int l, int m, int r) { int i, j, k, nl, nr; //size of left and right sub-arrays nl = m-l+1; nr = r-m; int larr[nl], rarr[nr]; //fill left and right sub-arrays for(i = 0; i<nl; i++) larr[i] = array[l+i]; for(j = 0; j<nr; j++) rarr[j] = array[m+1+j]; i = 0; j = 0; k = l; //marge temp arrays to real array while(i < nl && j<nr) { if(larr[i] <= rarr[j]) { array[k] = larr[i]; i++; } else { array[k] = rarr[j]; j++; } k++; } while(i<nl) { //extra element in left array array[k] = larr[i]; i++; k++; } while(j<nr) { //extra element in right array array[k] = rarr[j]; j++; k++; } } void mergeSort(int *array, int l, int r) { int m; if(l < r) { int m = l+(r-l)/2; // Sort first and second arrays mergeSort(array, l, m); mergeSort(array, m+1, r); merge(array, l, m, r); } } int main() { int n; cout << "Enter the number of elements: "; cin >> n; int arr[n]; //create an array with given number of elements cout << "Enter elements:" << endl; for(int i = 0; i<n; i++) { cin >> arr[i]; } cout << "Array before Sorting: "; display(arr, n); mergeSort(arr, 0, n-1); //(n-1) forlast index cout << "Array after Sorting: "; display(arr, n); }
OUTPUT :
Enter the number of elements: 5
Enter elements: 9 4 1 7 8 Array before Sorting: 9 4 1 7 8 Array after Sorting: 1 4 7 8 9 3B. Quick Sort
AIM:
To write a program to implement quick sort.
ALGORTIHM:
1. Choose an element, called pivot, from the list. Generally pivot can be the middle
index element 2. Reorder the list so that all elements with values less than the pivot come before the
pivot
3. All elements with values greater than the pivot come after it (equal values can go
either way).
a. After this partitioning, the pivot is in its final position. This is called the partition operation. 4. Recursively apply the above steps to the sub-list of elements with smaller values
and separately the sub-list of elements with greater values.
5. Stop the Program. PROGRAM :
#include <iostream> using namespace std; void quick_sort(int[],int,int); int partition(int[],int,int); int main() { int a[50],n,i; cout<<"How many elements?"; cin>>n; cout<<"\nEnter array elements:"; for(i=0;i<n;i++) cin>>a[i]; quick_sort(a,0,n-1); cout<<"\nArray aftersorting:"; for(i=0;i<n;i++) cout<<a[i]<<" "; return 0; }
void quick_sort(int a[],int l,int u)
{ int j; if(l<u) { j=partition(a,l,u); quick_sort(a,l,j-1); quick_sort(a,j+1,u); } }
int partition(int a[],int l,int u)
{ int v,i,j,temp; v=a[l]; i=l; j=u+1; do { do i++; while(a[i]<v&&i<=u); do j--; while(v<a[j]); if(i<j) { temp=a[i]; a[i]=a[j]; a[j]=temp; } }while(i<j); a[l]=a[j]; a[j]=v; return(j); }
OUTPUT : How many elements?7 Enter array elements:3 7 1 9 5 4 2 Array after sorting:1 2 3 4 5 7 9
RESULT: Thus the C++ program to Implementation of Merge Sort and Quick Sort was written, executed and verified successfully.
