QuickSort

[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?

[dhayden]

Should I just give up programming?

You shouldn't give up programming, but it's unrealistic to think that your (or anyone) could program quick sort without any programming knowledge.

You need to start small. Find an online tutorial, a book, or take a class. Some beginner programs that you might try to write (and show up here often) are:
- Let the user enter a set of numbers. Compute and display the average.
- Read set of numbers and print the largest and/or smallest one.
- Given a number, determine if it is prime.
- Compute and print the prime numbers from 1 to 1000.

[Ganado]

Why are you starting a new thread when you asked the same exact questions in a previous thread? We're trying to help, but you're making this hard.

Almost anyone can learn how to program. It might some more time and effort, but you certainly can do it. But you don't learn how to program by implementing quicksort, that is something fairly complicated to do after you already know the basics.

In programming, you need to break up your problem into smaller building blocks that you can then combine. Focus on each building block at a time. dhayden gave some examples (although prime number algorithms are a bit far away from sorting algorithms, both make you think about solving problems in steps). In the other thread, I gave an example of using std::vector, plus I went through the steps of one way to sort arrays (not quicksort).

Learn the basics, learn how to manipulate arrays/vectors, learn the easy, naive way of sorting an array, learn about how functions work, and then try to conquer quicksort.

Your other thread (don't double post, next time)
http://www.cplusplus.com/forum/beginner/235593/

[nearc]

sry I didn't know in which forum to post

[nearc]

You need to start small. Find an online tutorial, a book, or take a class. Some beginner programs that you might try to write

Well I'm no beginner, my last assignment was to make linked list

[dhayden]

Okay, consider implementing this function:

// quicksort the items in vec in the interval [start,stop)
quickSort(vector<int> &vec, size_t start, size_t stop);

Then to quickSort the entire vector:

quickSort(vector<int> &vec) {
    quickSort(vec, 0, vec.size());
}

[nearc]

// quicksort the items in vec in the interval [start,stop)
quickSort(vector<int> &vec, size_t start, size_t stop);
quickSort(vector<int> &vec) {
    quickSort(vec, 0, vec.size());
}

what does &vec do and whats the point of 0?

[dhayden]

&vec means that the parameter is passed by reference. That means that a change to vec inside the function will also change the vector that was passed in.
0 and vec.size() are the start and stop points to sort.

Note that this example declares two separate functions. Even though they have the same name, they are distinct functions. It might be easier to understand if I rename them:

// quicksort the items in vec in the interval [start,stop)
quickSortHelper(vector<int> &vec, size_t start, size_t stop);
quickSort(vector<int> &vec) {
    quickSortHelper(vec, 0, vec.size());
}

[Duthomhas]

At this point, you are really over your head. Programming isn't something you can cram for. You might have to re-take the course.

If you don't care that much about it, then yeah, you can give up. I don't recommend that, though. Learning to program is hard, and takes a lot of time and effort.

You absolutely have to get through the basics before doing something like a quick sort. A quick sort isn't terribly difficult, but it is tricky to get right.

This is an old FAQ that needs to be rewritten to make it easier to follow, but it might help you a bit. Google will have a lot to read on quicksort also.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/

Good luck!