How Quicksort works with example in SQL

Quicksort

Are you wondering how Quicksort works and which computer science algorithm is behind it? Here you can find an understandable one Quicksort explanation. We'll start with that general principle. Then we will explain to you two different examplesthat once did the sorting algorithm very muchgenerallyillustrated and once the functionality as an actual onein-place-Procedure represents. Afterwards we look at the algorithmwith a Pseudocodeand an associatedStructogrammore precisely. How to get a Quicksort Java or C ++ implementationyou can find out with the help of a sample code. Finally, we will show you all the important points for complexityof the sorting process - i.e. the Quicksort runtime and the one needed Storage space.

definition

The sorting process is one of the recursive and unstableSorting algorithms. It can be derived from the English quick = fast and sort = sort and was developed in its basic form by C. Antony R. Hoare in the sixties. The quicksort algorithm works like the merge sort according to the Divide-and-conquer(English "divide and conquer") of computer science.

Pivot element

Here is a short definition of the pivot element. The pivot element is derived from the French pivot. Maybe you know it from Gaussian elimination method or the basic exchange procedure. Just like in computer science, i.e. with quicksort, this is always a Element of a set of numberswhich first from an algorithm is determined to perform a particular calculation. Within the sorting process, the element represents, so to speak, a division limit. The smallest or largest element in terms of amount is then searched for in the current (partial) list and sorted recursively. The selection of the item is made Pivotingcalled.

Quicksort explanation

The exact principle behind the quicksort cannot necessarily be generalized. There may be certain deviations due to the programming language used, which can actually affect the process differently. Even so, there is a certain basic principle. Here you can find a quicksort explanation of how it works in general.

Pivot element specific

You can actually use all elements for this. So for us this means that we can choose both the first and the last element, a value from the middle or even a random value. For an optimal recursion one actually always uses the Median. It is best to use your university script as a guide so that you know what your lecturer prefers. Let's take the first element as our pivot element as an example.

divide and conquer

The pivot element will then placed in the middle and sorted the remaining values. Once after Left, If you smallerare and once after right, If you greaterare. You have to have the elements always in the original orderfrom left to right in their area.

Recursive quicksort call

Recursive quicksort call for both parts of the array (before and after the pivot element):

The pivot element is then in its correct place and new ones have to be determined. The first elements again, of course, but this time in both areas. The process is repeated, so the remaining elements are arranged in exactly the same scheme next to the pivot elements. In the next step, all new pivot elements no longer have any comparative values ​​and are therefore placed correctly and all values ​​are sorted.

Quicksort example - general

You should pay particular attention to Quicksort pay attention to the form in which it is required by your university! The reason is quite simply that the quicksort is very dependent on the programming language and can actually run differently. So for you this means that you should absolutely stick to the desired version of your professor. We'll show you a very nowgeneral quicksort examplewith which you should understand the sorting algorithm very well. In addition, we will show you an example, which is a typicalIn-place variant represents. Just take a look at our video for the variant you need.

Let's start right away with the general example. The following list is given:

[6] [8] [2] [5] [9] [1] [7] [3] [4]

Determine pivot element

First we have to determine our pivot element for this. But there is no standardized guideline for this. For us, that means we can choose the first number, the last number or a random number. It is best to orientate yourself on the task or take the variant that your lecturer uses in the lectures. In our case, we simply take the first number as the pivot element - that is, the 6. We mark the number 6 in red and write it in the middle.

sort by

Now the remaining numbers have to be sorted accordingly. The numbers die less than 6are coming to the left. The Bigger onesthen come logically To the right. So let's start with the 8. It is larger than the 6 and is written in the first position to the right of the pivot element. Then comes the 2. It is smaller than the 6 and is automatically placed in the first position in the left area. We then do exactly the same with the 5. It comes just one place further next to the 2. The 9 is larger than the 6 and is written to the right next to the 8. Then comes the 1, which we automatically sort to the left. The 7 pack to the right again and the 3 and 4 to the left again.

[2] [5] [1] [3] [4] [6] [8] [9] [7]

Second run

Now we have to go again determine new pivot elements. We're voting again the first number, but this time from both areas.Once from the left area the 2 and once from the right area the 8. Then the whole thing starts again from the beginning, but we only sort the left side up to the 6th and once the right side from the 6th.

[1] [2] [5] [3] [4] [6] [7] [8] [9]

Third pass

Then we have to determine new pivot elements again. Again the first numbers, of course. That’s the 1 and the 7 on the left. And once the 5 and the 9 on the right side. The 1 no longer has any comparison values, so it is in the right position. So we first have to sort the 3 and 4 correctly again, namely to the left of the 5. The 7 and 9 are the same as with the 1. They are individual elements and are therefore already correctly placed.

[1][2] [3] [4] [5][6][7][8][9]

Now only the 3 and the 4 remain. The 3 is again our first number so our pivot element and the 4 is placed accordingly on the right.

[1] [2] [3] [4] [5] [6] [7] [8] [9]

The 4 will now be our new pivot element and the array is now sorted. We can now put all our numbers marked in red down in a row and have our sorted list.

[1] [2] [3] [4] [5] [6] [7] [8] [9]

[1] [2] [3] [4] [5] [6] [7] [8] [9]

Quicksort example - in-place

For the actualIn-place variantlet's use the same list as we just did for the general quicksort example:

[6] [8] [2] [5] [9] [1] [7] [3] [4]

Determine pivot element

First we have to define a pivot element. As before, there is no general rule for this.

But this time there is still additionally an iwhichever far left in the remaining row of numbersstands. And then there is also a jwhich far right in the row of numbersstands. The iruns through the row of numbers to the right and searches for numbers that are larger than the pivot element. The In contrast, j searches for smaller valuesand also runs to the left.

In our case it is directly appropriate. The 8 is bigger and the 4 smaller than the 6. And in this variant these numbers change their place directly. The i continues to look for a larger number and then finds 9 and the j the smaller number 3. We swap the two. Then the j next finds the 1 and the i next 7. The two cross each other and at this point in time the run is always ended for the current process. Then only the j is swapped with the pivot element if the j is smaller. The 1 is smaller, so it can be swapped.

 [1] [4] [2] [5] [3][6][7] [9] [8]

Important!If our pivot element had been on the far right at the beginning, we would have had to compare it to our i! So you would have checked whether the i-element was larger than your pivot element. Just like in our case, you check whether j is smaller. This is because we have already divided the rest of the list into larger and smaller than the pivot element with i and j. Our pivot element must therefore be in the middle.

Second run

But back to the task! So we have our current list [1] [4] [2] [5] [3] [6] [7] [9] [8]. The pivot element 6 is then already in its correct position. So we can determine 2 new pivot elements again. Once in the left area up to 6 and once in the right area after the 6. Of course, we use the first number again in both cases, i.e. the 1 and the 7. We also sort the i as the first element from the rest of the list and j as the last element. But again on both sides!