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