# Thread: change sorting method using polymorphism

1. ## change sorting method using polymorphism

1)what i trying to do is to use polymorphism method on changing the sorting function.
a) how to change bubble sort to insertion sort..??what is insertion sort..never heard of it..
b)how to change sequential search to binary search...including the polymorphism method

#include<iostream.h>

class Array
{
protected:

int box[10];
int i;
int total;
int largest;

int hold;
int key;

public:
void calculation()
{
total=0;
largest=0;

for(i=0;i<10;i++)
{
cout<<"Enter number :";
cin>>box[i];
}
for(i=0;i<10;i++)
{
cout<<"\n"<<box[i];
}
for(i=0;i<10;i++)
{
total=total+box[i];
if(largest<box[i])
largest=box[i];

}
cout<<"\nThe total of numbers: "<<total;

cout<<"\nThe largest number: "<< largest;

}

virtual sort()
{
for( int pass=0;pass<10-1;pass++)
for(i=0;i<10-1;i++)
if(box[i]>box[i+1])
{
hold=box[i];
box[i]=box[i+1];
box[i+1]=hold;
}

cout<<"\nThe ascending number:\n";
for(i=0;i<10;i++)
cout<<box[i];
cout<<endl;
}

virtual search()
{

cout<<"Enter integer search key:"<<endl;
cin>>key;

for(i=0;i<10;i++)
if(box[i]==key)
if(i<10)

cout<<"Integer: "<<key<<" found at array element "<<i<<"\n";

}
};

main()
{
Array t;
t.calculation();
t.sort();
t.search();
return 0;
}

2. Insertion Sort:
This works by having some area where you will put the sorted list, and taking elements one at a time in the unsorted list and placing them in the correct spot in the sorted list.

Example:
Sorted: _ _ _ _
Unsorted: 5 1 3 2

S1: 5 _ _ _
U1: _ 1 3 2

S2: 1 5 _ _
U2: _ _ 3 2

S3: 1 3 5 _
U3: _ _ _ 2

S4: 1 2 3 5
U4: _ _ _ _

Now there are other implementation details to doing this that you can choose between. For example, you could make the algorithm in place (no need for the extra memory of a sorted list) at the cost of some time spent shuffling stuff around. And whether you're using an array or linked list or what not will also effect exactly how details are carried out.

Binary Search:
Nice way to find stuff if it's sorted. A nice way to think of it is that at any time you have a specific range of values you're considering and each step of the way you eliminate half of the remaining.

The loop essentially runs like this:

[code]
int lowerBound = smallest number
int upperBound = largest number
int midValue = "middle value"

While midValue is not what you are looking for {
If midValue is too big,
You went too far.
Set this value to be the new upperBound
Else it is too small,
You've not gone far enough.
Set this value to be the new lowerBound.
midValue = new "middle value"
}

[\code]

I have "middle value" in quotes because this could be any number of things. It could be an average of the two bounds, or it could actually be the element that is half way between the lower and upper elements...

Hope that helps some.

~SK