Haskell Quick Syntax Reference: A Pocket Guide to the Language, APIs, and Library

© Stefania Loredana Nita and Marius Mihailescu 2019

Stefania Loredana Nita and Marius MihailescuHaskell Quick Syntax Referencehttps://doi.org/10.1007/978-1-4842-4507-1_16

16. Algorithms

Stefania Loredana Nita¹  and Marius Mihailescu¹

(1)

Bucharest, Romania

 

In this chapter, you’ll learn how to implement algorithms such as quicksort, mergesort, and bubble sort.

Quicksort

Quicksort is a divide-and-conquer algorithm. Quicksort divides a large array into two smaller subarrays, known as the low elements and high elements. The time complexity in the best case is O(n log n) and in the worst case is O(n²).

The steps are as follows:

1. 1.

   Choose an element from the array. The element will be called the pivot .

    
2. 2.

   Reorder the array in such a way that all the elements ...