Roman numbers to decimal conversion ,c++ program...

//Roman numbers to decimal conversion ,c++ program

#include<iostream.h>
#include<process.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>

void main()
{
int s=0,beg=0,k,end=k,i,c=0,mid,m[50],p,j;
    char a[50];
    clrscr();
    cout<<"ENTER THE ROMAN NUMBER\n";
gets(a);
k=strlen(a);
for(i=0;i<k;i++)
{
switch(a[i])
{
    case 'I':
    p=1;
    m[i]=p;
    c++;
    break;       

    case 'V':
    p= 5;
    m[i]=p;
    c++;
    break;

    case 'X':
    p=10;
    m[i]=p;
    c++;
    break;

    case 'L':
    p=50;
    m[i]=p;
    c++;
    break;                      

    case 'C':
    p=100;
    m[i]=p;
    c++;
    break;

    case 'D':
    p=500;
    m[i]=p;
    c++;
    break;

    case 'M':
    p=1000;
    m[i]=p;
    c++;
    break;

    default:cout<<"sorry INVALID\n";
    getch();
    exit(0);

}

}

for(i=0;i<k;i++)
{

 while(beg<end)    
 {


 mid=(end+beg)/2;
  end=mid;

 if(beg==end)
 {

     s=s+m[beg];
     beg=beg+1;
     end=k;
 }
 else if((end-beg)==1)
 {
if(m[end]>m[beg])
{


     s=s+(m[end]-m[beg]);
     beg=end+1;
     end=k;
 }
 }

 }
}
cout<<"Decimal value   "<<s;
getch();
}

how to calculate the address of the 2D array

Address of a[ i ][ j ]th element (row major)
*********************************************
 BA + [ n * ( i - LBR) + ( j - LBC) ] * w

                                                         Where BA = Base address
                                                               W = Number of bytes occupied by each element
                                                                 N = Number of columns


Address of a[ i ][ j ]th element (colum major)
*********************************************
     BA + [ ( i - LBR) + m * ( j - LBC) ] * w

                                                           Where BA = Base address
                                                                        W = Number of bytes occupied by each element
                                                                         N = Number of rows

 WHAT IS A 2D ARRAY?

 A matrix (two dimensional array) is a group of lists, or arrays that are organized into one data set. To understand them, first look an example of the standard one dimensional array:

Array "A":
16
8
99
0
5

You can reference any point in the "array" by naming the array and following it with a number representing the position of a piece of data on the list. The first data on the array is represented with a "0", the second with a "1", and so on. For example, A[2] (in bold) represents 99 because it is the third figure of array A. You could imagine the references of the above table as the following:

Array "A":
[0]
[1]
[2]
[3]
[4]

A matrix is a set of arrays. Visualize the following table:

Matrix "B":
16 17 9
8 88 74
99 12 21
0 6 40
5 19 18

There are 3 different arrays in a single data set, "B". In Array A, you could reference any data by naming the point on the list, such as "1" or "3". However, with a matrix, you must give both a row and a column. You can reference data on a matrix in the following format:

MatrixName[row][column]

For example, B[3][2] would represent 40 because it is the it is on the fourth row down and the third column. Remember, matrix references also start at zero, not one! You can reference any of the data on this table with this chart:

Matrix "B":
[0][0] [0][1] [0][2]
[1][0] [1][1] [1][2]
[2][0] [2][1] [2][2]
[3][0] [3][1] [3][2]
[4][0] [4][1] [4][2]

Two-dimensional arrays are used everywhere, but are especially prevalent in computer programming and accounting

infix to postfix conversion

Infix to Postfix conversion using stack

Introduction:
         In the last post I have explained about the infix,prefix,postfix expression. In this post we are going to know about the conversion of infix to postfix expression.

Infix to Postfix Conversion:

• Consider an infix string x+y*c.Each character of the string is called tokens.
• The algorithm for converting an infix expression to postfix expression is given below.
• We need a stack to solve this problem

Algorithm for converting infix expression to postfix expression:

• Initialize an empty stack and a Postfix String S.
• Read the tokens from the infix string one at a time from left to right
• If the token is an operand, add it to the Postfix string S.
• If the token is a left parentheses, Push it on to the stack
• If the token is a right parentheses
  1. Repeatedly Pop the stack and add the poped out element in to the string S until a left parenthesis is encountered;
  2. Remove the left parenthesis from the stack and ignore it
• If the token is an operator
  1. If the stack is empty push the operator in to the stack       
  2. If the stack is not empty compare the precedence of the operator with the element on top of the stack
     • If the operator in the stack has higher precedence than the token Pop the stack and add the poped out element in to the string S. else Push the operator in to the stack                   
     • Repeat this step until the stack is not empty or the operator in the stack has higher precedence than the token         
• Repeat this step till all the characters are read.
• After all the characters are read and the stack is not empty then Pop the stack and add the tokens to the string S
• Return the Postfix string S

Example for Converting infix to Postfix Expression:

Example 1:
Infix String----->A*B+C/D
Solution:

1. Initially the stack is empty and the Postfix String S has no characters
2. Read the token A.A is a operand so it is added to the string S.now Stack->empty and S->A
3. Read the token *.* is an operator.stack is empty so push * in to the stack. now Stack->* and S->A
4. Read the token B.B is an operand so it is added to the string S. now Stack->* and S->AB
5. Read the token +.+is an operator.compare +and *.* has higher precedence than +. so pop * from the stack and add it to the string S. now Stack->empty and S->AB*.now the stack is empty so push the + in to the stack.now Stack->+ and S->AB*
6. Read the token C.C is a operand so it is added to the string S.now Stack->+ and S->AB*C
7. Read the token /./ is an operator.compare /and +./ has higher precedence than +. so push / in to the stack . now Stack->+/ and S->AB*C
8. Read the token D.D is a operand so it is added to the string S.now Stack->+/ and S->AB*CD
9. All the characters are read but the stack is not empty so pop the stack and add the characters to the String. now S->AB*CD/+

     So the Postfix String is AB*CD/+


Example 2:
Infix String----->A*(B+C)/D
Solution:

