dlinkedListSorting.cpp

/******************************
    dlinkedListSorting.cpp
    Auther:Syed Zain Ul hasan
  *****************************/

#include <iostream>
#include <stdlib.h>
using namespace std;

class Node          //Node class.
{
public:

    int data;
    Node* next;
    Node* previous;


    Node(int val)          //default constructor to initialize value of "data".
    {

        data = val;
        next = previous = NULL;
    }


};





class DLinkList
{
private:


    Node* first;           // first object to point starting point of linked list
    Node* last;            // last object to point ending point of linked list

public:

    DLinkList()
    {
        first = last = NULL;      //  at the beginning when linked list is empty.
    }




    /** Push Function.
     *
     *  1-A new Node is created.
     *  2-If Linked List is Empty then set new Node as first Node.
     *  3-Traverse through Linked List and reach at the end of list.
     *  4-Insert new Node.
     *
     *
     **/

    void push(int val)

    {
        Node* tmp = new Node(val);


        if(first == NULL)
        {
            tmp->next = NULL;
            tmp->previous = NULL;
            first = last = tmp;
        }
        else
        {

            last->next = tmp;
            tmp->previous = last;
            tmp->next = NULL;
            last = tmp;
        }
    }



    /**
     * POP Function.
    *
    * 1-Traverse through Linked List and reach at the end of list.
    * 2-Delete Last Node.
    * 3-Set Second last Node as last Node.
    *
    **/


    void pop()
    {
        if(first != NULL)
        {
            Node* tmp = last;
            last = last->previous;
            last->next = NULL;
            delete tmp;
        }
    }

    /**
     * Display Function
     *
     * 1-Traverse through Linked List and display value of data in every Node.
     *
     */
    void display()
    {
        Node* tmp = first;
        cout << "Linked List ";
        while(tmp != NULL)
        {
            cout << tmp->data << " ";
            tmp = tmp->next;
        }
        cout << endl;
    }


    /**
     * Bubble Sort Function.
     *
     *  1-A new Node is created and assigned address of first Node.
     *  2-Traverse through Linked List and reach at the end of list.
     *  3-Compare data of two Nodes.
     *  4-If the value of first  is grater then the value of
     *   second and swap them.
     *  5-Repeat steps unit Linked List is sorted.
     *
     */


    void BubbleSort()
    {

        Node *tmp = first;

        while(tmp->next != NULL)
        {

            if(tmp->data > tmp->next->data)
            {

                swap(tmp->data, tmp->next->data);

                BubbleSort();
            }

            tmp = tmp->next;

        }
    }




    /**
     * Selection Sort Function.
     *
     * 1-A new Node is created and assigned address of first Node.
     * 2-Divide Linked List into tow parts sorted and unsorted.
     * 3-Suppose that first element in Linked List is sorted and other is
     *   unsorted.
     * 4-Traverse through Linked List and compare sorted part with unsorted part.
     *   If value of unsorted part is less then sorted part then note the position
     *   of that element and swap then after pass is complete.
     */

    void SelectionSort()
    {

        Node* i = first;
        while(i != NULL)
        {
            Node* min = i;

            Node* j = i->next;
            while(j != NULL)
            {
                if(min->data > j->data)
                    min = j;
                j = j->next;
            }

            swap(i->data, min->data);
            i = i->next;
        }
    }


    /**
     * There is only one difference between Selection sort and insertion sort
     * selection sort compare sorted and unsorted elements in forward direction
     * but insertion sort in backward direction.
     */


    void InsertionSort()
    {

        Node *i = first->next;
        Node *j;

        while(i != NULL)
        {


            j = i;

            while(j != first && j->previous->data > j->data)
            {

                swap(j->previous->data , j->data);
                j = j->previous;
            }

            i = i->next;
        }

    }

};

int main()
{
    DLinkList d;            //Creating Object of DLinkList class.
    int choice;


    d.push(5);              //Inserting some random values in Linked List.
    d.push(7);
    d.push(51);
    d.push(52);
    d.push(533);
    d.push(15);
    d.push(65);
    d.push(775);
    d.push(75);
    d.push(25);
    d.display();
    cout << endl;

    cout << "1 - Bubble Sort" << endl
         << "2 - Insertion Sort" << endl
         << "3 - Selection Sort" << endl;
    int tmp;
    cin >> tmp;


    switch(tmp)
    {
    case 1:
        d.BubbleSort();
        break;

    case 2:
        d.InsertionSort();
        break;
    case 3:
        d.SelectionSort();
        break;
    default:

        cout << "Wrong choice" << endl;
        break;
    }


    d.display();






    system("pause");
    return 0;
}