Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Quick Sort
Explanation
Quick sort is a sorting algorithm that is based on the divide-and-conquer paradigm
...
The pivot is placed in its correct position in the sorted array, and the remaining elements
are sorted recursively
...
Choose a pivot element from the array
...
Partition the array around the pivot such that all elements smaller than the pivot are on
the left of the pivot and all elements greater than the pivot are on the right of the pivot
...
Recursively sort the left and right subarrays
...

1
...
In this case, we will choose the middle
element, which is 4
...
We then partition the array around the pivot such that all elements smaller than the pivot
are on the left of the pivot and all elements greater than the pivot are on the right of the
pivot
...

3
...
The left subarray will be sorted to
[1, 2, 5], and the right subarray will be sorted to [3, 7]
...
Finally, we combine the two sorted subarrays to get the sorted array [1, 2, 3, 4, 5, 7]
...

The worst case occurs when the pivot element is always the smallest or the largest in the array
...

 Easy to understand and implement
...


Disadvantages
 The worst-case time complexity of quick sort is O(n^2)
...
e
...

Not a good choice for sorting small data sets

---