• 1

• 11.9k
• 1
• 20
• 46

• 11.9k
• 1
• 20
• 46

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.