//radix sort method for link list. (click here to go link list)

void List::radixSort(){
    //find max;
    Node *max = FirstItem;
    Node *temp = FirstItem;

    while( temp != NULL){
        if(temp->data > max->data ){
            max = temp;
        }
        temp = temp->next
    }

    //convert int to string
    string s;
    std::stringstream out;
    out << max->data;
    s = out.str();

    int digit = s.length();
    List a[10];    

    int divider;
    int tempi;

    for(int i = 0; i < digit; i++){
        temp = FirstItem;
        while(temp != NULL){
            divider = pow(10.0,(double)i);
            tempi = (temp->data / divider) % 10
            a[tempi].AddListItem(temp->data)
            temp = temp->next;
        }
        deletion();
        for(int i = 0; i < 10; i++)
            while(a[i].FirstItem != NULL){
                AddListItem(a[i].FirstItem->data);
                a[i].FirstItem = (a[i].FirstItem)->next;
            }
        }
    }
}

//insertion sort method for link list. (click here to go link list)

void List::insertionSort(){
     Node *current;
     Node *nextCurrent;
     Node *temp;
     current = FirstItem->next;
     bool test = false;

     for(int i = 1; i < length; i++){
         temp = FirstItem;
         while(temp != current){
             nextCurrent = current->next;
             if(current->data < temp->data){
                 if(temp == FirstItem){
                     (current->prev)->next = current->next;
                     if(nextCurrent != NULL)
                     nextCurrent->prev = current->prev;
                     FirstItem = current;
                     current->prev = NULL;
                     current->next = temp;
                     temp->prev = current;
                 }
                 else{
                     (current->prev)->next = current->next;
                     if(nextCurrent != NULL)
                     nextCurrent->prev = current->prev;
                     (temp->prev)->next = current;
                     current->prev = temp->prev;
                     current->next = temp;
                     temp->prev = current;
                 }
                 test = true;
             } 

             temp = temp->next;
             if(test){
                 temp = current;
             }
         }
         test = false;
         current = nextCurrent;
     }
}

//quick sort method for link list. (click here to go link list)

void List::QuickSortList(Node *left, Node *right){
    Node *pivot;
    Node *lastS1;
    Node *lastUnknown;
    int temp;

    pivot = left;
    lastS1 = left;
    lastUnknown = left->next;

    if (left == right || left->prev == right) return;

    while(lastUnknown != right){
        if(lastUnknown->data < pivot->data){
            lastS1 = lastS1->next;
            temp = lastUnknown->data;
            lastUnknown->data = lastS1->data;
            lastS1->data = temp;
        }
        lastUnknown = lastUnknown->next;
    }

    if(lastUnknown->data < pivot->data){
        lastS1 = lastS1->next;
        temp = lastUnknown->data;
        lastUnknown->data = lastS1->data;
        lastS1->data = temp;
    }

    temp = pivot->data;
    pivot->data = lastS1->data;
    lastS1->data = temp;

    if(lastS1->prev != NULL)
        QuickSortList(left, lastS1->prev);
    if(lastS1->next != NULL)
        QuickSortList(lastS1->next, right);

}

//List.h

#include <stdio.h>
#include <cstdlib>
#include <iostream>

using namespace std;

class List{
    private:
        struct Node
        {
            int data;

            Node *prev;
	    Node *next;
        }; 

    public:
        Node *FirstItem;
        Node *LastItem;
        int length;

        List();
        ~List();
        void deletion();
        void AddListItem(int value);
        void PrintList();
        void QuickSortList(Node *left, Node *right);
        void insertionSort();
        void radixSort();   

};

//-----------------------------------------------------------------//
//-----------------------------------------------------------------//

//List.cpp

#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <cmath>
#include "List.h"

List::List(){
    FirstItem = NULL;
    LastItem = NULL;
    length = 0;
}

List::~List(){
    deletion();
}

void List::deletion(){
    Node *delItem;
    Node *item = FirstItem;

    while (item != NULL){
        delItem = item;
        item = item->next;
        delete delItem;
    }

    FirstItem = NULL;
    LastItem = NULL;
}

void List::AddListItem(int value){
    Node *item = new Node;
    item->data = value;

    if (FirstItem == NULL){
        FirstItem = item;
        LastItem = item;
        item->next = NULL;
        item->prev = NULL;
    }
    else{
        LastItem->next = item;
        item->prev = LastItem;
        LastItem = item;
        item->next = NULL;
    }
    length++;
}

void List::PrintList(){
    Node *pItem = FirstItem;
    while (pItem != NULL){
        cout << pItem->data << endl;
        pItem = pItem->next;
    }
}

void List::QuickSortList(Node *left, Node *right){
    (click here to go quick sort method)
}

void List::insertionSort(){
    (click here to go insertion sort method)
}

void List::radixSort(){
    (click here to go radix sort method)
}

//fcn.h
#include <cstdlib>
#include <iostream>

void quickSort(int*& a, int start, int end);
int partition(int*& a, int start, int end);
void sort(int*& a, int e1, int e2);

//------------------------------------------------------//
//------------------------------------------------------//

//fcn.cpp
#include <cstdlib>
#include <iostream>
#include "fcn.h"

using namespace std;

void swap(int*& a, int e1, int e2){
     int temp = a[e1];
     a[e1] = a[e2];
     a[e2] = temp;
}

int partition(int*& a, int start, int end){
     int pivot = a[start];
     int s1 = start;
     int fu = start + 1;
     end++;
     while(fu != end){
          if(a[fu] < pivot){
               swap(a, fu, s1 + 1);
               s1++;
          }
          fu++;
     }
     swap(a, s1, start);
     return s1;
}

void quickSort(int*& a, int start, int end){
     if(start < end){
          int middle = partition(a, start, end);
          quickSort(a, start, middle - 1);
          quickSort(a, middle + 1, end);
     }
}

//------------------------------------------------------//
//------------------------------------------------------//

//main.cpp  for testing

#include <cstdlib>
#include <iostream>
#include "fcn.h"

using namespace std;

int main(int argc, char *argv[])
{
     int* a = new int[6];
     a[0] = 9;
     a[1] = 1;
     a[2] = 3;
     a[3] = 6;
     a[4] = 5;
     a[5] = 4;

     quickSort(a,0,5);

     for(int i = 0; i < 6; i++){
          cout << a[i] << endl;
     }

     system("PAUSE");
     return EXIT_SUCCESS;
}

//------------------------------------------------------//
//------------------------------------------------------//

//how algorithm works (click the picture for larger image)

#include <sstream>

//convert string to double

string str;
double number;
str = “16.2″
number = atof(str.c_str());

//convert double to string

result = 16.2;   string s;
std::ostringstream ss;
ss << result;
s = ss.str();

//convert int to string

i = 5;
string s;
std::stringstream out;
out << i;
s = out.str();

//convert string to int

string str;
double number;
str = “16″
number = atoi(str.c_str());