1. Initially the stack is empty and the Postfix String S has no character.
2. Read the token A.A is a operand so it is added to the string S.now Stack->empty and S->A
3. Read the token *.* is an operator.stack is empty so push * in to the stack. now Stack->* and S->A
4. Read the token (.push the left parentheses in to the stack.
5. Read the token B.B is an operand so it is added to the string S. now Stack->* and S->AB
6. Read the token +.+is an operator.compare +and *.+ has lower precedence than *.So push + in to the stack. now Stack->*+ and S->AB
7. Read the token C.C is an operand so it is added to the string S.now Stack->*+ and S->ABC
8. Read the token ). ) is a right parentheses ,Pop the stack and add the + in to the string S. now Stack->* and S->ABC+
9. Read the token /./ is an operator.compare /and *./ and * have equal precedence but * comes before /so pop the stack and add * in to the string S.now stack is empty so push / in to the stack . now Stack->/ and S->ABC+*
10. Read the token D.D is an operand so it is added to the string S.now Stack->/ and S->ABC+*D 
11. Now the input string is empty but the stack is not empty so pop the stack and add the characters to the String.now Stack->Empty and S->ABC+*D/

         So the Postfix String is ABC+*D/

program to perform sparse matrix addition

program to add sparse matrix

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define MAX1 3
#define MAX2 3
#define MAXSIZE 9
#define BIGNUM 100
struct sparse
{
int *sp ;
int row ;
int *result ;
} ;
void initsparse ( struct sparse * ) ;
void create_array ( struct sparse * ) ;
int count ( struct sparse ) ;
void display ( struct sparse ) ;
void create_tuple ( struct sparse *, struct sparse ) ;
void display_tuple ( struct sparse ) ;
void addmat ( struct sparse *, struct sparse, struct sparse ) ;
void display_result ( struct sparse ) ;
void delsparse ( struct sparse * ) ;
void main( )
{
struct sparse s[5] ;
int i ;
clrscr( ) ;
for ( i = 0 ; i <= 4 ; i++ )
initsparse ( &s[i] ) ;
create_array ( &s[0] ) ;
create_tuple ( &s[1], s[0] ) ;
display_tuple ( s[1] ) ;
create_array ( &s[2] ) ;
create_tuple ( &s[3], s[2] ) ;
display_tuple ( s[3] ) ;
addmat ( &s[4], s[1], s[3] ) ;
printf ( "\nResult of addition of two matrices: " ) ;
display_result ( s[4] ) ;
for ( i = 0 ; i <= 4 ; i++ )
delsparse ( &s[i] ) ;
getch( ) ;
}
/* initialises structure elements */
void initsparse ( struct sparse *p )
{
p -> sp = NULL ;
p -> result = NULL ;
}
/* dynamically creates the matrix */
void create_array ( struct sparse *p )
{
int n, i ;
/* allocate memory */
p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof ( int ) ) ;
/* add elements to the array */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
printf ( "Enter element no. %d:", i ) ;
scanf ( "%d", &n ) ;
* ( p -> sp + i ) = n ;
}
}
/* displays the contents of the matrix */
void display ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % MAX2 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
}
/* counts the number of non-zero elements */
int count ( struct sparse s )
{
int cnt = 0, i ;
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
if ( * ( s.sp + i ) != 0 )
cnt++ ;
}
return cnt ;
}
/* creates an array that stores information about non-zero elements */
void create_tuple ( struct sparse *p, struct sparse s )
{
int r = 0 , c = -1, l = -1, i ;
/* get the total number of non-zero elements
and add 1 to store total no. of rows, cols, and non-zero values */
p -> row = count ( s ) + 1 ;
/* allocate memory */
p -> sp = ( int * ) malloc ( p -> row * 3 * sizeof ( int ) ) ;
/* store information about
total no. of rows, cols, and non-zero values */
* ( p -> sp + 0 ) = MAX1 ;
* ( p -> sp + 1 ) = MAX2 ;
* ( p -> sp + 2 ) = p -> row - 1 ;
l = 2 ;
/* scan the array and store info. about non-zero values in the 3-tuple */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
c++ ;
/* sets the row and column values */
if ( ( ( i % MAX2 ) == 0 ) && ( i != 0 ) )
{
r++ ;
c = 0 ;
}
/* checks for non-zero element row, column and non-zero element value is assigned to the matrix */
if ( * ( s.sp + i ) != 0 )
{
l++ ;
* ( p -> sp + l ) = r ;
l++ ;
* ( p -> sp + l ) = c ;
l++ ;
* ( p -> sp + l ) = * ( s.sp + i ) ;
}
}
}
/* displays the contents of the matrix */
void display_tuple ( struct sparse s )
{
int i, j ;
/* traverses the entire matrix */
printf ( "\nElements in a 3-tuple: \n" ) ;
j = ( * ( s.sp + 2 ) * 3 ) + 3 ;
for ( i = 0 ; i < j ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
printf ( "\n" ) ;
}
/* carries out addition of two matrices */
void addmat ( struct sparse *p, struct sparse s1, struct sparse s2 )
{
int i = 1, j = 1, k = 1 ;
int elem = 1 ;
int max, amax, bmax ;
int rowa, rowb, cola, colb, vala, valb ;
/* get the total number of non-zero values from both the matrices */
amax = * ( s1.sp + 2 ) ;
bmax = * ( s2.sp + 2 ) ;
max = amax + bmax ;
/* allocate memory for result */
p -> result = ( int * ) malloc ( MAXSIZE * 3 * sizeof ( int ) ) ;
while ( elem <= max )
{
/* check if i < max. non-zero values
in first 3-tuple and get the values */
if ( i <= amax )
{
rowa = * ( s1.sp + i * 3 + 0 ) ;
cola = * ( s1.sp + i * 3 + 1 ) ;
vala = * ( s1.sp + i * 3 + 2 ) ;
}
else
rowa = cola = BIGNUM ;
/* check if j < max. non-zero values in secon 3-tuple and get the values */
if ( j <= bmax )
{
rowb = * ( s2.sp + j * 3 + 0 ) ;
colb = * ( s2.sp + j * 3 + 1 ) ;
valb = * ( s2.sp + j * 3 + 2 ) ;
}
else
rowb = colb = BIGNUM ;
/* if row no. of both 3-tuple are same */
if ( rowa == rowb )
{
/* if col no. of both 3-tuple are same */
if ( cola == colb )
{
/* add tow non-zero values
store in result */
* ( p -> result + k * 3 + 0 ) = rowa ;
* ( p -> result + k * 3 + 1 ) = cola ;
* ( p -> result + k * 3 + 2 ) = vala + valb ;
i++ ;
j++ ;
max-- ;
}
/* if col no. of first 3-tuple is < col no. of second 3-tuple, then add info. as it is to result */
if ( cola < colb )
{
* ( p -> result + k * 3 + 0 ) = rowa ;
* ( p -> result + k * 3 + 1 ) = cola ;
* ( p -> result + k * 3 + 2 ) = vala ;
i++ ;
}
/* if col no. of first 3-tuple is > col no. of second 3-tuple, then add info. as it is to result */
if ( cola > colb )
{
* ( p -> result + k * 3 + 0 ) = rowb ;
* ( p -> result + k * 3 + 1 ) = colb ;
* ( p -> result + k * 3 + 2 ) = valb ;
j++ ;
}
k++ ;
}
/* if row no. of first 3-tuple is < row no. of second 3-tuple, then add info. as it is to result */
if ( rowa < rowb )
{
* ( p -> result + k * 3 + 0 ) = rowa ;
* ( p -> result + k * 3 + 1 ) = cola ;
* ( p -> result + k * 3 + 2 ) = vala ;
i++ ;
k++ ;
}
/* if row no. of first 3-tuple is > row no. of second 3-tuple, then add info. as it is to result */
if ( rowa > rowb )
{
* ( p -> result + k * 3 + 0 ) = rowb ;
* ( p -> result + k * 3 + 1 ) = colb ;
* ( p -> result + k * 3 + 2 ) = valb ;
j++ ;
k++ ;
}
elem++ ;
}
/* add info about the total no. of rows, cols, and non-zero values that the resultant array contains to the result */
* ( p -> result + 0 ) = MAX1 ;
* ( p -> result + 1 ) = MAX2 ;
* ( p -> result + 2 ) = max ;
}
/* displays the contents of the matrix */
void display_result ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i < ( * ( s.result + 0 + 2 ) + 1 ) * 3 ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.result + i ) ) ;
}
}
/* deallocates memory */
void delsparse ( struct sparse *p )
{
if ( p -> sp != NULL )
free ( p -> sp ) ;
if ( p -> result != NULL )
free ( p -> result ) ;
}

