Classes/Sort/IntLinkedListQuickSort.cpp

#include "IntLinkedListQuickSort.h"
#include "../String/StringTools.h"
#include "../String/String.h"
#include "../System/SystemDefine.h"

IntLinkedListQuickSort::IntLinkedListQuickSort()
{
}

IntLinkedListQuickSort::~IntLinkedListQuickSort()
{
}

static int statement;

void IntLinkedListQuickSort::setStatement(int iStatement)
{
        statement=iStatement;
}

int IntLinkedListQuickSort::partitionOrder(IntLinkedList *list, int start, int top)
{
    int pivot = list->getElement(top);                          // Partition around the last value
    int bottom = start-1;                           // Start outside the area to be partitioned
    bool done=true;

        while (done)                            // Until all elements are partitioned...
    {
                while (done)                        // Until we find an out of place element...
                {
                        bottom++;                       // ... move the bottom up.
            if (bottom == top)                  // If we hit the top...
            {
                                done = false;                       // ... we are done.
                break;
                        }
                        
                        if (statement==0)
                        {
                                int element=list->getElement(bottom);
                                        
                    if ( element < pivot)
                                {                                                                       // Is the bottom out of place?
                        list->setElement(element,top);      // Then put at the top... 6=7
                        break;
                                }                               // ... and start searching from the top.
                        }
                        else
                        {
                                int element=list->getElement(bottom);
                    if ( element > pivot)
                                {                                                                       // Is the bottom out of place?
                        list->setElement(element,top);  // Then put at the top... 6=7
                        break;
                                }                               // ... and start searching from the top.
                        }
                }

                while (done)                        // Until we find an out of place element...
        {
                        --top;                        // ... move the top down.
            
            if (top == bottom)                  // If we hit the bottom...
            {
                                done = false;                       // ... we are done.
                break;
                        }

                        if (statement==0)
                        {
                                int element=list->getElement(top);

                                if ( element > pivot)             // Is the top out of place?
                                {
                                        list->setElement(element,bottom); 
                                        break;                                                  
                                }                                       // ...and start searching from the bottom.
                        }
                        else
                        {
                                int element=list->getElement(top);

                                if (element < pivot)             // Is the top out of place?
                                {
                                        list->setElement(element,bottom); 
                                    break;                                                      
                                }                                       // ...and start searching from the bottom.
                        }
                }
        }
                
        list->setElement(pivot,top);                        // Put the pivot in its place.
    return top;                                 // Return the split point
}

void IntLinkedListQuickSort::sortLargestOrder(IntLinkedList *list, int start, int end)
{
        if ( start < end )
        {                                                                                       // If there are two or more elements...
        int split = partitionOrder(list, start, end);    //... partition the sublist...
        sortLargestOrder(list, start, split-1);        // ... and sort both halves.
        sortLargestOrder(list, split+1, end);     
        }
}

void IntLinkedListQuickSort::sortSmallestOrder(IntLinkedList *list, int start, int end)
{
        if ( start < end )
        {                                                                                       // If there are two or more elements...
        int split = partitionOrder(list,start,end);    //... partition the sublist...
        sortSmallestOrder(list, start, split-1 );        // ... and sort both halves.
        sortSmallestOrder(list, split+1, end);     

        }
}
                
1	#include "IntLinkedListQuickSort.h"
2	#include "../String/StringTools.h"
3	#include "../String/String.h"
4	#include "../System/SystemDefine.h"
5
6	IntLinkedListQuickSort::IntLinkedListQuickSort()
7	{
8	}
9
10	IntLinkedListQuickSort::~IntLinkedListQuickSort()
11	{
12	}
13
14	static int statement;
15
16	void IntLinkedListQuickSort::setStatement(int iStatement)
17	{
18	statement=iStatement;
19	}
20
21	int IntLinkedListQuickSort::partitionOrder(IntLinkedList *list, int start, int top)
22	{
23	int pivot = list->getElement(top); // Partition around the last value
24	int bottom = start-1; // Start outside the area to be partitioned
25	bool done=true;
26
27	while (done) // Until all elements are partitioned...
28	{
29	while (done) // Until we find an out of place element...
30	{
31	bottom++; // ... move the bottom up.
32	if (bottom == top) // If we hit the top...
33	{
34	done = false; // ... we are done.
35	break;
36	}
37
38	if (statement==0)
39	{
40	int element=list->getElement(bottom);
41
42	if ( element < pivot)
43	{ // Is the bottom out of place?
44	list->setElement(element,top); // Then put at the top... 6=7
45	break;
46	} // ... and start searching from the top.
47	}
48	else
49	{
50	int element=list->getElement(bottom);
51	if ( element > pivot)
52	{ // Is the bottom out of place?
53	list->setElement(element,top); // Then put at the top... 6=7
54	break;
55	} // ... and start searching from the top.
56	}
57	}
58
59	while (done) // Until we find an out of place element...
60	{
61	--top; // ... move the top down.
62
63	if (top == bottom) // If we hit the bottom...
64	{
65	done = false; // ... we are done.
66	break;
67	}
68
69	if (statement==0)
70	{
71	int element=list->getElement(top);
72
73	if ( element > pivot) // Is the top out of place?
74	{
75	list->setElement(element,bottom);
76	break;
77	} // ...and start searching from the bottom.
78	}
79	else
80	{
81	int element=list->getElement(top);
82
83	if (element < pivot) // Is the top out of place?
84	{
85	list->setElement(element,bottom);
86	break;
87	} // ...and start searching from the bottom.
88	}
89	}
90	}
91
92	list->setElement(pivot,top); // Put the pivot in its place.
93	return top; // Return the split point
94	}
95
96	void IntLinkedListQuickSort::sortLargestOrder(IntLinkedList *list, int start, int end)
97	{
98	if ( start < end )
99	{ // If there are two or more elements...
100	int split = partitionOrder(list, start, end); //... partition the sublist...
101	sortLargestOrder(list, start, split-1); // ... and sort both halves.
102	sortLargestOrder(list, split+1, end);
103	}
104	}
105
106	void IntLinkedListQuickSort::sortSmallestOrder(IntLinkedList *list, int start, int end)
107	{
108	if ( start < end )
109	{ // If there are two or more elements...
110	int split = partitionOrder(list,start,end); //... partition the sublist...
111	sortSmallestOrder(list, start, split-1 ); // ... and sort both halves.
112	sortSmallestOrder(list, split+1, end);
113
114	}
115	}
116