Algorithm you must know

This article is about algorithm which programmer must know. You might use these algorithm a lot.

・Bubble Sort
・Quick Sort
・Merge Sort

Sorting algorithm is used to sort the data in descending or ascending. Use different methods depending on the complexity and amount of data.

Bubble Sort

Bubble Sort is a method of sorting that compares two adjacent elements and swaps them if they are not in the intended order.

How to work

1. Starting with the first index, compare the the first element and the second element of the array.
2. If the first element is greater than the second element, swap them.
3. Compare the second element and the third element. And swap them if they are not in order.
4. Repeat until the last element.

Below, we have a picture of how bubble sort will sort the given array [-2,45,0,11,-9].

Source: https://www.honeybadger.io/blog/ruby-bubble-sort/

i=0: Compare -2 and 45. They are in order, so move onto the next step.

i=1: Compare 45 and 0. The second element(45) is greater than the third element(0), swap them.

i=2: Compare 45 and 11. The third element(45) is greater than the fourth element(11), swap them.

i=3: Compare 45 and -9. The fourth element(45) is greater than the last element(-9), swap them.

The same process goes on for the remaining iterations.
As a result, [-2,45,0,11,-9] is sorted into [-9,-2,0,11,45].

Sample code

Quick Sort

Quick Sort is a sorting algorithm based on the divide-and-conquer sorting algorithm.

How to work

1. An array is divided into subarrays by selecting a pivot element.
   The pivot element should be positioned in such a way that elements less than pivot are kept on the left side and elements greater than pivot are on the right side of the pivot.
2. The same process goes on for the left and right subarrays.
3. Repeat until each subarray contains a single element.
4. Combine elements to form a sorted array.

The picture below is an example.

Source: https://dev.to/mwong068/quick-sort-in-ruby-2302

At first, select a pivot element
Ex.(7).
And divide into subarrays. Elements less than pivot are kept on the left side and elements greater than pivot are on the right side of the pivot.
Ex.[1,2,6,5] [7] [12,15,10]
Repeat the same process for each subarrays.
Ex.[1,2][5][6]/[10][12,15]
Combine these elements to a sorted array.
EX. [1,2,5,6,7,10,12,15]

Sample code

Merge Sort

Merge Sort is one of the most prominent divide-and-conquer sorting algorithms. It can be used the values in any traversable data structure such as a list.

How to work

1. Merge sort works by splitting the input list into two halves
2. Repeat the process on those halves
3. Merge the two sorted halves together

The figure below is an example.

Repeat the two divisions of the array until the number of elements becomes
[4,3,5,7,1,8,6,2]→[4,3,5,7][1,8,6,2]→…→[4][3][5]..[6][2]
Sort the divided elements and merge them.
[3,4][5,7][1,8][2,6]→[3,4,5,7][1,2,6,8]→[1,2,3,4,5,6,7,8]

Source: https://medium-company.com/

Sample code