# #1 Interview Preparation | How to sort an array with quicksort ?

## Code challenge

Given an array of numbers, write the function **quicksort(…)** which sorts in ascending order the input with the quicksort method.

- The difficulty of this challenge is ranked as :
**Advanced** - The topic of this challenge is categorized as :
**Algorithm**

## Expected output

## For whom is this article ?

This article aims to introduce the reader to a sorting algorithm called **quicksort**. It presents the quicksort method alongside with its code implementation and is addressed to the following people :

- People preparing for coding interviews
- People aiming to improve their coding skills by learning the quicksort algorithm
- People interested in algorithms and recursive thinking

## What is quicksort ?

Quicksort is a recursive **sorting** function (also called algorithm) which has the goal of sorting data. Data can be sorted in different ways, as an example a list of numbers can be sorted in an ascending or descending order. In this article we will implement the quicksort method to sort a list of numbers in an ascending order. See below the expected behaviour of our sorting function.

## How does it work ?

Quicksort takes as an input an array of elements, and returns its input sorted. The idea of the quicksort algorithm is the following : First it selects a **pivot** (the left-most element in the array), then it splits all the elements (except the pivot) into two partitions (1. elements smaller or equal than the pivot, 2. elements greater than the pivot). Once the partitions are obtained, it calls recursively quicksort on both of the partitions before concatenating the **sorted** partitions and the pivot.

Here are the steps.

- Check if the input array is empty (if yes, it is sorted). If not, go to step 2
- Select the first element of the array (pivot)
- Find all the elements smaller or equal than the pivot (excluding the pivot)
- Find all the elements greater than the pivot
- Concatenate quicksort of (3), the pivot and quicksort of (4)

See below a step-by-step example.

The result of step 5 is the sorted array [2, 5, 6]

**Note :** In step 5, quicksort of [2] is [2] because it is an array of one element (similarly quicksort of [6] is [6]). In case the array has more than one element, the entire steps should be applied.

## Coding quicksort(…)

This section aims to present an implementation of the quicksort algorithm in vba which follows the functional programming principles. The below code contains all the auxiliary functions and can be run on your machine simply by copying and pasting it in your coding environment.

The quicksort function uses the below helper functions to manipulate arrays. Those functions do not have any side effects meaning that they always create their output without modifying any of their inputs.

**cons(x, xs)**: returns a new array containing, in order, the element**x**and all the elements of the array**xs****concat(xs, ys)**: returns a new array containing, in order, all the elements of the array**xs**and all the elements of the array**ys****head(xs)**: returns the first element of the array**xs****tail(xs)**: returns a new array containing all the elements of the array**xs**except its first element**size(xs)**: returns the size of the array**xs****smallerOrEqualThan(x, xs)**: returns a new array with all the elements of**xs**that are smaller or equal than**x****greaterThan(x, xs)**: returns a new array with all the elements of**xs**that are greater than**x**

## VBA examples

This section shows examples of how the quicksort function, defined above, can be used.

Thanks for reading. I hope you have learnt something and this article helped you better understand how quicksort works. If you have any questions or comments, don’t hesitate to contact me