A Collection of Code Snippets in as Many Programming Languages as Possible

This project is maintained by TheRenegadeCoder

Welcome to the Quick Sort page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

- Jeremy Grifski
- Ron Zuckerman

Quick sort is an algorithm that works by dividing a list into smaller lists. It recursively partially sorts and divides each sublist into further lists until it reaches the base case of a list that is either empty or contains only a single element, because those cases are by definition already sorted. After that it concatenates all of the sublists together into a single sorted list.

Step by step the process is:

- Pick an element. This element is called the pivot.
- Move all elements in the list that are greater than the pivot after the pivot
- Move all elements that are less than the pivot before the pivot.
- Recursively repeat steps 1-4 until a list of size 0-1 is found.
- Concatinate all the sublists into a single sorted list.

The performance of sorting algorithms is generally defined in "Big O notation". If you are not familiar with such notations, please refer to the relevant article by Rob Bell or the Wikipedia entry listed in further readings below.

Cases | Big O Notatation |
---|---|

Best case | O(n log n) |

Average case | O(n log n) |

Worst case | O(n^{2}) |

As the name implies, quicksort is a rather efficient algorithm; however,
its performance can be affected by the pivot that is selected. For example,
always selecting the last element in the list (or sublist) can make the algorithm easy
to write, but on a sorted list that will lead to an efficiency of O(n^{2})
(the worst case).

The example below was taken from Wikipedia's article about Quick sort.
The **bolded** elements are the pivots. In this example, the last element in each list/sublist
was chosen to be the pivot, but that is not necesary. (See the section about performance above.)
Each row shows the comparison of an element to the pivot (steps 2-3).
The arrows convey splitting each list into sublists and then bringing them back together (steps
4-5).

Write a sample program that takes a list of numbers in the format "4, 5, 3, 1, 2". It should then sort the numbers and output them:

```
$ ./quick-sort.lang "4, 5, 3, 1, 2"
1, 2, 3, 4, 5
```

The solution should handle duplicate elements

```
$ ./quick-sort.lang "4, 5, 3, 1, 4, 2"
1, 2, 3, 4, 4, 5
```

In addition, there should be some error handling for situations where the user doesn't supply correct input.

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Quick Sort. In order to keep things simple, we split up the testing as follows:

- Quick Sort Valid Tests
- Quick Sort Invalid Tests

Description | Input | Output |
---|---|---|

Sample Input | "4, 5, 3, 1, 2" | "1, 2, 3, 4, 5" |

Sample Input: With Duplicate | "4, 5, 3, 1, 4, 2" | "1, 2, 3, 4, 4, 5" |

Sample Input: Already Sorted | "1, 2, 3, 4, 5" | "1, 2, 3, 4, 5" |

Sample Input: Reverse Sorted | "9, 8, 7, 6, 5, 4, 3, 2, 1" | "1, 2, 3, 4, 5, 6, 7, 8, 9" |

Description | Input |
---|---|

No Input | |

Empty Input | "" |

Invalid Input: Not A List | "1" |

Invalid Input: Wrong Format | "4 5 3" |

All of these tests should output the following:

```
Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5"
```

- Quick Sort in Algol68
- Quick Sort in Bash
- Quick Sort in C
- Quick Sort in C#
- Quick Sort in C++
- Quick Sort in Dart
- Quick Sort in Euphoria
- Quick Sort in Go
- Quick Sort in Haskell
- Quick Sort in Java
- Quick Sort in Javascript
- Quick Sort in Kotlin
- Quick Sort in Lisp
- Quick Sort in Mathematica
- Quick Sort in Objective C
- Quick Sort in Php
- Quick Sort in Python
- Quick Sort in Rust
- Quick Sort in Scala