Alignment algorithms

Tram Ho

Merge sort

Like Quick sort, Merge sort is an algorithm to divide and treat. Divide the array into small arrays, then merge the small pieces that have been put together.

For example with array 38, 27, 43, 3, 9, 82, 10, merge sort's sequence will look like this:

Algorithm deployment: Because merge sort is an algorithm that uses a lot of memory, it is better to use linked lists, with linked lists, it is much simpler to split and store than using the array. usually (You need to have basic knowledge about pointers before looking at the code below).

Counting sort

Counting sort is a technique of arranging objects in a specific range. It works by counting the number of objects with the same value. Then use a little math to calculate the final position of that object.

The complexity of this algorithm is O (n + k) where n is the quantity of the quantity, k is the value range of n objects.

Find out through an example:

This is a code that arranges array of characters, the algorithm can also be used to sort arrays of integers. For an array of integers that include both positive and negative numbers, the algorithm needs to be changed slightly. The reason is because in c ++ you cannot access the value in the negative position in the array. To solve this problem, you need to recalculate about k and rebuild the count array so that the smallest element is in position 0.

Radix sort

The familiar algorithms such as quick sort, merge sort, heap sort, … are sorting algorithms based on the value of comparisons, the complexity of these algorithms cannot be better than O (nLogn). As for the counting sort algorithm above, is a linear algorithm with complexity of O (n + k). In case k equals n*n , counting sort is a bad choice. Radix sort is a good choice in this TH.

The idea of ​​this algorithm is to arrange numbers by values ​​of tens, hundreds, thousands, …

For example:

Algorithm deployment:

Share the news now

Source : viblo.asia