Module 04
Partha Pratim
Das Module 04: Programming in C++
Objectives & Sorting and Searching
Outline
Sorting
Bubble Sort
Standard Library
Searching
Partha Pratim Das
Standard Library
STL: Department of Computer Science and Engineering
algorithm Indian Institute of Technology, Kharagpur
Summary
[email protected] Tanwi Mallick
Srijoni Majumdar
Himadri B G S Bhuyan
NPTEL MOOCs Programming in C++ Partha Pratim Das 1
Module Objectives
Module 04
Partha Pratim Implementation of Sorting and Searching in C and C++
Das
Objectives &
Outline
Sorting
Bubble Sort
Standard Library
Searching
Standard Library
STL:
algorithm
Summary
NPTEL MOOCs Programming in C++ Partha Pratim Das 2
Module Outline
Module 04
Partha Pratim Sorting in C and C++
Das
Bubble Sort
Objectives & Using Standard Library
Outline
Searching in C and C++
Sorting
Bubble Sort Using Standard Library
Standard Library
Searching algorithm Library
Standard Library
STL:
algorithm
Summary
NPTEL MOOCs Programming in C++ Partha Pratim Das 3
Program 04.01: Bubble Sort
Module 04 C Program C++ Program
Partha Pratim // FileName:Bubble_Sort.c: // FileName:Bubble_Sort.cpp:
Das #include <stdio.h> #include <iostream>
using namespace std;
int main() { int main() {
Objectives & int data[] = {32, 71, 12, 45, 26}; int data[] = {32, 71, 12, 45, 26};
Outline int i, step, n = 5, temp; int n = 5, temp;
Sorting
for(step = 0; step < n - 1; ++step) for(int step = 0; step < n - 1; ++step)
Bubble Sort
for(i = 0; i < n-step-1; ++i) { for(int i = 0;i < n-step-1; ++i) {
Standard Library
if(data[i] > data[i+1]) { if (data[i] > data[i+1]) {
Searching temp = data[i]; temp = data[i];
Standard Library data[i] = data[i+1]; data[i] = data[i+1];
data[i+1] = temp; data[i+1] = temp;
STL: } }
algorithm } }
Summary for(i = 0; i < n; ++i) for(int i = 0; i < n; ++i)
printf("%d ", data[i]); cout << data[i] << " ";
return 0; return 0;
} }
12 26 32 45 71 12 26 32 45 71
• Implementation is same in both C and C++ apart from the changes in basic header files, I/O functions
explained in Module 02.
NPTEL MOOCs Programming in C++ Partha Pratim Das 4
Program 04.02: Using sort from standard library
Module 04 C Program (Desc order) C++ Program (Desc order)
Partha Pratim // FileName:qsort.c: // FileName:Algorithm_Cust_c++.cpp:
Das #include <stdio.h> #include <iostream>
#include <stdlib.h> #include <algorithm>
using namespace std;
Objectives &
Outline // compare Function Pointer // compare Function Pointer
int compare(const void *a, const void *b) { bool compare (int i, int j) {
Sorting
return (*(int*)a < *(int*)b); return (i > j);
Bubble Sort
} }
Standard Library
Searching int main () { int main() {
Standard Library int data[] = {32, 71, 12, 45, 26}; int data[] = {32, 71, 12, 45, 26};
STL: // Start ptr, # elements, size, func. ptr // Start ptr, end ptr, func. ptr
algorithm qsort(data, 5, sizeof(int), compare); sort (data, data+5, compare);
Summary for(int i = 0; i < 5; i++) for (int i = 0; i < 5; i++)
printf ("%d ", data[i]); cout << data[i] << " ";
return 0; return 0;
} }
71 45 32 26 12 71 45 32 26 12
• sizeof int, array passed in qsort • Size need not be passed.
NPTEL MOOCs Programming in C++ Partha Pratim Das 5
Program 04.03: Using default sort of algorithm
Module 04 C++ Program
Partha Pratim // FileName:Algorithm_Cust_c++.cpp:
Das #include <iostream>
#include <algorithm>
using namespace std;
Objectives &
Outline int main () {
int data[] = {32, 71, 12, 45, 26};
Sorting
Bubble Sort
sort (data, data+5);
Standard Library
Searching for (int i = 0; i < 5; i++)
Standard Library cout << data[i] << " ";
STL: return 0;
algorithm }
Summary 12 26 32 45 71
• Sort using the default sort function of algorithm library which does the sorting in ascending order only.
NPTEL MOOCs Programming in C++ Partha Pratim Das 6
Program 04.04: Binary Search
Module 04 C Program C++ Program
Partha Pratim // FileName:Binary_Search.c: // FileName:Binary_Search_c++.cpp:
Das #include <stdio.h> #include <iostream>
#include <stdlib.h> #include <algorithm>
using namespace std;
Objectives &
Outline // compare Function Pointer
int compare (const void * a, const void * b) {
Sorting
if ( *(int*)a < *(int*)b ) return -1;
Bubble Sort
if ( *(int*)a == *(int*)b ) return 0;
Standard Library
if ( *(int*)a > *(int*)b ) return 1;
Searching }
Standard Library
int main () { int main() {
STL: int data[] = {1, 2, 3, 4, 5}; int data[] = {1, 2, 3, 4, 5};
algorithm int key = 3; int key = 3;
Summary if (bsearch (&key, data, 5, if (binary_search (data, data+5, key))
sizeof(int), compare))
cout << "found!\n"; cout << "found!\n";
else else
cout << "not found.\n"; cout << "not found.\n";
return 0; return 0;
} }
found! found!
NPTEL MOOCs Programming in C++ Partha Pratim Das 7
The algorithm Library
Module 04
The algorithm library of c++ helps us to easily implement
Partha Pratim
Das commonly used complex functions. We discussed the functions
Objectives &
for sort and search. Let us look at some more useful functions.
Outline
Replace element in an array
Sorting
Bubble Sort
Standard Library
Rotates the order of the elements
Searching
Standard Library
STL:
algorithm
Summary
NPTEL MOOCs Programming in C++ Partha Pratim Das 8
Program 04.05: replace and rotate functions
Module 04 Replace Rotate
Partha Pratim // FileName:Replace.cpp: // FileName:Rotate.cpp:
Das #include <iostream> #include <iostream>
#include <algorithm> #include <algorithm>
using namespace std; using namespace std;
Objectives &
Outline int main() { int main() {
int data[] = {1, 2, 3, 4, 5}; int data[] = {1, 2, 3, 4, 5};
Sorting
Bubble Sort
replace (data, data+5, 3, 2); rotate (data, data+2, data+5);
Standard Library
Searching for(int i = 0; i < 5; ++i) for(int i = 0; i < 5; ++i)
Standard Library cout << data[i] << " "; cout << data[i] <<" ";
STL: return 0; return 0;
algorithm } }
Summary
1 2 2 4 5 3 4 5 1 2
• 3rd element replaced with 2 • Array circular shifted around 3rd element.
NPTEL MOOCs Programming in C++ Partha Pratim Das 9
Module Summary
Module 04
Partha Pratim Flexibility of defining customised sort algorithms to be
Das
passed as parameter to sort and search functions defined
Objectives &
Outline
in the algorithm library.
Sorting Predefined optimised versions of these sort and search
Bubble Sort
Standard Library functions can also be used.
Searching
Standard Library
There are a number of useful functions like rotate, replace,
STL: merge, swap, remove etc in algorithm library.
algorithm
Summary
NPTEL MOOCs Programming in C++ Partha Pratim Das 10
Instructor and TAs
Module 04
Partha Pratim
Das Name Mail Mobile
Objectives &
Partha Pratim Das, Instructor [email protected] 9830030880
Outline Tanwi Mallick, TA [email protected] 9674277774
Sorting
Srijoni Majumdar, TA [email protected] 9674474267
Bubble Sort Himadri B G S Bhuyan, TA [email protected] 9438911655
Standard Library
Searching
Standard Library
STL:
algorithm
Summary
NPTEL MOOCs Programming in C++ Partha Pratim Das 11
