Naming
#Naming
II think your variable names could use some work. Why did you choose Wall
? That name just doesn't strike me as useful in this context.
C++
#C++
TheThe only line of code in this that differentiates it from C is the print statement, which I assume is just for debugging. If you #include <utility>
you get some very useful functions. (You'll need to #include <algorithm>
if you're using C++ that pre-dates C++11.) For example, std::swap()
will swap 2 values for you without the need to write out 4 lines of code:
Recursion
#Recursion
AsAs you found, when you have a deeply recursive function, it can eventually eat up the entire stack if you're not careful. Luckily, you can eliminate recursion in many cases. I modified yours to remove the recursion by adding a simple std::queue
and putting the ranges in the queue instead of calling back into the function. First, I made a simple struct
to hold a range of indexes to sort:
#Naming
I think your variable names could use some work. Why did you choose Wall
? That name just doesn't strike me as useful in this context.
#C++
The only line of code in this that differentiates it from C is the print statement, which I assume is just for debugging. If you #include <utility>
you get some very useful functions. (You'll need to #include <algorithm>
if you're using C++ that pre-dates C++11.) For example, std::swap()
will swap 2 values for you without the need to write out 4 lines of code:
#Recursion
As you found, when you have a deeply recursive function, it can eventually eat up the entire stack if you're not careful. Luckily, you can eliminate recursion in many cases. I modified yours to remove the recursion by adding a simple std::queue
and putting the ranges in the queue instead of calling back into the function. First, I made a simple struct
to hold a range of indexes to sort:
Naming
I think your variable names could use some work. Why did you choose Wall
? That name just doesn't strike me as useful in this context.
C++
The only line of code in this that differentiates it from C is the print statement, which I assume is just for debugging. If you #include <utility>
you get some very useful functions. (You'll need to #include <algorithm>
if you're using C++ that pre-dates C++11.) For example, std::swap()
will swap 2 values for you without the need to write out 4 lines of code:
Recursion
As you found, when you have a deeply recursive function, it can eventually eat up the entire stack if you're not careful. Luckily, you can eliminate recursion in many cases. I modified yours to remove the recursion by adding a simple std::queue
and putting the ranges in the queue instead of calling back into the function. First, I made a simple struct
to hold a range of indexes to sort:
#C++
The only line of code in this that differentiates it from C is the print statement, which I assume is just for debugging. If you #include <stdlib.h><utility>
you get some very useful functions. (You'll need to #include <algorithm>
if you're using C++ that pre-dates C++11.) For example, std::swap()
will swap 2 values for you without the need to write out 4 lines of code:
#C++
The only line of code in this that differentiates it from C is the print statement, which I assume is just for debugging. If you #include <stdlib.h>
you get some very useful functions. For example, std::swap()
will swap 2 values for you without the need to write out 4 lines of code:
#C++
The only line of code in this that differentiates it from C is the print statement, which I assume is just for debugging. If you #include <utility>
you get some very useful functions. (You'll need to #include <algorithm>
if you're using C++ that pre-dates C++11.) For example, std::swap()
will swap 2 values for you without the need to write out 4 lines of code:
I think this is fairly impressive. I don't know if I would have done this in-place if I sat down to do this today. That said, I do see a few things you could improve.
#Naming
I think your variable names could use some work. Why did you choose Wall
? That name just doesn't strike me as useful in this context.
I notice that you're mixing capitals and lowercase letters for the first letter of your variables. Typically variables start with a lowercase letter and type names start with an uppercase letter. You don't necessarily have to follow that convention, but you should be consistent.
#C++
The only line of code in this that differentiates it from C is the print statement, which I assume is just for debugging. If you #include <stdlib.h>
you get some very useful functions. For example, std::swap()
will swap 2 values for you without the need to write out 4 lines of code:
std::swap(Array[Wall], Array[index]);
does the same thing as:
int Temp = 0; //Variable used for swaping array members
...
Temp = Array[Wall];
Array[Wall] = Array[Index];
Array[Index] = Temp;
Also, you don't need std::endl
where you've used it. That will flush the buffer which will slow things down. You can simply use:
std::cout << Wall << "\n";
And if you're really paranoid, you can add a single call to:
std::cout << std::endl;
after QuickSort
returns;
#Recursion
As you found, when you have a deeply recursive function, it can eventually eat up the entire stack if you're not careful. Luckily, you can eliminate recursion in many cases. I modified yours to remove the recursion by adding a simple std::queue
and putting the ranges in the queue instead of calling back into the function. First, I made a simple struct
to hold a range of indexes to sort:
struct Range {
int start;
int end;
Range(int newStart, int newEnd) : start(newStart), end(newEnd) {}
};
Then I updated the function to use a std::queue
and the new Range
type:
void QuickSort(int* array, int start, int end)
{
std::queue<Range> queue;
queue.push(Range(start, end));
while(!queue.empty())
{
Range next = queue.front();
queue.pop();
int start = next.start;
int end = next.end;
int Wall = start;
if (start < end)
{
for (int Index = start; Index < end; Index++)
{
if (array[Index] <= array[end])
{
std::swap(array[Wall], array[Index]);
Wall++;
}
}
std::swap(array[end], array[Wall]);
queue.push(Range(start, --Wall));
queue.push(Range(++Wall, end));
}
}
}
I kept most of your code, but used std::swap
and removed the recursion.
To be honest, I didn't think the performance of your version was bad at all. It seemed to work plenty fast for me.