Classes/Sort/StringLinkedListQuickSort.cpp

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

StringLinkedListQuickSort::StringLinkedListQuickSort()
{
}

StringLinkedListQuickSort::~StringLinkedListQuickSort()
{
}

static int statement;

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

/////////////////////////////////////////////////////////////////
// string sorting
/////////////////////////////////////////////////////////////////

int StringLinkedListQuickSort::partitionOrder(StringLinkedList *list, int start, int top)
{

        StringTools stringTools;
    
        String pivot = list->getElement(top);
    char *pivotBuffer = (char*)pivot.buffer;               // Partition around the last value
        int pivotLength=pivot.length;
 
        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)
                        {
                                char *stringBuffer=list->getElement(bottom);
                                int stringLength=list->stringLength;

                                if (stringTools.isStringSmaller(stringBuffer,stringLength,pivotBuffer,pivotLength))
                                {       
                                        list->setElement(stringBuffer,stringLength,top);      // Then put at the top... 6=7
                                break;
                                }                               // ... and start searching from the top.
                        }
                        else
                        {
                                char *stringBuffer=list->getElement(bottom);
                                int stringLength=list->stringLength;

                                if (stringTools.isStringLarger(stringBuffer,stringLength,pivotBuffer,pivotLength))
                                {                                                                       // Is the bottom out of place?
                                        list->setElement(stringBuffer,stringLength,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)
                        {
                                char *stringBuffer=list->getElement(top);
                                int stringLength=list->stringLength;

                                if (stringTools.isStringLarger(stringBuffer,stringLength,pivotBuffer,pivotLength))
                                {
                                        list->setElement(stringBuffer,stringLength,bottom);      // Then put it at the bottom...
                                    break;                                                      
                                }                                       // ...and start searching from the bottom.
                        }
                        else
                        {
                                char *stringBuffer=list->getElement(top);
                                int stringLength=list->stringLength;

                                if (stringTools.isStringSmaller(stringBuffer,stringLength,pivotBuffer,pivotLength))
                                {
                                        list->setElement(stringBuffer,stringLength,bottom);      // Then put it at the bottom...
                                    break;                                                      
                                }                                       // ...and start searching from the bottom.
                        }
                }
        }
                
        list->setElement(pivotBuffer,pivotLength,top);    // Put the pivot in its place.
    return top;                                 // Return the split point
}

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