Classes/Sort/FloatLinkedListQuickSort.cpp

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

FloatLinkedListQuickSort::FloatLinkedListQuickSort()
{
}

FloatLinkedListQuickSort::~FloatLinkedListQuickSort()
{
}

static int statement;

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

int FloatLinkedListQuickSort::partitionOrder(FloatLinkedList *list, int start, int top)
{
    float 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)
                        {
                                float 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
                        {
                                float 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)
                        {
                                float 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
                        {
                                float element=list->getElement(top);

                                if (list->getElement(top) < 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 FloatLinkedListQuickSort::sortLargestOrder(FloatLinkedList *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 FloatLinkedListQuickSort::sortSmallestOrder(FloatLinkedList *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 "FloatLinkedListQuickSort.h"
2			#include "../String/StringTools.h"
3			#include "../String/String.h"
4			#include "../System/SystemDefine.h"
5
6			FloatLinkedListQuickSort::FloatLinkedListQuickSort()
7			{
8			}
9
10			FloatLinkedListQuickSort::~FloatLinkedListQuickSort()
11			{
12			}
13
14			static int statement;
15
16			void FloatLinkedListQuickSort::setStatement(int iStatement)
17			{
18			statement=iStatement;
19			}
20
21			int FloatLinkedListQuickSort::partitionOrder(FloatLinkedList *list, int start, int top)
22			{
23			float 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			float 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			float element=list->getElement(bottom);
51
52			if (element > pivot)
53			{ // Is the bottom out of place?
54			list->setElement(element,top); // Then put at the top... 6=7
55			break;
56			} // ... and start searching from the top.
57			}
58			}
59
60			while (done) // Until we find an out of place element...
61			{
62			--top; // ... move the top down.
63
64			if (top == bottom) // If we hit the bottom...
65			{
66			done = false; // ... we are done.
67			break;
68			}
69
70			if (statement==0)
71			{
72			float element=list->getElement(top);
73
74			if ( element > pivot) // Is the top out of place?
75			{
76			list->setElement(element,bottom);
77			break;
78			} // ...and start searching from the bottom.
79			}
80			else
81			{
82			float element=list->getElement(top);
83
84			if (list->getElement(top) < pivot) // Is the top out of place?
85			{
86			list->setElement(element,bottom);
87			break;
88			} // ...and start searching from the bottom.
89			}
90			}
91			}
92
93			list->setElement(pivot,top); // Put the pivot in its place.
94			return top; // Return the split point
95			}
96
97			void FloatLinkedListQuickSort::sortLargestOrder(FloatLinkedList *list, int start, int end)
98			{
99			if ( start < end )
100			{ // If there are two or more elements...
101			int split = partitionOrder(list, start, end); //... partition the sublist...
102			sortLargestOrder(list, start, split-1); // ... and sort both halves.
103			sortLargestOrder(list, split+1, end);
104			}
105			}
106
107			void FloatLinkedListQuickSort::sortSmallestOrder(FloatLinkedList *list, int start, int end)
108			{
109			if ( start < end )
110			{ // If there are two or more elements...
111			int split = partitionOrder(list,start,end); //... partition the sublist...
112			sortSmallestOrder(list, start, split-1 ); // ... and sort both halves.
113			sortSmallestOrder(list, split+1, end);
114
115			}
116			}
117