Question

Can anyone explain to me how to use quick sort?
for example, an array like this:
1 3 4 6 8 9 4 10 how do you sort it? Thank you :)

Answer 1

https://www.youtube.com/watch?v=y_G9BkAm6B8

Answer 2

what programming language?

Answer 3

just the basic algorithm, like the step

Answer 4

java

Answer 5

http://en.wikipedia.org/wiki/Bubble_sort This may help

Answer 6

mandre's link is very helpful. Have you watched it?

Answer 7

yes, just after watching I got more confused that's why I hope someone can explain it using example array

Answer 8

Okay! So, give me some random numbers, and we'll sort those.

Answer 9

Make one up. It's more tangible that way.

Answer 10

Are you there? I'll help you through it! It'll take some memorization because it's an algorithm. But going through it will help you remember it and hopefully make it make sense.

Answer 11

the random array is in my question

Answer 12

or I can just make a new one that's more random: 3 8 2 7 4 1 9

Answer 13

1 3 4 6 8 9 4 10
Okay, pick any random spot! Just think about the spot, not the number. If you were a computer, it'd waste time looking for the best number.

There are 8 numbers, so just pick a random number from 0 to 7, if you want.

Answer 14

Haha, okay! So, same thing! Pick a random \(spot\).

Answer 15

That's where we'll start.

Answer 16

then 7?

Answer 17

I'm not really sure which one is the best to pick

Answer 18

Okay, the spot where 7 is!
That's the idea. There really IS a great spot to pick, which you'll understand when you've gone through it a time or a few times. But it would take knowing all of the numbers. Rough estimates would be quicker, but they still take some time. (Linear, if you like to talk about that stuff. If not, don't worry.)

So, you just pick a random one and hope for the best. You can modify your own search algorithm any time, or maybe see how the teacher handles this. For now, though, we'll just go with "start at some 'random' place."

Answer 19

So, we're looking at {3 8 2 7 4 1 9} and you want to start with 7. Which seems like a good idea.

Now the next step. We want to compare everything to 7. Specifically.. well.

What we'll do is look at the ends (3 and 9, right now). \(\{\color{blue}3\ 8\ 2\ 7\ 4\ 1\ \color{blue}9\}\)

We want to get everything \(less\ than\) 7 to the left side, and \(more than\) 7 to the right side. If we find another 7, we should put it.. on the left side. Any side works.

Do you understand our goal? Because what comes next is how to achieve it.

Answer 20

I understand that part. But how do you swap them? Like in which case do you swap them?

Answer 21

Good question!
So, start from the left, just because we do that in English.
If it is less than our chosen number, 7, then we want to leave it on that side. So we'll go right to the next number. If it is MORE THAN our 7, we want to get it on the other side. But how? Well, let's look at our numbers.
So we're looking at the 3 in
\(\{\color{red}3\ 8\ 2\ 7\ 4\ 1\ \color{blue}9\}\)
So it's good there, and we move to the next, to see how it is.
\(\{3\ \color{red} 8\ 2\ 7\ 4\ 1\ \color{blue}9\}\)
We don't want it there, so now we will handle this case.

Answer 22

So, that 8 is to the left of the 7, which we want to change. So, let's put it on the right side. But not anywhere! We will wait until we find some bad number on the other side, and swap them. Then we make two corrections at once! :D

Answer 23

So let's look at the right side now. Now we'll look at the blue number.
\(\{\color{red}3\ 8\ 2\ 7\ 4\ 1\ \color{blue}9\}\)
We want these right-side numbers to be greater than our 7, or we'll move them.

Is this alright with you, so far?

Answer 24

yes

Answer 25

Okay! So what do you think we'll do with this 9?

Answer 26

do nothing? because it is already greater than 7

Answer 27

Right! :)
And then what do we want to do? (Hint: we want to look at something else)

Answer 28

ummm... you check 2 on the left side?

Answer 29

