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();
}
Related links
Single link list Stack AVL Trees Binary search Counting Sort
Doubly link list Queue Graphs Bubble Sort Radix sort
Circular link list Binary search tree Hashing Insertion Sort Bucket Sort
Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort
At Cui tutorial, courses, past papers and final year projects
#tutorial #cui #pastpaper #courses #finalyearprojects
