Hey to everyone! I guess you all did sorting at least once. I also guess that everyone knows a sorting called "Bubble", cause it is the easiest and most popular. But when it comes to time and your memory, what will you do?
Imagine a situation. You have a mass that contains about 10^100 elements. Is it still good to use bubble sorting? Just imagine checking every element... and not once. It is not so difficult to count how many operations it is and how much time it takes.
Let's get to know some more interesting ways to sort your mass (to go through).
There are many types of algorithms:
- O (n2) sorting algorithms like insertion, bubble, and selection sort, which are used in special cases;
- quicksort: O (n log n), but the worst time is O (n2) if the array is already sorted or the elements are equal;
- O (n log n) algorithms such as merge and heap sort
- O (n) or linear sorting algorithms for lists of integers.
1.Heapsort
The heap conversion procedure (happify) can be applied to a node only if its child nodes have already been converted. The sorting implies dividing the array equally until several small ones are obtained from one array - no more than two elements in size. The two elements can be easily compared with each other and ordered depending on the requirement: in ascending or descending order.
After splitting, one element from each array is selected and compared with each other. The smallest (or largest) element is sent to the resulting array, the remaining element remains relevant for comparison with an element from another array in the next step.
2.Selection sort
It is the easy one to understand and to make too. We are going through the array and looking for the maximum element. We swap the found maximum with the last element. The unsorted part of the array has decreased by one element. We apply the same actions to this unsorted part until the unsorted part of the array is reduced to one element.
General idea:
- The local maximum (minimum) is searched for in the unsorted subarray.
- The maximum (minimum) found is swapped with the last (first) element in the subarray.
3.Quick sort
The subarray element is selected, and the array is divided into 3 subarrays: smaller subarray, equal to the subarray, and large subarray. Then this algorithm is applied recursively to subarrays.
General idea:
- Choosing a subarray
- Splitting the array into 3 parts
- Create variables l and r for the beginning and end of the considered subarray
- Increase l until the l-th element is less than the subarray
- Decrease r until the r-th element is larger than the subarray If l is still less than r, then we swap the l-th and r-th elements in places, increment l and decrement r. If l suddenly becomes larger than r, then we interrupt the cycle
- Repeat recursively until we reach an array of 1 element
4.Bitonic sort
The idea: the original array is converted into a biton sequence - a sequence that first increases and then decreases.
- Split the array into two parts, create two subarrays, add all the elements equal to the minimum of the elements of each of the two parts to the first, and equal to the maximum in the second.
- Recursively call the algorithm from the subarrays, after which we sort the first part in order, the second in reverse order and connect them together.
5.Timsort
A hybrid sort that combines insert sort and merge sort.
- Split the elements of the array into several subarrays of a small size, while we will expand the subarray as the elements in it are sorted.
- Sort the subarrays by insertion sort
- Merge subarrays as in merge sort, taking them of equal size. Merge subarrays at the top only when the size of the third most distant from the top of the subarray is greater than or equal to the sum of their sizes.
I tried to show the sorting algorithms from different groups. You can try by yourself and you will see that for example "Selections sort" is slower (more operations), than "Heapsort", that's why bubble, selection, gnome, shaker and insertion sortings are used only in special cases. Use algorithms correctly to prevent loss of time and memory!
That is a small help for all beginners that want to get acquainted with the sorting ways (not just bubbles). If you need some help, you can write to me anytime.
Good luck in your job!
Written by Yuri Filatov, IT Expert at Andersen