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	bearsoft	1.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