1
CSC331- Data Structure & Algorithms
Lahore Garrison University
Lec17+18 Fall 2020
Instructor: Sahar Moin
NLogN Algorithms
• Divide and Conquer
• Merge Sort
• Quick Sort
• Heap Sort
Divide and Conquer
What if we split the list into two parts?
10 12 8 4 2 11 7 5
Divide and Conquer
Sort the two parts:
10
4 12
8 10
8 12
4 2 11
5 7 11
5
Divide and Conquer
Then merge the two parts together:
24 48 10
5 12
7 82 10
5 11
7 12
11
Merge Sort
• Merge sort is a divide and conquer algorithm that was invented by John von
Neumann in 1945.
• A detailed description and analysis of bottom-up merge sort appeared in a
report by Goldstine and von Neumann as early as 1948.
• Merge Sort is a Divide and Conquer algorithm. It divides the input array into
two halves, calls itself for the two halves, and then merges the two sorted
halves
• Time Complexity: O(nlog(n))
6 Lahore Garrison University
How Merge Sort Works?
Merge Sort
• Merge sort keeps on dividing the list into equal halves until it can
no more be divided.
• By definition, if it is only one element in the list, it is sorted. Then,
merge sort combines the smaller sorted lists keeping the new list
sorted too.
12
Lahore Garrison University
3 Phases (4 major steps) in the Merge Sort Algorithm
Division Phase – Divide the array(list) into 2 halves by finding the
midpoint of the array(list).
• Midpoint (m) = (left + right)/ 2
• Here left is the starting index & right is the last index of the
array(list)
Recursion Phase –
• Call Merge Sort on the left sub-array (sub-list)
• Call Merge Sort on the right sub-array (sub-list)
Merge Phase –
• Call merge function to merge the divided sub-arrays back to the
original array.
• Perform sorting of these smaller sub arrays before merging them
back
Algorithm
• Declare left and right var which will mark the
extreme indices of the array
• Left will be assigned to 0 and right will be
assigned to n-1
• Find mid = (left+right)/2
• Call mergeSort on (left,mid) and (mid+1,rear)
• Above will continue till left<right
• Then we will call merge on the 2 subproblems
Pseudo Code
15
Lahore Garrison University
Merge Sort
Merge Sort
implementation
Lahore Garrison University
17
int main()
{
cout << "Enter size of array: " << endl;
int size;
cin >> size;
int myarray[size];
cout << "Enter " << size << " integers in any order: " << endl;
for (int i = 0; i < size; i++) {
cin >> myarray[i];}
cout << "Before Sorting" << endl;
for (int i = 0; i < size; i++) {
cout << myarray[i] << " “; }
cout << endl;
mergeSort(myarray, 0, (size - 1), size); // mergesort(arr,left,right) called
cout << "After Sorting" << endl;
for (int i = 0; i < size; i++) {
cout << myarray[i] << " ";
}
return 0;}
#include <iostream> /* Copy the remaining elements of first half, if there are any */
using namespace std;
while (i <= m) {
void merge(int arr[], int l, int m, int r, int size)
temp[k] = arr[i];
{
i++;
int i = l;
k++;
int j = m + 1;
}
int k = l; /* Copy the remaining elements of second half, if there are any
/* create temp array */ */
int temp[size]; while (j <= r) {
while (i <= m && j <= r) { temp[k] = arr[j];
if (arr[i] <= arr[j]) { j++;
temp[k] = arr[i]; k++;
i++; }
k++; }
/* Copy the temp array to original array */
else {
for (int p = l; p <= r; p++) {
temp[k] = arr[j];
arr[p] = temp[p];
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, int size)
{
if (l < r) {
// find midpoint
int m = (l + r) / 2;
// recurcive mergesort first and second halves
mergeSort(arr, l, m, size);
mergeSort(arr, m + 1, r, size);
// merge
merge(arr, l, m, r, size);
}}
C++ Program to Implement Merge
Sort(with fixed size of array)
Representation:
void merge(int arr[], int l, int m, int r) { /* Copy the remaining elements of first
int i = l; half, if there are any */
int j = m + 1;
while (i <= m) {
int k = l;
/* create temp array */ temp[k] = arr[i];
int temp[5]; i++;
while (i <= m && j <= r) { k++; }
if (arr[i] <= arr[j]) { /* Copy the remaining elements of
temp[k] = arr[i]; second half, if there are any */
i++;
while (j <= r) {
k++;
} temp[k] = arr[j];
else { j++;
temp[k] = arr[j]; k++;
j++; }
k++;}}
/* Copy the temp array to original array */
for (int p = l; p <= r; p++) {
arr[p] = temp[p];
}}
/* 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) {
// find midpoint
int m = (l + r) / 2;
// recurcive mergesort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// merge
merge(arr, l, m, r);}}
int main() {
int myarray[5];
//int arr_size = cout << endl;
sizeof(myarray)/sizeof(myarray[0]); mergeSort(myarray, 0, (arr_size - 1));
int arr_size = 5; // mergesort(arr,left,right) called
cout << "Enter 5 integers in any order: " << cout << "After Sorting" << endl;
endl; for (int i = 0; i < 5; i++) {
for (int i = 0; i < 5; i++) { cout << myarray[i] << " ";
cin >> myarray[i]; }
} return 0;
cout << "Before Sorting" << endl; }
for (int i = 0; i < 5; i++) {
cout << myarray[i] << " ";}
Quick sort
Quick Sort
• Quick Sort Algorithm is a Divide & Conquer algorithm.
• It divides input array in two partitions, calls itself for the two
partitions(recursively) and performs in-place sorting while doing so.
• A separate partition() function is used for performing this in-place sorting at
every iteration.
• Quick sort is one of the most efficient sorting algorithms.
• >> Time Complexity: θ(nlog(n))
• >> Space Complexity: O(log(n))
Quick Sort Working
10 80 30 90 40 50 70
Quick Sort
Quick Sort (Working )
• There are 2 Phases (3 major steps) in the Quick
Sort Algorithm –
• Division Phase – Divide the array(list) into 2
halves by finding the pivot point to perform the
partition of the array(list).
• The in-place sorting happens in this partition
process itself.
• Recursion Phase –
• Call Quick Sort on the left partition (sub-list)
• Call Quick Sort on the right partition (sub-list)
Quick Sort Algorithm(Pseudo Code)
Quick Sort Partition Function
(Pseudo Code)
int main()
{int size=0;
cout<<"Enter Size of array: "<<endl;
cin>>size;
int myarray[size]; QuickSort(myarray,0,(size-1)); // quick sort
cout<<"Enter "<<size<<" integers in any cout<<"After Sorting"<<endl;
order: "<<endl; for(int i=0;i<size;i++)
for(int i=0;i<size;i++) {
{ cout<<myarray[i]<<" ";
cin>>myarray[i]; }
}
cout<<"Before Sorting"<<endl; return 0;
}
for(int i=0;i<size;i++)
{
cout<<myarray[i]<<" ";
}
cout<<endl;
Quick Sort
# include <iostream>
using namespace std;
// quick sort sorting algorithm
int Partition(int arr[], int s, int e)
{ int temp = arr[e];
int pivot = arr[e]; arr[e] = arr[pIndex];
int pIndex = s;
arr[pIndex] = temp;
for(int i = s;i<e;i++) return pIndex;}
{
if(arr[i]<pivot)
{
int temp = arr[i];
arr[i] = arr[pIndex];
arr[pIndex] = temp;
pIndex++;} }
void QuickSort(int arr[], int s, int e)
{
if(s<e)
{
int p = Partition(arr,s, e);
QuickSort(arr, s, (p-1)); // recursive QS call for left partition
QuickSort(arr, (p+1), e); // recursive QS call for right partition
}
}