Sparse matrices, which are common in scientific applications, are matrices in which most elements are zero. To save space and running time it is critical to only store the nonzero elements. A standard representation of sparse matrices in sequential languages is to use an array with one element per row each of which contains a linked-list of the nonzero values in that row along with their column number. A similar representation can be used in parallel. In NESL a sparse matrix can be represented as a sequence of rows, each of which is a sequence of (column-number, value) pairs of the nonzero values in the row

operator overloading using friend function

operator overloading both unary and binary operator using friend function.

What is a friend function c plus plus?

A friend function in C++ is a function that is not part of the implementation of a class, i.e. not a method of the class, but that is allowed to manipulate the private parts of a class.

#include <iostream>
using namespace std;
class loc {
int longitude, latitude;
public:
loc() {} // needed to construct temporaries
loc(int lg, int lt) {
longitude = lg;
latitude = lt;
}
void show() {
cout << longitude << " ";
cout << latitude << "\n";
}
friend loc operator+(loc , loc ); // now a friend
loc operator-(loc op2);
loc operator=(loc op2);
loc operator++();
};
// Now, + is overloaded using friend function.
loc operator+(loc op1, loc op2)
{
loc temp;
temp.longitude = op1.longitude + op2.longitude;
temp.latitude = op1.latitude + op2.latitude;
return *this;
}
// Overload - for loc.
loc loc::operator-(loc op2)
{
loc temp;
// notice order of operands
temp.longitude = longitude - op2.longitude;
temp.latitude = latitude - op2.latitude;
return temp;
}
// Overload assignment for loc
loc loc::operator=(loc op2)
{
longitude = op2.longitude;
latitude = op2.latitude;
return *this; // i.e., return object that generated call
}
// Overload ++ for loc.
loc loc::operator++()
{
longitude++;
latitude++;
return *this;
}
int main()
{
loc ob1(10, 20), ob2( 5, 30);
ob1 = ob1 + ob2;
ob1.show();
return 0;
}

C++ Operator Overloading Guidelines

One of the nice features of C++ is that you can give special meanings to operators, when they are used with user-defined classes. This is called operator overloading. You can implement C++ operator overloads by providing special member-functions on your classes that follow a particular naming convention. For example, to overload the + operator for your class, you would provide a member-function named operator+ on your class.
The following set of operators is commonly overloaded for user-defined classes:

• = (assignment operator)
• + - * (binary arithmetic operators)
• += -= *= (compound assignment operators)
• == != (comparison operators)

operator overloading

operator overloading using unary and binary operator
#include <iostream>
using namespace std;
class loc
{
int longitude, latitude;
public:
loc() {} // needed to construct temporaries
loc(int lg, int lt)
{
longitude = lg;
latitude = lt;
}
void show()
{
cout << longitude << " ";
cout << latitude << "\n";
}
loc operator+(loc op2);
loc operator-(loc op2);
loc operator=(loc op2);
loc operator++();
};
// Overload + for loc.
loc loc::operator+(loc op2)
{
loc temp;
temp.longitude = op2.longitude + longitude;
temp.latitude = op2.latitude + latitude;
return *this;
}
// Overload - for loc.
loc loc::operator-(loc op2)
{
loc temp;
// notice order of operands
temp.longitude = longitude - op2.longitude;
temp.latitude = latitude - op2.latitude;
return *this;
}
// Overload asignment for loc.
loc loc::operator=(loc op2)
{
longitude = op2.longitude;
latitude = op2.latitude;
return *this; // i.e., return object that generated call
}
// Overload prefix ++ for loc.
loc loc::operator++()
{
longitude++;
latitude++;
return *this;
}
int main()
{
loc ob1(10, 20), ob2( 5, 30), ob3(90, 90);
ob1.show();
ob2.show();
++ob1;
ob1.show(); // displays 11 21
ob2 = ++ob1;
ob1.show(); // displays 12 22
ob2.show(); // displays 12 22
ob1 = ob2 = ob3; // multiple assignment
ob1.show(); // displays 90 90
ob2.show(); // displays 90 90
return 0;
}

