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	#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	}