This time on SwiftyAlogs we will be taking a look at the classic sorting algorithm ** Quick Sort**. Similar to Merge Sort,

**works based on the idea of**

*Quick Sort**split and tackle*.

**relies on choosing some element, known as a**

*Quick Sort**pivot*, and then segmenting or partitioning the collection to be sorted around that

*pivot*.

**is a very flexible way to sort; allowing for the**

*Quick Sort**pivot*to be declared in a number of ways:

- Pivot on the first element
- Pivot on the last element (this is the one we will use)
- Pivot on a random element
- Pivot on the median element

#### The critical part of the Quick Sort process is the partition…

A *partition* works based on the following idea: If we have an array of things, and we choose a *pivot* . . .

- place the
*pivot*in the correct position in the array - move all things smaller before the
*pivot* - move all things larger after the
*pivot*

The resulting two sides of this operation all called *partitions*, within each of these we can recursively repeat the process until we reach a point where our *partitions* are too small to sort, and we should ultimately have a sorted array.

#### It works like this…

#### So, starting with an unsorted array…

- First we take the last element as our
**pivot**. - Next we assign
**i**and**j**to track indexes..**j = 0**, and**i = j-1**to start with - From here we compare
**j**with the**pivot**. If the**pivot**is less than the value of**j**, we move on, incrementing**j+1**. If the value of**j**is greater than the**pivot**, we swap the**pivot**with**j**and increment both**j+1**and**i+1**. - Now we compare values again, if the
**j**is less than the**pivot**, we will increment**i+1**, and swap theat*values***j**and**i**. - Next increment
**j+1**, and do it all again, compare to the**pivot**, swap or not, and move on. - Once we reach the last element in the array (the one right next to the
**pivot**), we compare those two values,*IF*the value is less than the**pivot**then the**pivot**stays put, and we**partition**below it.

This can be tricky to understand at first, here is a great video on youtube that explains it with cups, and here is another one that uses dancing Hungarians.

#### Lets take a look at the code…

#### And run it…

*Check out the code here on Github*

#### Closing thoughts…

** Quick Sort** is comparatively one of the more challenging algorithms that we have looked at in this series thus far, but with a little practice it should become clear. I would strongly encourage you to take it to paper if you are a bit confused, start with a smaller set of values, and write it out; this certainly helped me to understand things a bit better. One of the best things in my opinion about

**is how flexible the concept is, there a many different ways to approach it and many ways to implement it! If you’re interested in digging deeper on this I would encourage you to head over to The Swift Algorithm Club and check out their deep dive. Thanks again to GeeksForGeeks for providing a great resource for learning CS concepts. As usual it’s important to remember that when you explain an idea you take the greatest steps towards mastery.**

*Quick Sort*Until next time …