Quick Sort Don't know..

[nearc]

Hey, I need to program Quick Sort so it would sort 100,000 unsorted and reverse sorted elements, and time sort speed.
The problem is- I am bad at programing, I don't know what basic knowledge that I will need to program. Will I need vectors or classes (I haven't learned them), I have no vision how code should look. Tried googling but there are no codes, only explanation how algorithm works.
Should I just give up programming?

[Handy Andy]

Hello nearc,

Some options for you is to include the header file <array> to use a "std::array" or the header file <vector> for "std::vector" along with the header file <algorithm> to use "std::sort". Given a choice I would use the vector because it will hold only what you need whereas a "std::array" generally needs to be defined larger than what you actually need.

There are other options that might work better, but that would have to depend on the information that you are storing.

The problem is- I am bad at programing, I don't know what basic knowledge that I will need to program.

You might want to start with the tutorials here http://www.cplusplus.com/doc/tutorial/ One way or the other you need to start with the basics. Without prior programming you need to learn from the start. Jumping into a program with a sort routine with out knowing how to program will make your job harder.

Tried googling but there are no codes, only explanation how algorithm works.

Then I would say that you asked the wrong question because I find lots of code and examples every day.

Should I just give up programming?

Hard to answer that. You have to decide if this is what you want to do and if you want to put the time into learning.

There are always people here willing to help you understand what you did wrong or are having a problem with.

Hope that helps,

Andy

[Ganado]

Learning quicksort should not be the first thing you program. Understanding how quicksort works (and more importantly, why it works so well) is pretty complicated.

Judging by your other post, it sounds you aren't quite sure how any type of sorting works, let alone quicksort.

Before you get overwhelmed by the concept of sorting, you should break things down into smaller parts.
Let's look at this array, {1, 2, 4, 3, 5}. It is not sorted, because 3 > 4, but the 3 comes after 4.
What would you do to sort this? You would simply swap the 3 and of 4.

Do you know how to swap two elements in an array?

scroll down to the bottom of this page for an example of vector
http://en.cppreference.com/w/cpp/container/vector

Here's my example mentioned above, in code

// Example program
#include <iostream>
#include <vector>
#include <algorithm> // swap

int main()
{
    std::vector<int> vec = {1, 2, 4, 3, 5};
    
    // vec[0] is 1
    // vec[1] is 2
    // vec[2] is 4  <-- out of order
    // vec[3] is 3  <-- out of order
    // vec[4] is 5
    
    // We want to swap the 4 and 3
    
    std::swap(vec[2], vec[3]);
    
    // Now, the vector is sorted. Print out out to see for yourself.
    
    for (int element : vec)
    {
        std::cout << element << " ";
    }

}

Now, think about what would happen if multiple pairs of elements are out of order, and not just the {4, 3}?

For example, {4, 1, 5, 2}.
We look through each element, starting at the first one, and looking at consecutive elements. If the next element is smaller than the previous element, we know that we need to do some swapping. Otherwise, if every previous element is smaller than the next element, the array is sorted.

In the example, we start at the beginning of the array, and we see that 1 is less than 4, so we swap 4 and 1.
The array is now {1, 4, 5 2}.
Then, start at the beginning of the array, and iterate up until we see that 2 is less than 5, so let's swap the 5 and 2.
The array is now {1, 4, 2, 5}.
Then, start at the beginning of the array, and iterate up until we see that 2 is less than 4, so leet's swap the 4 and 2.
The array is now {1, 2, 4, 5}.
Finally, start at the beginning of the array, and iterate up, and we will see that every element is not decreasing. The array is sorted.

Note: What I am describing above is not quicksort, but rather a more naive algorithm. But you should understand the simpler algorithms before you conquer quicksort.

But as Andy said, there are plenty of code and pseudo-code examples of quicksort, and other simpler sorting algorithms. Just google "C++ quicksort" if you need to.

[icy1]

nearc wrote:

Hey, I need to program Quick Sort so it would sort 100,000 unsorted and reverse sorted elements, and time sort speed.
The problem is- I am bad at programing, I don't know what basic knowledge that I will need to program.

Hi nearc, if you don't mind me asking -- who's telling you to do this? There are lots of benchmarks and algorithm complexity explanations out there already.

Quicksort is O(n log n) on average, and O(n²) worst case, which I believe is shown in the reverse-sorted input that you mentioned, so we already know the timing without reinventing the wheel.

If this is an exercise in translating algorithm explanation into code, the wiki explanation is pretty straightforward: https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

Try to rewrite that pseudocode and post here if you have issues. I wrote an adaptation of it not too long ago for a linked list.

[nearc]

if you don't mind me asking -- who's telling you to do this

my professor, I need to do this assignment till 05/01

[Thomas1965]

What have you learned so far - loops, recursion, array, vector ?

Should I just give up programming?

I wouldn't go that far. Maybe just give up on this particular course. It's ridiculous if you got such an assignment without prior teaching and instructions.
You don't need a course to just get an assignment and find some solution online.

[nearc]

What have you learned so far - loops, recursion, array, vector ?

Yeah we learned those (I forgot recursion and learned about vectors online). Now we are going through algorithms and dynamic memory.

[Norm Gunderson]

The following links contain information about sequence containers & sorting that you might find informative:

http://www.cplusplus.com/faq/sequences/

http://www.cplusplus.com/faq/sequences/sequencing/sort-stuff/

http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/
(the links to each of the sorting algorithms at the top of the "Sorting Algorithms" page contain handy little animations of how the sorting algorithms work)

This page is for the quicksort algorithm:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/

[Thomas1965]

First step would be to create the two vectors and fill them.
Try to do this first, once you have done this you can worry about the sorting.