Thread: change sorting method using polymorphism

  1. #1
    Registered User
    Join Date
    Jul 2003
    Posts
    5

    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;
    }
    Last edited by Forever82; 07-31-2003 at 12:13 PM.

  2. #2

  3. #3
    Registered User
    Join Date
    Jul 2003
    Posts
    7
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. two dimensional array sorting in C/C++
    By George2 in forum C Programming
    Replies: 16
    Last Post: 11-19-2006, 03:17 AM
  2. Reference parameters and calculating change
    By Cstudent2121 in forum C Programming
    Replies: 6
    Last Post: 11-04-2005, 03:19 PM
  3. Change this program so it uses function??
    By stormfront in forum C Programming
    Replies: 8
    Last Post: 11-01-2005, 08:55 AM
  4. Sorting Method
    By silicon in forum C++ Programming
    Replies: 2
    Last Post: 04-18-2005, 10:06 PM
  5. Replies: 2
    Last Post: 09-04-2001, 02:12 PM