Classes/Sort/ArrayQuickSort.cpp

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

ArrayQuickSort::ArrayQuickSort()
{
}

ArrayQuickSort::~ArrayQuickSort()
{
}


static int statement;

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

//      quicksort(array,0,numberof-1);

int ArrayQuickSort::partitionOrder(int *list, int start, int top)
{
    int pivot = list[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)
                        {
                    if (list[bottom] < pivot)
                                {                                                                       // Is the bottom out of place?
                        list[top] = list[bottom];       // Then put at the top... 6=7
                        break;
                                }                               // ... and start searching from the top.
                        }
                        else
                        {
                    if (list[bottom] > pivot)
                                {                                                                       // Is the bottom out of place?
                        list[top] = list[bottom];       // 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)
                        {
                                if (list[top] > pivot)             // Is the top out of place?
                                {
                                        list[bottom] = list[top];       // Then put it at the bottom...
                                    break;                                                      
                                }                                       // ...and start searching from the bottom.
                        }
                        else
                        {
                                if (list[top] < pivot)             // Is the top out of place?
                                {
                                        list[bottom] = list[top];       // Then put it at the bottom...
                                    break;                                                      
                                }                                       // ...and start searching from the bottom.
                        }
                }
        }
                
        list[top] = pivot;                          // Put the pivot in its place.
    return top;                                 // Return the split point
}

void ArrayQuickSort::sortLargestOrder(int *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 ArrayQuickSort::sortSmallestOrder(int *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);     

        }
}
                
/////////////////////////////////////////////////////////////////
// string sorting
/////////////////////////////////////////////////////////////////