*what is operator overloading?
Operators are functions. Specifically, operators are special functions that are used to perform operations on data without directly calling methods each time. Common operators that you should be familiar with include +, -, *, /, <<, >>, and so on. All such operators can be used on primative data types in C++ to achieve certain results. For example, we can use the + operator to add together two numeric values, such as ints, floats, and doubles:
* What are the benefits of operator overloading?

By overloading standard operators on a class, you can exploit the intuition of the users of that class. This lets users program in the language of the problem domain rather than in the language of the machine.
The ultimate goal is to reduce both the learning curve and the defect rate.

program for queue Implementation using Linked List in C++

Queue Implementation using Linked List in C++

#include<iostream.h>
#include<conio.h>
struct node
{
 int data;
 struct node *link;
};
class queue
{
 struct node *front,*rear,*ptr;
 public:
 queue(){
 rear=NULL;
 front=NULL;
 }
 void enqueue(int);          
 void dqueue();
 void display();
};
  void queue::enqueue(int data)
{
  ptr=new node;
  if(rear==NULL)
   { front=ptr;
   }
   else
   {
    rear->link=ptr;
    ptr->link=NULL;
    }
    rear=ptr;
  rear->data=data;               
  cout<<"\n>>";
      }
  void queue::dqueue()
{
int item;
 if(front==NULL)
 cout<<"\nQueue is empty:\n";
 else
 {
   item=front->data;
if(front==rear)
   {
   front=NULL;
   rear=NULL;
   }
else
{
   ptr=front;
   front=front->link;
   delete ptr;
   }
   cout<<"deleted elmnt : "<<item;
 }
}

  void queue::display()
{
ptr=front;
 if(front==NULL)
    cout<<"\nQueue is empty";
 else
    {
cout<<"\nElements in queue are: ";
     while(ptr!=NULL)
{
  cout<<ptr->data<<"|";
  ptr=ptr->link;
}
    }         
}
  void main()
{
queue q;
int ch,data;
clrscr();
cout<<"\n........MENU..........\n";
cout<<"1 . enqueue\n";
cout<<"2 . dqueue\n";
cout<<"3 . display\n";
cout<<"4 . exit\n";
while(1)
{
cout<<"\n Enter your choice: ";
cin>>ch;
switch(ch)
   {
    case 1:
    cout<<"\n Enter the element: ";
    cin>>data;
    q.enqueue(data);break;

    case 2:
    q.dqueue();break;

    case 3:
    q.display();break;

    case 4:
    ch=5;break;
    default:
    cout<<"\nInvalid selection\n";break;
    }
    if(ch==5)
    break;
}
       getch();
}

What are queues in C plus plus?

A queue in any language is a singly-linked list structure that permits new data to be inserted only at the end of a list while existing data can only be extracted from the beginning of the list. Queues are also known as a first in, first out (FIFO) structure. Unlike a standard singly-linked list, the list maintains a pointer to the last node as well as the first, in order to insert new data and extract existing data in constant time.
Variations on the queue include the priority queue which permit data to be weighted, such that data with the greatest priority is promoted to the front of the queue, behind any existing data with the same or higher priority, using an insertion sort technique. Insertion is therefore achieved in linear time rather than constant time, however extraction is always in constant time.

Linked Lists

The linked list is used in many libraries/applications and for a good reason. The following are advantages it has over other containers, indirectly from the reference page on cplusplus.com:

• Efficient insertion and erasure of elements anywhere in the container (constant time).
• Iterating over the elements in forward order (linear time).
• Efficient moving elements and block of elements within the container or even between different containers (constant time).

The following only applies to a doubly linked list which I will explain later on:

• Iterating over the elements in forward or reverse order (linear time).

Something the reference doesn't explain is how it's implemented. Why would you *want* to know about that? For me, simply curiosity. For others, perhaps they may create their own type of linked list container. Either way, it's knowledge that *someone* will eventually use hopefully. 

Design

The linked list is generally pictured as a list of linear nodes that are tethered together somehow. In C/++, you generally have a structure which contains data and a pointer to the next structure container which contains data and a pointer to the next structure container... and so on. The linked list's main advantage is that it doesn't contain data in a contiguous way and rather, a flexible way. This allows for fast insertion and better overall iteration. The linked list is often even used as the basis for other containers (such as queue or stack containers).

There are several variations of the linked-list. Actually, the term "linked list" doesn't really refer to the implementation (thus, an abstract term), just the nature of how the data of the container is held (linked via references). The most common implementation of the linked list is probably the doubly linked list. The doubly linked list is a list that contains nodes that contains references to the previous *and* next link in the list. This allows for fast node erasure, faster fetching of end nodes, and more flexible iteration.

At the cost of flexibility of the doubly-linked list, it generally costs more memory to use. In large lists, consider the idea of a node being twice the size as normal. This can affect the application quite a bit. In the case that you have no reason to iterate backwards, the doubly-linked list can be considered inefficient, simply by design. std::list is a doubly linked list. As a result, if I ever come about the need for a singly-linked list, I implement my own. A singly-linked list can only iterate forward simply because the node it holds only holds a reference to the next node in the list and not the previous but comes with the merit of one less reference.

Another type of linked-list that's not used quite as often is the circular linked-list. All this is a singly/doubly-linked list where the end node iterates forward to the beginning node (and possibly vice versa). There aren't many uses for this as it generally has problems with iterating through the list but take, for instance, a list that iterates through the nodes until a given signal is received. Also, it's really a technique used with linked lists... not always in implementation although special list implementations can handle circular linked lists better than others.

In embedded systems, the use of linked lists can be expensive. The holding of each reference can be so heavy that it's undesirable to use a linked-list with nodes that only hold one location of data. Instead, they generally used what's called unrolled linked lists. In an unrolled linked list, the node holds a reference to the next and previous, like normal, but each node holds arrays of data. When you iterate through each node, you iterate through the data in the array linearly, then move on to the next node. This way we can have three or four nodes of data in one while reducing the amount of nodes altogether (therefor saving memory). However, this generally uses contiguous memory to hold nodes so it becomes difficult to move nodes that are in the array.