Well, that would be the next number on the left side, which is better shown when I use the right graphic.. We're at \(\{3\ \color{red} 8\ 2\ 7\ 4\ 1\ \color{blue}9\}\).

But we found a problem on the left side. So we want to find a problem on the right side so that we can swap them and "kill two birds with one stone."
So, the 9 is okay. But what will we do now?

Answer 30

ok, so 1?

Answer 31

Yes! We move left to the next number, and check it out!
\(\{3\ \color{red} 8\ 2\ 7\ 4\ \color{blue}1\ 9\}\)

So now we want to look at that 1. It's on the right side. If it's greater than 7, that's okay. But it's not. So what will we do now?

(Hint: we found something wrong on the left side, and we want to "kill two birds with one stone.")

Answer 32

so 1<7 and it should be on the left you swap 8 and 1?

Answer 33

RIGHT!!

Answer 34

Now, I'm going to do that swap. I'll keep the colors on there own sides, because we're traveling along those spots.
\(\{3\ \color{red} 1\ 2\ 7\ 4\ \color{blue}8\ 9\}\)

That was our swap. Now we keep going. We might as well keep our pattern going by looking at the left side moving on from the red.

So, we're good with that one because we swapped it. We don't even need to check it. So we move onto the two.

Sound good?

Answer 35

ok

Answer 36

\(\{3\ 1\ \color{red} 2\ 7\ 4\ \color{blue}8\ 9\}\)
Is 2 okay there?

Before we go on, I'll remind you that we decided on putting a 7 on the left side if we encountered one.

Answer 37

Is 2 okay there?

Answer 38

2 is ok? because it is less than 7?

Answer 39

Yep! and we want the left side to be less than 7 or 7. I have to emphasize this, because immediately to the right is a 7. So \(2\le7\) so we're good.

Okay so 2 is good, and we move on to the 7.
\(\{3\ 1\ 2\ \color{red} 7\ 4\ \color{blue}8\ 9\}\)
What to do with our chosen number, 7?

Answer 40

7<=7 so nothing happens?

Answer 41

then do you look at the right of 7?

Answer 42

And I need to correct myself. The left side is \(\le7\), the right side is \(\ge7\).

Answer 43

ok

Answer 44

I need a moment to refresh my memory, sorry.

I know that the 7 needs to swap with the 4.
This is explained by our goal....

Answer 45

ok I can wait

Answer 46

Okay... I think... That an okay thing to do... Is...
We'll say 7 isn't less than 7, so we swap. We'll keep doing what we were doing before. Forget the equality.
The issue is when you find another 7, in which case we need to do something special. The YouTube link algorithm breaks down there.

Answer 47

So, 7 is NOT okay with our left side, the side we look at with red.

Answer 48

then is anything swap?

Answer 49

\(\{3\ 1\ 2\ \color{red} 7\ 4\ \color{blue}8\ 9\}\)
So now we move on to the blue side again.
8 is okay, because we switched it. Now we go to the left of it.
\(\{3\ 1\ 2\ \color{red} 7\ \color{blue}4\ 8\ 9\}\)

Answer 50

so 4 should not be on the right, it gets swap? but with which number?

Answer 51

And the 4 is greater than 7, so it is no good. We have bad ones on both side, so we swap.

We stopped at the 7 because it was not less than seven and would need to move. So we do this swap.
\(\{3\ 1\ 2\ \color{red} 4\ \color{blue}7\ 8\ 9\}\)

