Bubble Sort using C++

Bubble sort using loop and bubble sort in link list

One of the simplest sorting methods.

The basic idea is to move required value (smallest or highest ) to the top.

Compare adjacent values (all elements)
Swap values if required
Repeat the comparisons until all the elements are in place

for i= 1 to n-1

for j= 1 to n-1

if A[j] > a[j+1] then

swap(A[j],A[j+1])

C++ Code for bubble sort using loop

#include <iostream.h>

int main()

{const int arraySize = 10; // size of array a

int a[ arraySize ] = { 2, 6, 4, 8, 10, 12, 89, 68,45,37 };

int hold;// temporary location used to swap arrayelements

cout << “Data items in original order\n”;

// output original array

for ( int i = 0; i < arraySize; i++ )

cout << a[ i ];

// bubble sort

// loop to control number of passes

for ( int pass = 0; pass < arraySize – 1; pass++ )

// loop to control number of comparisons per pass

for ( int j = 0; j < arraySize – 1; j++ )

// compare side-by-side elements and swap them if

// first element is greater than second element

if ( a[ j ] > a[ j + 1 ] ) {

hold = a[ j ];

a[ j ] = a[ j + 1 ];

a[ j + 1 ] = hold;

} // end if

cout << “\nData items in ascending order\n”;

// output sorted array

for ( int k = 0; k < arraySize; k++ )

cout << a[ k ];

cout << endl;

return 0; // indicates successful termination

} // end main

Analysis of Bubble sort

for i= 1 to n-1

for j= 1 to n-1n

if A[j] > a[j+1] then

swap(A[j],A[j+1])

(N-1) steps executed (N-1) times

(n-1)*(n-1) = O(n2)

C++ code for bubble sort in linklist

#include<iostream>
#include<conio.h>
using namespace std;
int found=1;
class node
{int num;
node*next;
public:
node()
{}
void set_num(int n){num=n;}
int get_num(){return num;}
void set_next(node*n1){next=n1;}
node *get_next(){return next;}
};
class linklist
{node*head;
public:
linklist()
{head=NULL;}

void insart(int n)
{node* nn= new node;
nn->set_num(n);
nn->set_next(head);
head=nn;}

void insart_at_tail(int data)
{
node* newNode = new node;
newNode->set_num(data);
newNode->set_next(NULL);
node *tmp = head;

if ( tmp != NULL )
{
while ( tmp->get_next() != NULL )
{tmp = tmp->get_next();}
tmp->set_next(newNode);}
else {head = newNode;}
}
void del()
{if(head==NULL)
cout<<“\n list is empty \n”;
else
{node*temp=head;
cout<<“\n the deleting element is “<<head->get_num()<<“\n”;
head=head->get_next();
delete(temp);}

}

void BubbleSort()
{
int n=0;
node *p;
p=head;
while(p!=NULL)
{n++;
p=p->get_next();
}

for( int i=1; i<=n-1 ; i++)
{
p=head;
for(int j=0 ;j<n-i ;j++)
{
if(p->get_num() > (p->get_next())->get_num())
{
int hold = p->get_num();
p->set_num( (p->get_next())->get_num());
(p->get_next())->set_num(hold);
}
p=p->get_next();
}
}

}

void display()
{if(head==NULL)
cout<<“\n list is empty \n”;
else
{node*temp =head;
while(temp!=NULL)
{cout<<temp->get_num()<<” “;
temp=temp->get_next();}
cout<<“\n”;
}
}
};
void main()
{ linklist p;
int c=0,n;
while (c!=5)
{cout<<” press 1 for inseart number \n”;
cout<<“press 2 for delete number \n”;
cout<<“press 3 for display numbers\n “;
cout<<“press 4 for sort \n”;
cout<<“press 5 for exit \n”;
cin>>c;
switch(c)
{case 1:
int n;
cout<<“enter the number in queue \n”;cin>>n;
p.insart(n);break;
case 2:
p.del();break;
case 3:
//use system clear screen here
p.display();break;
case 4:
p.BubbleSort();
}
}
getch();
}

C++ code for bubble sort in linklist with binary search

#include<iostream>
#include<conio.h>
#include<cstdlib>
#include<time.h>
#include<windows.h>

using namespace std;

class node
{
public:
int data;
node*next;
node*pre;
node()
{
next=NULL;
pre=NULL;
data=0;
}
};
class linklist
{
node*head;
int count;

public:
linklist()
{
head=NULL;
count=0;
}

void insert(int dataa)
{
node*p=head;
node*newnode=new node;
newnode->data=dataa;
head=newnode;
newnode->next=p;
if(p!=NULL)
p->pre=newnode;
count++;

}

void display()
{
node*p;
p=head;

while(p!=NULL)
{
cout<<p->data<<” “;
if(p->next==NULL)
break;
p=p->next;
}
}

void bubble()
{
int tmp=0,i=0;
node*p=head->next,*q=head,*r,*s;
r=p;s=q;
while(i<count-1)
{
p=head->next; q=head;
while(p!=NULL)
{
if(p->data<q->data)
{
tmp=p->data;
p->data=q->data;
q->data=tmp;
}

q=p;
p=p->next;
}
i++;
}
}

node* binary_search(int dataa,int left,int right)
{
node*p;
p=head;
int mid=(left+right)/2;
for(int i=1;i<mid;i++)
p=p->next;

if(p->data==dataa)
return p;

if(left-right==0)
return NULL;

if(dataa<p->data)
return binary_search(dataa,left,mid);
else
return binary_search(dataa,mid+1,right);
}

int getcount()
{return count;}

};

int main()
{
srand(time(0));
linklist a;
for(int i=1;i<=10;i++)
a.insert(rand()%100);
a.display();
cout<<endl;
a.bubble();
a.display();
int data;
cout<<endl<<“Enter data: “;
cin>>data;
node*p=a.binary_search(data,1,a.getcount());
if(p!=NULL)
cout<<p->data<<” “<<p;
else
cout<<p<<“NO DATA EXISTS”;

getch();
}

At Cui tutorial, courses, past papers and final year projects

#tutorial #cui #pastpaper #courses #finalyearprojects