program to illustrate pass by reference method

#include<iostream.h>
#include<conio.h>
class sample
{
int x;
public:
void read()
{
cout<<"Enter the value\n";
cin>>x;
}
void display()
{
cout<<"The sum is\n";
cout<<x;
}
void add(sample &s1,sample &s2)
{
x=s1.x+s2.x;
}
};
void main()
{
sample s1,s2,s3;
clrscr();
s1.read();
s2.read();
s3.add(s1,s2);
s3.display();
getch();
}

Pass by value

When you use pass-by-value, the compiler copies the value of an argument in a calling function to a corresponding non-pointer or non-reference parameter in the called function definition. The parameter in the called function is initialized with the value of the passed argument. As long as the parameter has not been declared as constant, the value of the parameter can be changed, but the changes are only performed within the scope of the called function only; they have no effect on the value of the argument in the calling function.

Pass by reference

Passing by by reference refers to a method of passing the address of an argument in the calling function to a corresponding parameter in the called function.In C, the corresponding parameter in the called function must be declared as a pointer type. In C++, the corresponding parameter can be declared as any reference type, not just a pointer type.

In this way, the value of the argument in the calling function can be modified by the called function.

Difference between pass by value and pass by reference  

In pass by value approach, the called function creates another copies of the variables passes as arguments. In this approach, the values of the original variables remain unchanged. However, we come across situations where we need to change the values of the original variables. Then the values may b passed by reference

program to represent pass by value concept

c++program code for representing  pass by value concept,also connected with class object concept
#include<iostream.h>
#include<conio.h>
class sample
{
int x;
public:
void read()
{
cout<<"Enter the value\n";
cin>>x;
}
void display()
{
cout<<"The sum is\n";
cout<<x;
}
void add(sample s1,sample s2)
{
x=s1.x+s2.x;
}
};
void main()
{
sample s1,s2,s3;
clrscr();
s1.read();
s2.read();
s3.add(s1,s2);
s3.display();
getch();
}

program to swap the values of 2 different object

c++ program code for swapping the values of different object (uses freind function concept)

c++ program code for swaping the values of different object

#include<iostream.h>
#include<conio.h>
class sample
{
int x;
public:
void read();
friend void display(sample,sample);
friend void swap(sample,sample);
};
void sample::read()
{
cout<<"Enter the value\n";
cin>>x;
}
void display(sample s1,sample s2)
{
cout<<"Before swaping\n";
cout<<"s1  "<<s1.x;
cout<<"\ns2  " <<s2.x;
}

void swap( sample s1,sample s2)
{
int t;
t=s1.x;
s1.x=s2.x;
s2.x=t;
cout<<"\nAfter swaping\n";
cout<<"s1  "<<s1.x;
cout<<"\ns2  " <<s2.x;
}
void main()
{
clrscr();
sample s1,s2;
s1.read();
s2.read();

display(s1,s2);
swap(s1,s2);
getch();
}

 what is an object?

A region of storage with associated semantics.

After the declaration int i; we say that "i is an object of type int." In OO/C++, "object" usually means "an instance of a class." Thus a class defines the behavior of possibly many objects (instances).

program to add n time in hh\mm\ss format(using class)

program to add n time using  class and object concept

program to add n numbers using class and object concept

#include<iostream.h>
#include<conio.h>
 class time
 {
 public:
 int h,m,s,oh,om,os,i,j,n,p,q;
 void read();
 void display();

 }ob;
 void time:: read()
 {
 cout<<"Enter the limit\n";
 cin>>n;
  h=0;
 m=0;
 s=0;

 for(i=0;i<n;i++)
 {
 cout<<"Enter the "<<i+1<<" time in hh/mm/ss format \n";
 cin>>oh;
 h=h+oh;
 cin>>om;
 m=m+om;
 cin>>os;
 s=s+os;
 }
 }
 void time::display( )
 {

  p=ob.s/60;
  ob.s=ob.s%60;
  q= (ob.m+p)/60;
  ob.m=(ob.m+p)%60;
  ob.h=ob.h+q;
  cout<<" time in hh/mm/ss format \n";
  cout<<ob.h<<":"<<ob.m<<":"<<ob.s;
  }
  void main()
  {
  clrscr();
  ob.read();
  ob.display();
  getch();
  }

program for queue operation

Program for queue operation ,using   class object concept.

#include<iostream.h>
#include<conio.h>
class queue
{
public:
int q[50],n,limit,front, rear;
queue()
{
cout<<"\nEnter the limit\n";
cin>>limit;
front=0;
rear=0;
}
void push();
void pop();
void peep();
};
void queue::push()
{
if(rear<limit)
{
cout<<"Enter the data\n";
cin>>q[rear];
rear++;
cout<<"Element inserted\n";
}
else
{
cout<<"\nqueue is full\n";
}

}
void queue::pop()
{
if(front<rear)
{
front++;

push operation in a queue

cout<<"\nElement is deleted\n";
}
else
{
cout<<"Queue is empty\n";
}
}


 void queue::peep()
 {
 int i;
 if(front<rear)
 {
 cout<<"The queue elements are:";
 for(i=front;i<rear;i++)
 {
 cout<<"\n"<<q[i];
 }
 }
 else
 {
 cout<<"Queue is empty\n";
 }
 }
 void main()
 {
 clrscr();
 queue ob;
 int n,limit;
 do
 {
 cout<<"\nMENU\n\n1.PUSH\n2.POP\n3.PEEP\n4.EXIT\n";
 cout<<"\nENTER YOUR CHOICE:";
 cin>>n;
 switch(n)
 {
 case 1:ob.push();
       break;
case 2:ob.pop();
break;
case 3: ob.peep();
break;
}

}while(n!=4);
getch();
}

what is a queue i?

A queue is a singly linked list that models a first in first out model (just as a queue of diners are dealt with on a first come first served basis). Insertions always occur at the tail of the queue and extractions always at the head.
A variation of the queue is a priority queue where nodes are weighted such that those with higher priority are moved in front of those with lower priority. This is akin to diners who have a reservation being moved to the head of the queue. In this case, insertions always occur at the head but the head node will pass the data onto the next node if the data has lower priority. The process continues until the data has higher priority than the current node at which point is it is placed in front of the current node. If the current node has no next node to pass the data onto, the data becomes the tail node. This is known as an insertion sort.