Now, we're a computer. So how do we know when we've reached the middle? Well, we start from the left side like normal. So we're at the 4. The 4 is okay there, so we move to the right, to the specific 7 we chose earlier. So we are done!
\(\{3\ 1\ 2\ 4\ \color{#DD00DD}7\ 8\ 9\}\)

Answer 52

Notice that we followed an algorithm all the way through. We haven't proved it correct, but it seems to be okay. Except that it breaks down for two 7's. Which we need to fix.

Answer 53

so it stops because everything is fixed?

Answer 54

Right, if there is only one 7! Only one of our randomly chosen value.

Answer 55

It stops because everything less than 7 is on the left, and greater than 7 is on the right.

Answer 56

then what if there is another 7? What happens?

Answer 57

It's done because 4 is okay so we move to the right to a 7. Then we look at the right side and encounter a 7. So we're good.

That's what I have to figure out...

Answer 58

ok. So what next?

Answer 59

Once we have done that algorithm once, we are left with \(some\) order.
\(\{3\ 1\ 2\ 4\ 7\ 8\ 9\}\)
\(\{\color{red}{3\ 1\ 2\ 4}\ \color{#dd00dd}7\ \color{blue}{ 8\ 9}\}\)
Now we see that they're separted by the 7.

We must now use the same algorithm, from the very start, on each section. So the red and blue sections above must undergo this algorithm, starting with picking a random spot.

Answer 60

So, say we choose 2.
We start at the ends again.
\(\{\color{red}3\ 1\ 2\ \color{blue}4\ 7\ 8\ 9\}\)
3 is not less than 2, so it is on the wrong side.
So we switch sides.
4 is greater than two, so we're okay. So we move immediately left.
\(\{\color{red}3\ 1\ \color{blue}2\ 4\ 7\ 8\ 9\}\)
2 is not greater than 2, so we now have a bad number on both sides, so we swap.
\(\{\color{red}2\ 1\ \color{blue}3\ 4\ 7\ 8\ 9\}\)
Then 2 is not less than two, so it's bad and we go to the other side.
3 is okay, so we go to the immediate left.
\(\{\color{red}2\ \color{blue}1\ 3\ 4\ 7\ 8\ 9\}\)
1 is blue, but not greater than two. We have bad numbers on both sides, so we swap.
\(\{\color{red}1\ \color{blue}2\ 3\ 4\ 7\ 8\ 9\}\)
We go back to the left (red). 1 is less than two, so we go to the next index.

Now both sides are at the same spot.

If you think about it, we have an `int` with the left index and an `int` with the right index. When they're equal, that group is done. Another indicator is that we're looking at the same number, but I can't think of which is more efficient to test.

Answer 61

but 8 and 9 on the right don't have to go through the swapping again? what if it is not sorted like 9 8?

Answer 62

Good observation! I did the left side of the 7. The right side of the 7 needs to be sorted as well.
With a long list, by the end, you'll have broken it up into many, many sections. but each swap takes out two problematic numbers!

I notice, though, when you encounter your chosen number, you keep moving it. That seems bad, swapping every single step. I think we should swap it with some number between where it is and where your other side is. If it's between the sides, you'll see it again, but you won't worry about it every step. This also fixes the problem of multiple occurrences of the chosen number. The only downside is that we could end up with something like:
\(\{\color{red}{4\ 3\ 6\ 2\ 7}\ \color{#ee00ee}7\ \color{blue}{7\ 7\ 8\ 9\ 8\ 20\ 8}\}\)
Repeated 7's would be resorted, even though they wouldn't move. I gues you can move from your chosen one left until it's not 7 and right until it's not 7.

Answer 63

guess*

Answer 64

so whenever you swap something/ sorting, you break up the sequence into sections?

Answer 65

The main aspect of all quicksort algorithms (if I remember correctly) is the pattern of partitioning.

Answer 66

ok, I get it. It's just like merge sort where you have to partition the sequence to individual ones?

Answer 67

Whenever you choose a number is when you create the rule of thumb that will divide your set into two sections.

The swapping will use this rule to establish some order (less than 7 vs more than seven).

We then repartition, and divide and conquer each side. It might break up into more and more partitions, but it's still quick.

Answer 68

I see. You explain it very well! Thanks a lot, I wish I can give you two medals lol

Answer 69

Haha, no problem!

I hope you have the general concept now!

It still needs tweaks, but I hope that it will suffice for now :)

Answer 70

yep, I understand the general concept now :D

Answer 71

Great! Take care! I'm glad that you kept on asking questions and following along. It's the only way you can learn.