Algorithms : Sort,Search and
recursivity
By Ghalem Salim
Essential skills in algorithmics
In order to have a good skill and master all what is related to programming and
algorithmics you need :
- Problem Solving
- DSA understanding
- Good Programming level
Sorting algorithm
It is the way to arrange the
elements so it has a specific
order.
- Bubble sort
- Insertion sort
- Selection Sort
Bubble sort
Imagine you have a line of children
sorted by height and you want to sort
them from smallest to tallest. You
compare two children at a time, and if
the smallest is on the right, you swap
them. You repeat this until everything
is sorted.
Bubble sort
- speed : 🐢
- simplicity : Very simple
- how it works : Swap neighbors until everything is sorted
- Inconvenient : It compares and swaps each item multiple times, even if the
list is almost sorted.
Insertion Sort
Imagine that you are sorting cards in
your hand. You take a card and put it
directly in its place, comparing it with
those you already have in hand.
Insertion Sort
- speed : 🚀 for small lists
- simplicity : Simple
- how it works : Swap neighbors until everything is sorted
- Advantage: Insert each element in the correct place,Fewer exchanges than
Bubble Sort, therefore more effective on small lists.
- Inconvenient: less performant with large lists
Selection Sort
Imagine that you want to order medals
from smallest to largest. You look for
the smallest one, you put it first, then
you look for the second smallest, etc.
Selection Sort
- speed : normal
- simplicity : Simple
- how it works : Find the smallest one and put it in its place
- Advantage:Does fewer trades than Bubble Sort, so a little better.
Linear Search
Linear Search searches for an item
one by one, like looking for a key in an
unorganized drawer.
- Simple
- Useful for small lists
- 🐢 for large lists
Binary Search
Binary Search cuts the list in half at
each step. It only works on a sorted
list!
- divide to gain time
- very fast
- best way for large lists
Why we should learn them
- Performance optimization: choosing the right algorithm can make your code 10 to 100 times faster!
- Technical interviews: these algorithms are often requested in interviews.
- Actual usage:
- Quick Sort is already used in JavaScript (.sort() in V8).
-Binary Search is used in all databases.
-Linear Search is basic but useful when you can't sort your data.
Understanding them well will make you more efficient and effective as a developer!
Recursivity
Recursion is when a function calls
itself to solve a problem in smaller
steps. Instead of using loops,
recursion breaks a big problem into
smaller problems until reaching a base
case.
Example: factorial
Here it is the most well known
example :
- lets calculate factorial of 5
- 5! = 5 x 4 x 3 x 2 x1
- we can say that :
5! = 5 x 4! and 4! = 4 X 3!....
Exercice
- Calculate the sum of an array using factorial:
- use slice method
- make it recursive
- don’t forget the case to stop it!
Also see…
- Quick sort
- Dividing problem
-