Difference between Stack and Queue  

Stack is a collection of objects that works in LIFO (Last in First out) mechanism while Queue is FIFO (First in First out). This means that the object that is inserted first is removed last in a stack while an object that is inserted first is removed first in a queue

program for all stack operation

c++ program for stack operations..(operation include pop,peep,push)
#include<iostream.h>
#include<conio.h>
class stack
{
public:
int s[50],n,item,top;
void read();
void push();                // for stck insertion
void pop();                //for stack deletion
void display();          // displaying stack element
};
void stack:: read()
{
cout<<"Enter the limit of the stack\n";
cin>>n;
}
void stack::push()
{
top++;
if(top==n)
{
cout<<"Stack full\n";
getch();
}
else
{
cout<<"Enter the item\n";
cin>>item;
s[top]=item;
cout<<"Element inseted into the stack\n";
}
}
void stack::pop()
{
if(top==-1)
{
cout<<"Stack empty\n";
}
else
{
top--;
cout<<"Element deleted\n";
}
}
 void stack::display()
 {
 int i;
 if(top==-1)
 {
 cout<<"Stack is empty\n";
 getch();
 }
 else
 {
 cout<<"The stack elements are:";
 for(i=top;i>=0;i--)
 {
 cout<<"\n"<<s[i];
 getch();
 }
 }
 }
 void main()
 {
 clrscr();
 stack a;
 a.top=-1;
 int n,c,k;
 a.read();
 do
 {
 cout<<"\nMENU\n\n1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT\n";
 cout<<"\nENTER YOUR CHOICE:";
 cin>>n;
 switch(n)
 {
 case 1:
 cout<<"\nenter number of insertion:";
 cin>>c;
 for(k=0;k<c;k++)
 {
 a.push();
 }
 break;
case 2:
 cout<<"\nenter number of deletion:";
 cin>>c;
 for(k=0;k<c;k++)
 {
 a.pop();
 }
 break;
case 3:
 a.display();
 break;

}
}while(n!=4);
getch();
}
what is stack operation?
Stack is an ordered group of homogeneous items. —Items are added to and removed from the top of the stack (the most recently added items are at the top of the stack). —The last item to be added is the first to be removed (LIFO: Last In, First Out). A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end called the TOP of the stack.
—The implementation of stack provides for the insertion and deletion of items (at run time), so that a stack is a dynamic, constantly changing object.—

Difference between Stack and Queue  

Stack is a collection of objects that works in LIFO (Last in First out) mechanism while Queue is FIFO (First in First out). This means that the object that is inserted first is removed last in a stack while an object that is inserted first is removed first in a queue

Recursive program for finding tha greatest common divisor.

greatest common divisor(GCD) or HCF highest common factor....

#include<iostream.h>
#include<conio.h>
#include<process.h>
void hcf(int,int);
void main()
{
int a,b,c;
clrscr();
cout<<"Enter two numbers\n";
cin>>a>>b;
hcf(a,b);
getch();
}
void hcf(int a,int b)
{
int rem;
if(b>0)
{
rem=a%b;
a=b;
b=rem;
hcf(a,b);  //recursive function call for greatest common factor
}
cout<<" The GCD is\t"<<a;
getch();
exit(0);
}

method 2
#include<iostream.h>
#include<conio.h>
int gcd(int,int);
void main()
{
int a,b,c;
clrscr();
cout<<"Enter two numbers\n";
cin>>a>>b;
c=gcd(a,b);
cout<<"The Greatest Common Divisor is \t"<<c;
getch();
}
int gcd(int n,int m)
{
if(n%m== 0)
{
 return m;
 }
 else
 return gcd(m,n%m);
 }

what is recursion in c++?

Recursion, in any programming language, refers to, most commonly, a call to a function inside that function, (i.e a function calling itself) .

program for binary search

// program for binary search.
 .#include
#include
int search(int[],int,int);                                                                    //binary search declaration
void main()
{
int a[20],n,item,p,i;
clrscr();
printf("Enter the limit\n");
scanf("%d",&n);
printf("Enter the array\n");
for(i=0;iscanf("%d",&a[i]);
printf("Enter the array to be searched\n");
scanf("%d",&item);
p=search(a,n,item);                                                                         //   binary search call
if(p==-1)
{
printf("sorry\n");
}
else{
printf("Item found at %d position",p+1);
}

getch();
}
int search(int a[],int n, int item)                                                                //   binary search definition
{
int beg=0,end=n-1,mid;
while(beg<=end)
{
mid=(beg+end)/2;
if(a[mid]==item)
{
return mid;
 }
else if(item>a[mid])
{
beg=mid+1;
}
else
{
end=mid-1;
}
}
return -1;
}

 A fast way to search a sorted array is to use a binary search. The idea is to look at the element in the middle. If the key is equal to that, the search is finished. If the key is less than the middle element, do a binary search on the first half. If it's greater, do a binary search of the second half.

Algorithm

Algorithm is quite simple. It can be done either recursively or iteratively:

1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:
   • searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
   • searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

Now we should define, when iterations should stop. First case is when searched element is found. Second one is when sub array has no elements. In this case, we can conclude, that searched value doesn't present in the array.

 // program for binary search.
 // program for binary search.

PROGRAM FOR LINEAR SEARCH

program for linear search
#include<iostream.h>
#include<conio.h>
int a[15],i,n,item;
void read();
int lsearch(int [],int,int);
void main()
{
int p;
clrscr();
read();
cout<<"Enter the search element\n";
cin>>item;
p=lsearch(a,n,item);
cout<<"\nElement found at "<<p+1<<" position";
getch();
}
int lsearch(int a[],int n,int item)
{
for(i=0;i<n;i++)
{
if(a[i]==item)
{
break;
}
}
return(i);
}
void read()
{
cout<<"Enter the limit\n";
cin>>n;
cout<<"Enter the numbers\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
}

 In Linear Search the list is searched sequentially and the position is returned if the key element to be searched is available in the list, otherwise -1 is returned.. The search in Linear Search starts at the beginning of an array and move to the end, testing for a match at each item. All the elements preceding the search element are traversed before the search element is traversed. i.e. if the element to be searched is in position 10, all elements form 1-9 are checked before 10.

merge sorting

program for merge sort...
#include<conio.h>
#include<iostream.h>

#include<stdio.h>
void main()
{
int i,j,n,p,m,a[20],b[20],c[40],k;
clrscr();
cout<<"Enter the limit 1\n";
cin>>m;
cout<<"Enter the elements\n"; /* 2 arrays must be in sorted order otherwise you make them sorted..*/
for(i=0;i<m;i++)
{
cin>>a[i];
}
cout<<"Enter the limit 2\n";
cin>>n;
cout<<"Enter the elements\n";
for(j=0;j<n;j++)
{
cin>>b[j];
}
i=0;
j=0;
k=0;
while((i<m)&&(j<n))
{
if(a[i]<=b[j])
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=b[j];
k++;
j++;
}
}
while(i<m)
{
c[k]=a[i];
k++;
i++;
}
while(j<n)
{
c[k]=b[j];
k++;
j++;
}
cout<<"sorted elements\n";
for(i=0;i<n+m;i++)
{
cout<<c[i]<<" ";
}
getch();
}

