• About WordPress
    • WordPress.org
    • Documentation
    • Support
    • Feedback
  • Log In
  • Register
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment
Cuitutorial
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment

Data Structure

Home » Blog » Bubble Sort using C++

Bubble Sort using C++

  • Posted by saqib
  • Categories Data Structure
  • Date December 6, 2022
  • Comments 0 comment

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

 

  • Share:
author avatar
saqib

Previous post

Sorting and searching in data structure
December 6, 2022

Next post

Insertion Sort
December 6, 2022

You may also like

Counting Sort
6 December, 2022

Counting sort is a type of Linear Time Sort Counting Sort was invented by H.H.Seward in 1954 All the sorting algorithms introduced so far share an                              …

Insertion Sort
6 December, 2022

Insertion Sort using loop and recursive function complete code On the ith pass we “insert” the ith element A[i] into its rightful place among A[1],A[2],…A[i-1] which were placed in sorted order. After this insertion A[1],A[2],…A[i] are in sorted order. Time …

Sorting and searching in data structure
6 December, 2022

What is Sorting? Sorting is the process of ordering a list of objects, according to some linear order, such as £ for numbers. Sorting can be divided into two types i.e. internal and external. Internal sorting takes place in main …

Leave A Reply Cancel reply

You must be logged in to post a comment.

admin@cuitutorial.com
Facebook-f Twitter Youtube Linkedin Instagram Stack-overflow Pinterest Github Quora Whatsapp
Courses
  • All Courses
  • Past Paper
  • Final year projects
  • Interview Questions
  • Contact
Important Pages
  • Privacy Policy
  • Terms of Service
  • Cookie Policy
Links
  • University Events
  • Team
Education & learning platform for All Computer science subjects
Final year projects
Past Paper
Interview questions
Programming, C/C++, Asp.net/MVC. Android, MySql, Jquery, Ajax, javascript, Php, Html5, Bootstrap4.
NTS, GAT, PPSC, FPSC

Copyright © 2021 | Cuitutorial