int ArrayQuickSort::partitionStringOrder(String **list, int start, int top)
{
        StringTools stringTools;

    String *pivot = list[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)
                        {
                                String *string=list[bottom];
                                String *string2=pivot;

                                if (stringTools.isStringSmaller(string->buffer,string->length,string2->buffer,string2->length))
                                {                                                                       // Is the bottom out of place?
                        list[top] = list[bottom];       // Then put at the top... 6=7
                        break;
                                }                               // ... and start searching from the top.
                        }
                        else
                        {
                                String *string=list[bottom];
                                String *string2=pivot;

                                if (stringTools.isStringLarger(string->buffer,string->length,string2->buffer,string2->length))
                                {                                                                       // Is the bottom out of place?
                        list[top] = list[bottom];       // 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)
                        {
                                String *string=list[top];
                                String *string2=pivot;

                                if (stringTools.isStringLarger(string->buffer,string->length,string2->buffer,string2->length))
                                {
                                        list[bottom] = list[top];       // Then put it at the bottom...
                                    break;                                                      
                                }                                       // ...and start searching from the bottom.
                        }
                        else
                        {
                                String *string=list[top];
                                String *string2=pivot;

                                if (stringTools.isStringSmaller(string->buffer,string->length,string2->buffer,string2->length))
                                {
                                        list[bottom] = list[top];       // Then put it at the bottom...
                                    break;                                                      
                                }                                       // ...and start searching from the bottom.
                        }
                }
        }
                
        list[top] = pivot;                          // Put the pivot in its place.
    return top;                                 // Return the split point
}

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

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

        }
}
1	bearsoft	1.1	#include "ArrayQuickSort.h"
2			#include "../String/StringTools.h"
3			#include "../String/String.h"
4			#include "../System/SystemDefine.h"
5
6			ArrayQuickSort::ArrayQuickSort()
7			{
8			}
9
10			ArrayQuickSort::~ArrayQuickSort()
11			{
12			}
13
14
15
16
17			static int statement;
18
19			void ArrayQuickSort::setStatement(int iStatement)
20			{
21			statement=iStatement;
22			}
23
24			// quicksort(array,0,numberof-1);
25
26			int ArrayQuickSort::partitionOrder(int *list, int start, int top)
27			{
28			int pivot = list[top]; // Partition around the last value
29			int bottom = start-1; // Start outside the area to be partitioned
30			bool done=true;
31
32			while (done) // Until all elements are partitioned...
33			{
34			while (done) // Until we find an out of place element...
35			{
36			bottom++; // ... move the bottom up.
37			if (bottom == top) // If we hit the top...
38			{
39			done = false; // ... we are done.
40			break;
41			}
42
43			if (statement==0)
44			{
45			if (list[bottom] < pivot)
46			{ // Is the bottom out of place?
47			list[top] = list[bottom]; // Then put at the top... 6=7
48			break;
49			} // ... and start searching from the top.
50			}
51			else
52			{
53			if (list[bottom] > pivot)
54			{ // Is the bottom out of place?
55			list[top] = list[bottom]; // Then put at the top... 6=7
56			break;
57			} // ... and start searching from the top.
58			}
59			}
60
61			while (done) // Until we find an out of place element...
62			{
63			--top; // ... move the top down.
64
65			if (top == bottom) // If we hit the bottom...
66			{
67			done = false; // ... we are done.
68			break;
69			}
70
71			if (statement==0)
72			{
73			if (list[top] > pivot) // Is the top out of place?
74			{
75			list[bottom] = list[top]; // Then put it at the bottom...
76			break;
77			} // ...and start searching from the bottom.
78			}
79			else
80			{
81			if (list[top] < pivot) // Is the top out of place?
82			{
83			list[bottom] = list[top]; // Then put it at the bottom...
84			break;
85			} // ...and start searching from the bottom.
86			}
87			}
88			}
89
90			list[top] = pivot; // Put the pivot in its place.
91			return top; // Return the split point
92			}
93
94			void ArrayQuickSort::sortLargestOrder(int *list, int start, int end)
95			{
96			if ( start < end )
97			{ // If there are two or more elements...
98			int split = partitionOrder(list, start, end); //... partition the sublist...
99			sortLargestOrder(list, start, split-1); // ... and sort both halves.
100			sortLargestOrder(list, split+1, end);
101			}
102			}
103
104			void ArrayQuickSort::sortSmallestOrder(int *list, int start, int end)
105			{
106			if ( start < end )
107			{ // If there are two or more elements...
108			int split = partitionOrder(list,start,end); //... partition the sublist...
109			sortSmallestOrder(list, start, split-1 ); // ... and sort both halves.
110			sortSmallestOrder(list, split+1, end);
111
112			}
113			}
114
115			/////////////////////////////////////////////////////////////////
116			// string sorting
117			/////////////////////////////////////////////////////////////////
118
119			int ArrayQuickSort::partitionStringOrder(String **list, int start, int top)
120			{
121			StringTools stringTools;
122
123			String *pivot = list[top]; // Partition around the last value
124			int bottom = start-1; // Start outside the area to be partitioned
125			bool done=true;
126
127			while (done) // Until all elements are partitioned...
128			{
129			while (done) // Until we find an out of place element...
130			{
131			bottom++; // ... move the bottom up.
132			if (bottom == top) // If we hit the top...
133			{
134			done = false; // ... we are done.
135			break;
136			}
137
138			if (statement==0)
139			{
140			String *string=list[bottom];
141			String *string2=pivot;
142
143			if (stringTools.isStringSmaller(string->buffer,string->length,string2->buffer,string2->length))
144			{ // Is the bottom out of place?
145			list[top] = list[bottom]; // Then put at the top... 6=7
146			break;
147			} // ... and start searching from the top.
148			}
149			else
150			{
151			String *string=list[bottom];
152			String *string2=pivot;
153
154			if (stringTools.isStringLarger(string->buffer,string->length,string2->buffer,string2->length))
155			{ // Is the bottom out of place?
156			list[top] = list[bottom]; // Then put at the top... 6=7
157			break;
158			} // ... and start searching from the top.
159			}
160			}
161
162			while (done) // Until we find an out of place element...
163			{
164			--top; // ... move the top down.
165
166			if (top == bottom) // If we hit the bottom...
167			{
168			done = false; // ... we are done.
169			break;
170			}
171
172			if (statement==0)
173			{
174			String *string=list[top];
175			String *string2=pivot;
176
177			if (stringTools.isStringLarger(string->buffer,string->length,string2->buffer,string2->length))
178			{
179			list[bottom] = list[top]; // Then put it at the bottom...
180			break;
181			} // ...and start searching from the bottom.
182			}
183			else
184			{
185			String *string=list[top];
186			String *string2=pivot;
187
188			if (stringTools.isStringSmaller(string->buffer,string->length,string2->buffer,string2->length))
189			{
190			list[bottom] = list[top]; // Then put it at the bottom...
191			break;
192			} // ...and start searching from the bottom.
193			}
194			}
195			}
196
197			list[top] = pivot; // Put the pivot in its place.
198			return top; // Return the split point
199			}
200
201			void ArrayQuickSort::sortLargestStringOrder(String **list, int start, int end)
202			{
203			if ( start < end )
204			{ // If there are two or more elements...
205			int split = partitionStringOrder(list, start, end); //... partition the sublist...
206			sortLargestStringOrder(list, start, split-1); // ... and sort both halves.
207			sortLargestStringOrder(list, split+1, end);
208			}
209			}
210
211			void ArrayQuickSort::sortSmallestStringOrder(String **list, int start, int end)
212			{
213			if ( start < end )
214			{ // If there are two or more elements...
215			int split = partitionStringOrder(list,start,end); //... partition the sublist...
216			sortSmallestStringOrder(list, start, split-1 ); // ... and sort both halves.
217			sortSmallestStringOrder(list, split+1, end);
218
219			}
220			}