MERGE SORT

The mergesort algorithm is based on the classical divide-and-conquer paradigm. It operates as follows:

DIVIDE: Partition the n-element sequence to be sorted into two subsequences of n/2 elements each.

CONQUER: Sort the two subsequences recursively using the mergesort.

COMBINE: Merge the two sorted sorted subsequences of size n/2 each to produce the sorted sequence consisting of n elements.

Note that recursion "bottoms out" when the sequence to be sorted is of unit length. Since every sequence of length 1 is in sorted order, no further recursive call is necessary. The key operation of the mergesort algorithm is the merging of the two sorted sequencesin the "combine step". To perform the merging, we use an auxilliary procedure Merge(A,p,q,r), where A is an array and p,q and r are indices numbering elements of the array such that dure assumes that the subarrays A[p..q] and A[q+1...r] are in sorted order.It merges them to form a single sorted subarray that replaces the current subarray A[p..r]. Thus finally,we obtain the sorted array A[1..n], which is the solution.

program for quick sort

c++ program for quick sort..
#include<iostream.h>
#include<conio.h>
int a[50],l,u,i,j,n;
void quick(int a[] ,int,int); function declaration for quiick sort
void main()
{
clrscr();
cout<<"Enter the limit\n";
cin>>n;
cout<<"Enter "<<n<<"  elements\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
l=0;u=n-1;
quick(a,l,u);                // function call for quick sort
cout<<"\n sorted elements are\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
getch();
}
void quick(int a[],int l,int u)              //function definition for quick sort
{
int p,temp;
if(l<u)
{
p=a[l];
i=l;
j=u;
while(i<j)
{
while((a[i]<=p)&&( i<j))
  {
  i++;
  }
  while((a[j]>p)&&(i<j))
  {
  j--;
  }
  if(i<=j)
  {
  temp=a[i];
  a[i]=a[j];
  a[j]=temp;
  }
  }
  temp=a[j];
  a[j]=a[l];
  a[l]=temp;
  if(l!=j-1)
  quick(a,l,j-1);

   if((j+1)!=u)
  quick(a,j+1,u);          //recursive function call

  }
  }

Quick Sort

In some ways the quick sort uses a similar idea to the bubble sort in that it compares items and swaps them if they are out of sequence. However, the idea of the quick sort is to divide the list into smaller lists which can then also be sorted using the quick sort algorithm. This is usually done through recursion. Lists of length 0 are ignored and those of length 1 are considered to be sorted.
Quick sort, like Merge Sort, is a divide-and-conquer sorting algorithm. The premise of quicksort is to separate the "big" elements from the "small" elements repeatedly. The first step of the algorithm requires choosing a "pivot" value that will be used to divide big and small numbers. Each implementation of quicksort has its own method of choosing the pivot value--some methods are much better than others. The implementation below simply uses the first element of the list as the pivot value. Once the pivot value has been selected, all values smaller than the pivot are placed toward the beginning of the set and all the ones larger than the pivot are placed to the right. This process essentially sets the pivot value in the correct place each time. Each side of the pivot is then quicksorted.
Ideally, the pivot would be selected such that it were smaller than about half the elements and larger than about half the elements. Consider the extreme case where either the smallest or the largest value is chosen as the pivot: when quicksort is called recursively on the values on either side of it, one set of data will be empty while the other would be almost as large as the original data set. To improve the efficiency of the sort, there are clever ways to choose the pivot value such that it is extremely unlikely to end up with an extreme value. One such method is to randomly select three numbers from the set of data and set the middle one as the pivot. Though the comparisons make the sort slightly slower, a "good" pivot value can drastically improve the efficiency of quicksort.

1. 1. Pick an element from the table you're sorting. We call this the 'pivot'.
2. 2. Exchange the pivot with the right-most element in the table.
3. 3. Go through the table from both left and right ends; from the left end, search for elements GREATER than the pivot; from the right end, search for elements SMALLER than the pivot.
4. 4. When you find these two elements, exchange them and go on.
5. 5. When the two go-throughs cross, exchange the pivot and the element where the left go-through is pointing.
6. 6. The pivot is on its final place in the table, and to the left there's only elements smaller than it, to the right there's only elements greater than it. Now perform the same process for both sides of the table recursively.

Consider the data set 5 9 3 8 6 4 2 1 7 0. For simplicity, take the first element as the pivot value, in this case the 5. After iterative comparisons, the array has the following arrangement: [0 3 4 2 1 5 8 6 7 9]. Note that all the values to the left of the 5 are smaller and all those to the right are larger. When quicksort is called on the smaller half, the problem of a "bad" pivot value is highlighted. Note that the array of smaller numbers, [ 0 3 4 2 1 ] does not change and the next array that gets quicksorted is practically the same: [ 3 4 2 1 ]. A complete trace of the algorithm follows.
5 9 3 8 6 4 2 1 7 0
Quicksorting subarray: [ 5 9 3 8 6 4 2 1 7 0 ]
Quicksorting subarray: [ 0 3 4 2 1 ]
Quicksorting subarray: [ ]
Quicksorting subarray: [ 3 4 2 1 ]
Quicksorting subarray: [ 1 2 ]
Quicksorting subarray: [ ]
Quicksorting subarray: [ 2 ]
Quicksorting subarray: [ 4 ]
Quicksorting subarray: [ 8 6 7 9 ]
Quicksorting subarray: [ 7 6 ]
Quicksorting subarray: [ 6 ]
Quicksorting subarray: [ ]
Quicksorting subarray: [ 9 ]
0 1 2 3 4 5 6 7 8 9

