//1selection sort algorithm {
#include<iostream> if(x[j] > large){
using namespace std; large = x[j];
class SelectionSort{ indx = j;
public: }
int no_of_elements; }
int elements[10]; x[indx] = x[i];
public: x[i] = large;
void getarray(); }
void sortit(int [], int); }
void display(); void SelectionSort::display(){
}; cout<<"The sorted array is :\n";
void SelectionSort::getarray(){ for(int i = 0 ; i < no_of_elements; i++){
cout<<"How many elements? "; cout<<elements[i]<<" ";
cin>>no_of_elements; }
cout<<"Insert array of element to sort: "; cout<<endl;
for(int i=0;i<no_of_elements;i++){ }
cin>>elements[i]; int main(){
}} SelectionSort SS;
void SelectionSort::sortit(int x[], int n){ SS.getarray();
int i, indx, j, large; SS.sortit(SS.elements,SS.no_of_elements);
for(i = n - 1; i > 0; i--){ SS.display();
large = x[0]; system("pause");
indx = 0; return 0;
for(j = 1; j <= i; j++) }
Data structure and Algorithm practical
1
//3 binary searching int iteration = 0, left = 0, right =
my_numbers.size()-1, mid;
#include <iostream>
while (left <= right) {
#include <vector>
iteration++;
using namespace std;
mid = (int) ((left + right) / 2);
void Binary_Search(const vector<int>
&numbers, int value); if (key == my_numbers[mid]) {
int main() { cout << "Binary search found "
<< my_numbers[mid] << " after " << iteration <<
vector <int>my_numbers; " iterations.\n";
for (int i=0; i<4000000; i++)
iteration++;
my_numbers.push_back(i);
return;
cout << "Size of vector my_nymbers :" <<
my_numbers.size() << endl; }
Binary_Search(my_numbers, 2); else if (key > my_numbers[mid])
Binary_Search(my_numbers, 23); left = mid + 1;
Binary_Search(my_numbers, 234); else
Binary_Search(my_numbers, 7655); right = mid - 1;
Binary_Search(my_numbers, 10101); }
Binary_Search(my_numbers, 895543); cout << "Binary search did not found " <<
my_numbers[mid] << " after " << iteration << "
Binary_Search(my_numbers, 3785111); iterations.\n";
system("pause"); return;
return 0; }
}
void Binary_Search(const vector< int>
&my_numbers, int key) {
//2. search algorithm example
Data structure and Algorithm practical
2
#include <iostream> // std::cout int indicator[] = {20,30,50};
#include <algorithm> // std::search it = std::search (haystack.begin(),
haystack.end(), indicator, indicator+3,
#include <vector> // std::vector mypredicate);
bool mypredicate (int i, int j) {
return (i==j); if (it!=haystack.end())
} std::cout << "indicator found at position " <<
(it-haystack.begin()) << '\n';
int main () { else
std::vector<int> haystack; std::cout << "indicator not found\n";
system("pause");
// set some values: haystack: 10 20 30 40 return 0;
50 60 70 80 90 }
for (int i=1; i<10; i++) //4 sequencial searching
haystack.push_back(i*10);
#include<iostream>
// using default comparison:
int pointer[] = {40,50,60,70};
using namespace std;
std::vector<int>::iterator it;
it = std::search (haystack.begin(),
haystack.end(), pointer, pointer+4); int main(){
if (it!=haystack.end()) int arr[10];
std::cout << "pointer found at position " <<
(it-haystack.begin()) << '\n';
int no_of_elements, key;
else
std::cout << "pointer not found\n";
bool found = false;
// using predicate comparison:
cout<<"Enter the number of element: ";
Data structure and Algorithm practical
3
}
cin>>no_of_elements;
if(!found){
for(int i = 0; i < no_of_elements; i++){
cout<<"Key not found!";
cout<<"arr["<<i<<"]: ";
cin>>arr[i]; system("pause");
return 0;
cout<<"Enter the value to search: ";
cin>>key;
for(int i=0;i<no_of_elements;i++){
if(key == arr[i]){
found = true;
cout<<"The value is found at index
arr["<<i<<"]\n";
Data structure and Algorithm practical
4
//Assignment ???
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void swap(std::vector<int> & data, int i, int j)
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
void print(std::vector<int> const & data)
std::vector<int>::const_iterator iter =
data.begin();
Data structure and Algorithm practical
5
for (; iter != data.end(); ++iter) {
{ srand(low);
cout << *iter << " "; int gen = 0;
} gen = rand() % (high - low + 1) + low;
return gen;
if (data.size() > 0) }
cout << endl; //useful for small lists, and for large lists where
data is
}
//already sorted
}
void BubbleSort(std::vector<int> & data)
{
int generateRandom(int low, int high);
int length = data.size();
void Shuffle(std::vector<int> & data)
{
for (int i = 0; i < length; ++i)
int length = data.size();
{
bool swapped = false;
for (int i = 0; i < length-1; ++i)
for (int j = 0; j < length - (i+1); ++j)
{
{
swap(data, i, generateRandom(i+1, length-
1)); if (data[j] > data[j+1])
} {
swap(data, j, j+1);
print(data); swapped = true;
} }
int generateRandom(int low, int high)
Data structure and Algorithm practical
6
if (!swapped) break; }
} }
//useful for small and mostly sorted lists
//useful for small lists and where swapping is //expensive to move array elements
expensive
void InsertionSort(std::vector<int> & data)
// does at most n swaps
{
void SelectionSort(std::vector<int> & data)
int length = data.size();
{
int length = data.size();
for (int i = 1; i < length; ++i)
{
for (int i = 0; i < length; ++i)
bool inplace = true;
{
int j = 0;
int min = i;
for (; j < i; ++j)
for (int j = i+1; j < length; ++j)
{
{
if (data[i] < data[j])
if (data[j] < data[min])
{
{
inplace = false;
min = j;
break;
}
}
}
}
if (min != i)
if (!inplace)
{
{
swap(data, i, min);
int save = data[i];
}
Data structure and Algorithm practical
7
for (int k = i; k > j; --k) }
data[k] = data[k-1]; void Merge(std::vector<int> & data, int lowl, int
highl, int lowr, int highr)
}
{
data[j] = save;
int tmp_low = lowl;
}
std::vector<int> tmp;
}
}
while (lowl <= highl && lowr <= highr)
{
void Merge(std::vector<int> & data, int lowl, int
highl, int lowr, int highr); if (data[lowl] < data[lowr])
void MergeSort(std::vector<int> & data, int low, {
int high)
tmp.push_back(data[lowl++]);
{
}
if (low >= high)
else if (data[lowr] < data[lowl])
{
{
return;
tmp.push_back(data[lowr++]);
}
}
else
int mid = low + (high-low)/2;
{
tmp.push_back(data[lowl++]);
MergeSort(data, low, mid);
tmp.push_back(data[lowr++]);
}
MergeSort(data, mid+1, high);
}
Merge(data, low, mid, mid+1, high);
while (lowl <= highl)
Data structure and Algorithm practical
8
{ QuickSort(data, low, p-1);
tmp.push_back(data[lowl++]); QuickSort(data, p+1, high);
} }
while (lowr <= highr) int Partition(std::vector<int> & data, int low, int
high)
{
{
tmp.push_back(data[lowr++]);
int p = low;
}
for (int i = p+1; i <= high; ++i)
{
std::vector<int>::const_iterator iter =
tmp.begin(); if (data[i] < data[p])
for(; iter != tmp.end(); ++iter) swap(data, i, p);
{ if (i != p+1)
data[tmp_low++] = *iter; {
} swap(data, i, p+1);
} }
p = p + 1;
int Partition(std::vector<int> & data, int low, int }
high);
}
void QuickSort(std::vector<int> & data, int low,
int high)
{ return p;
}
if (low >= high) return;
//O(kN) k is max number of digits
int p = Partition(data, low, high);
int findMaxDigits(std::vector<int> & data);
Data structure and Algorithm practical
9
void PutInQueues(std::queue<int> q[], int q[qpos].push(*iter);
qcount, std::vector<int> & data, int digit);
}
void GetPartialSorted(std::queue<int> q[], int
}
qcount, std::vector<int> & data);
int getDigitAt(int n, int digit)
void RadixSort(std::vector<int> & data)
{ {
int dig = 0;
std::queue<int> q[10];
int maxDigits = findMaxDigits(data); while (digit--)
for (int i = 0; i < maxDigits; ++i) dig = n % 10;
n = n / 10;
{
PutInQueues(q, 10, data, i+1); }
return dig;
data.clear();
GetPartialSorted(q, 10, data); }
} void GetPartialSorted(std::queue<int> q[], int
qcount, std::vector<int> & data)
{
int getDigitAt(int n, int digit);
for (int i = 0; i < qcount; ++i)
void PutInQueues(std::queue<int> q[], int
qcount, std::vector<int> & data, int digit) {
if (q[i].size() > 0)
{
std::vector<int>::const_iterator iter = {
data.begin(); int length = q[i].size();
for(; iter != data.end(); ++iter) while (length--)
{ {
int qpos = getDigitAt(*iter, digit); data.push_back(q[i].front());
Data structure and Algorithm practical
10
q[i].pop(); int count = 0;
} while(n != 0)
} {
} n = n/10;
} ++count;
int numDigits(int n);
int findMaxDigits(std::vector<int> & data) return count;
{ }
std::vector<int>::const_iterator iter =
data.begin();
int main()
int max = 0;
{
for (; iter != data.end(); ++iter)
int a[] = {5, 6, 1, 2, 0, 8, -1, -2, 8, 0};
{
std::vector<int> data(a, a +
int numd = numDigits(*iter); sizeof(a)/sizeof(int));
if (max < numd)
{ //Bubble sort
max = numd; BubbleSort(data);
} print(data);
//Selection sort
return max; Shuffle(data);
} SelectionSort(data);
print(data);
int numDigits(int n)
{ //Insertion sort
Data structure and Algorithm practical
11
Shuffle(data);
InsertionSort(data);
print(data);
//Merge sort
Shuffle(data);
MergeSort(data, 0, data.size()-1);
print(data);
//Quick sort
Shuffle(data);
QuickSort(data, 0, data.size()-1);
print(data);
//Radix Sort
int b[] = {123, 6, 24, 4567, 45, 989834, 98, 23,
8, 0};
std::vector<int> rdata(b, b +
sizeof(b)/sizeof(int));
RadixSort(rdata);
print(rdata);
system("pause");
return 0;
Data structure and Algorithm practical
12
