---
type: slide
---
# Sorting
---
Sorting is an important feature to have in any programming language. Whether you want to sort an array of numbers, or a list of strings, it's very common to have a set of data that you want to order in some way.
---
There are a number of well-known algorithms used to sort data. However, not all of these algorithms are created equal: some are significantly more efficient than others.
---
## Bubble Sort
---
- For each element in the array, compare it with the next element (the element to the right).
- If the element is greater than the value on the right, swap the two values.
- Continue to swap until you have reached the end of the array. At this point the rightmost element will be in its correct place.
- Start at the beginning of the array and repeat this process. Since the rightmost element from the last iteration is now sorted, this process will terminate earlier and earlier each time you repeat
---
[see this video](https://www.youtube.com/watch?v=8Kp-8OGwphY)
---
Big **O** ?
---
O(n^2)
---
## Insertion Sort
---
- Start by picking the second element in the array (we will assume the first element is the start of the "sorted" portion)
- Now compare the second element with the one before it and swap if necessary.
- Continue to the next element and if it is in the incorrect order, iterate through the sorted portion to place the element in the correct place.
- Repeat until the array is sorted.
---
[see this video](https://www.youtube.com/watch?v=DFG-XuyPYUQ)
---
Big **O** ?
---
O(n^2)
Like bubble sort, insertion sort typically is O(n^2), since you need to go through the array for each element in it in order to find its proper position.
---
Selection Sort
---
- Assign the first element to be the smallest value (this is called the minimum).
- Compare this item to the next item in the array until you find a smaller number.
- If a smaller number is found, designate that smaller number to be the new "minimum" and continue until the end of the array.
- If the "minimum" is not the value (index) you initially began with, swap the two values. You will now see that the beginning of the array is in the correct order.
- Repeat this with the next element until the array is sorted.
---
[see this video](https://www.youtube.com/watch?v=f8hXR_Hvybo)
---
Big **O** ?
---
O(n^2)
Just like bubble sort and insertion sort, selection sort is O(n^2).
---
as we noticed that bubble sort, insertion sort, and selection sort are not the most efficient algorithms. all of them are typically O(n^2)
---
## Merge Sort
the algorithm involves splitting the array into smaller subarrays.
---
- Break up the array into halves until you can compare one value with another
- Once you have smaller sorted arrays, merge those arrays with other sorted pairs until you are back at the full length of the array
- Once the array has been merged back together, return the merged (and sorted!) array
---
---
---
So how does the algorithm perform in terms of its time complexity?
---
Once the array has been broken down into one-element subarrays, it takes O(n) comparisons to get two-element merged subarrays. From there, it takes O(n)
comparisons to get four-element merged subarrays, and so on. In total it takes O(log(n)) sets of O(n) comparisons, since the logarithm roughly measures how many times you can divide a number by 2 until you get a number that is 1 or less. Therefore, the time complexity for merge sort is O(n log(n)), which is significantly better than the complexity of bubble, insertion, and selection sort!
---
When trying to implement merge sort, it's helpful to first write a function that takes two sorted arrays and merges them together. Merge sort then works by splitting the array in half, recursively calling itself on each half, and then using the merge helper to merge the two sorted halves back together.
---
## Quick Sort
---
- Pick an element in the array and designate it as the "pivot". We'll make things simple to start, and will choose the pivot as the first element.
- Next, compare every other element in the array to the pivot.
- If it's less than the pivot value, move it to the left of the pivot.
- If it's greater, move it to the right.
- Once you have finished comparing, the pivot will be in the right place
- Next, recursively call quicksort again with the left and right halves from the pivot until the array is sorted
---
[see this video](
https://www.youtube.com/watch?v=XE4VP_8Y0BU)
---
```Like merge sort, quicksort typically runs at O(n log(n)), and even in the best case is O(n log(n)). But in the worst case - if the pivot is chosen to be the leftmost element and the array is already sorted, for instance - the runtime will be O(n2).```
---
finally you have to implement these Algorithms to understand it very will.
you can see some sorting algorithms in [this link](https://www.geeksforgeeks.org/sorting-algorithms) and you can find some problems that you can solve with sorting [here](https://leetcode.com/tag/sorting/)
Google Drive
Gist
Clipboard
Sign in with Wallet