program for selection sort

c++program for selection sort..
#include<conio.h>
#include<iostream.h>

#include<stdio.h>
void main()
{
int i,j,n,p,a[20],s,t;
clrscr();
cout<<"Enter the limit\n";
cin>>n;
cout<<"Enter the elements\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}

for(i=0;i<n;i++)
 {
 s=a[i];
 p=i;
 for(j=i+1;j<n;j++)
 {
 if(a[j]<s)
  {
  s=a[j];
  p=j;
  }
 }

  t=a[p];
  a[p]=a[i];
  a[i]=t;

  }

for(i=0;i<n;i++)
  {
  cout<<a[i]<<"  ";
  }


getch();
}

The Selection Sort Algorithm

Like bubble sort, selection sort is implemented with one loop nested inside another. This suggests that the efficiency of selection sort, like bubble sort, is n ² . To understand why this is indeed correct, consider how many comparisons must take place. The first iteration through the data require n - 1 comparisons to find the minimum value to swap into the first position. Because the first position can then be ignored when finding the next smallest value, the second iteration requires n - 2 comparisons and third requires n - 3 . This progression continues as follows:
(n - 1) + (n - 2) + ... +2 + 1 = n(n - 1)/2 = O(n ²)
Unlike other quadratic tests, the efficiency of selection sort is independent of the data. Bubble sort, for example, can sort sorted and some nearly-sorted lists in linear time because it is able to identify when it has a sorted list. Selection sort does not do anything like that because it is only seeking the minimum value on each iteration. Therefore, it cannot recognize (on the first iteration) the difference between the following two sets of data: 1 2 3 4 5 6 7 8 9 and 1 9 8 7 6 5 4 3 2. In each case, it will identify the 1 as the smallest element and then go on to sorting the rest of the list. Because it treats all data sets the same and has no ability to short-circuit the rest of the sort if it ever comes across a sorted list before the algorithm is complete, insertion sort has no best or worst cases. Selection sort always takes O(n ²) operations, regardless of the characteristics of the data being sorted.

program for insertion sort

c++ program for insertion sort..
#include<conio.h>
#include<iostream.h>

#include<stdio.h>
void main()
{
int i,j,t,n=4,a[15],k;
clrscr();
cout<<"Enter the elements\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}

for(i=1;i<n;i++)
 {
 j=i;
 for(j=0;j<i;j++)
  {
     if(a[i]<a[j])
     {
     t=a[i];

     for(k=i;k>j;k--)
       {
       a[k]=a[k-1];
       }
       a[k]=t;
     }
  }
  }
  for(i=0;i<n;i++)
  {
  cout<<a[i]<<"  ";
  }


getch();
}

Insertion Sort

The insertion sort algorithm is the sort unknowingly used by most card players when sorting the cards in their hands. When holding a hand of cards, players will often scan their cards from left to right, looking for the first card that is out of place. For example, if the first three cards of a player's hand are 4, 5, 2, he will often be satisfied that the 4 and the 5 are in order relative to each other, but, upon getting to the 2, desires to place it before the 4 and the 5. In that case, the player typically removes the 2 from the list, shifts the 4 and the 5 one spot to the right, and then places the 2 into the first slot on the left. This is insertion sort. Unlike other simple sorts like selection sort and bubble sort which rely primarily on comparing and swapping, the insertion sort achieves a sorted data set by identifying an element that out of order relative to the elements around it, removing it from the list, shifting elements up one place and then placing the removed element in its correct location. Follow the step by step process of sorting the following small list.

• (4) 3 1 2 --> The four is in the correct place relative to the elements that have been
• considered to this point.
• (4 3) 1 2 --> The four and the three are incorrectly placed relative to one another, so remove and shift
• (4 _) 1 2 --> Remove the 3 from the list
• (_ 4) 1 2 --> shift the four into the relative correct place
• (3 4) 1 2 --> Now the sublist that was being considered is in sorted order
• (3) 4 1 2 --> The three is in sorted order relative to the data before it
• (3 4) 1 2 --> The three and the four are in sorted order relative to the data before it
• (3 4 1) 2 --> The 3, 4, and 1 are not in sorted order, so remove and shift
• (3 4 _) 2 --> Remove the 1
• (3 _ 4) 2 --> Shift the 4 up one place
• (_ 3 4) 2 --> Shift the 3 into its relatively correct place
• (1 3 4) 2 --> Place the one such that the sublist being considered is in sorted order
• (1) 3 4 2 --> (1) is a sorted list
• (1 3) 4 2 --> (1 3) is a sorted list
• (1 3 4) 2 --> (1 3 4) is a sorted list
• (1 3 4 2) --> The two is out of order, so remove and shift
• (1 3 4 _) --> Remove the 2
• (1 3 _ 4) --> Shift the 4
• (1 _ 3 4) --> Shift the 3
• (1 2 3 4) --> Place the 2 into its correct place
• (1) 2 3 4 --> (1) is a sorted list
• (1 2) 3 4 --> (1 2) is a sorted list
• (1 2 3) 4 --> (1 2 3) is a sorted list
• (1 2 3 4) --> (1 2 3 4) is a sorted list, sort complete.

With a larger data set, it is even easier to see the sorted sublist growing in size with each successive iteration. Note that after each iteration, the size of the sorted data at the beginning of the list grows by one.

8 9 3 5 6 4 2 1 7 0
3 8 9 5 6 4 2 1 7 0
3 5 8 9 6 4 2 1 7 0
3 5 6 8 9 4 2 1 7 0
3 4 5 6 8 9 2 1 7 0
2 3 4 5 6 8 9 1 7 0
1 2 3 4 5 6 8 9 7 0
1 2 3 4 5 6 7 8 9 0
0 1 2 3 4 5 6 7 8 9