Sorting Algorithms

Selection sort – the sorting algorithm is to pass the array from beginning to end in search of the minimum element of the array and move it to the beginning. The complexity of this algorithm is O(n2).

Bubble sort – this algorithm swaps two adjacent elements if the first element of the array is greater than the second. This is so as long as the algorithm does not swap places all the unsorted elements. The complexity of this sorting algorithm is O(n^2).

Insertion sort algorithm sorts the array as it passes on its elements. At each iteration, an element is taken and compared with each element in the already sorted part of the array, thus finding "their place", then the element is inserted at its position. This is so as long as the algorithm does not pass over the array. The output is a sorted array. The complexity of this algorithm is O(n^2).

Quick sort – the essence of the algorithm is to split the array into two sub-array, the middle line is the item that is in the center of the array. In the course of the algorithm elements, smaller than average will be moved to the left, and large right. The same effect will occur recursively with the sub-array, they will be divided into two sub-array until, until what to cut (there will be one element). The output is a sorted array. The complexity of the algorithm depends on the input data and in the best case will be O(n×2log2n). In the worst case O(n^2). There is also the average value is O(n×log2n).

Comb sort – the idea of the algorithm is very similar to sorting the exchange, but the main difference is that compares are not two adjacent elements, and the elements in the interval, for example, in the five elements. This provides elimination of small values in the end that helps to speed up sorting of large arrays. The first iteration is performed with step calculated according to the formula (the array size)/(reduction factor) where the reduction factor is equal to approximately 1,247330950103979, or rounded up to 1.3. The second and subsequent iterations will take place from step (current step)/(reduction factor) and will occur as long as the move will not be equal to one. In almost any case, the complexity of the algorithm equals O(n×log2n).