Comparing Sort Algorithms

This article discusses array sorting algorithms. First, the algorithms selected for testing are presented with a brief description of their work, after which the testing is carried out directly, the results of which are entered in the table and the final conclusions are made.

Sorting algorithms are very widely used in programming, but sometimes programmers don’t even think about which algorithm works best of all (the term “best of all” means a combination of speed and complexity of both writing and execution).

In this article we will try to find out. To ensure the best results, all the presented algorithms will sort an integer array of 200 elements. The computer on which the testing will be carried out has the following characteristics: AMD A6-3400M 4x1.4 GHz processor, 8 GB RAM, Windows 10 x64 build 10586.36 operating system.

To conduct the study, the following sorting algorithms were selected:

Selection sort - the essence of the algorithm is to go through the array from beginning to end in finding the minimum element of the array and moving it to the beginning. The complexity of such an 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 happens until the algorithm swaps all unsorted elements. The complexity of this sorting algorithm is O (n ^ 2).

Insertion sort - the algorithm sorts the array as it passes through its elements. At each iteration, an element is taken and compared with each element in the already sorted part of the array, thus finding "its place", after which the element is inserted into its position. This happens until the algorithm passes through the entire array. At the output, we get a sorted array. The complexity of this algorithm is O (n ^ 2).

Quick sort- the essence of the algorithm is to divide the array into two sub-arrays, the middle line is the element that is located in the very center of the array. During the operation of the algorithm, elements smaller than the average will be moved to the left, and large to the right. The same action will occur recursively from the sub-array, they will be divided into two more sub-arrays until there is something to cut (one element remains). At the output, we get a sorted array. The complexity of the algorithm depends on the input data and, at best, will be O (n × 2log2n). In the worst case, O (n ^ 2). There is also an average value, this is O (n × log2n).

Comb sort- the idea of ​​the algorithm is very similar to sorting by exchange, but the main difference is that not two neighboring elements are compared, but elements in the gap, for example, into five elements. This ensures that small values ​​are not eliminated at the end, which helps speed up sorting in large arrays. The first iteration is performed in steps calculated by the formula (array size) / (reduction factor), where the reduction factor is approximately 1.247330950103979, or rounded to 1.3. The second and subsequent iterations will take place with a step (current step) / (reduction factor) and will continue until the step is equal to one. In almost any case, the complexity of the algorithm is O (n × log2n).

For testing, 5 launches of each algorithm will be performed and the best time will be selected. The best time and the memory used for this will be entered in the table. We will also test the speed of sorting an array of sizes of 10, 50, 200 and 1000 elements to determine what tasks a particular algorithm is intended for.

Completely unsorted array:

image

Partially sorted array (half of the elements are ordered):

image

Results provided in graphs:

image

image

Conclusions:

As a result of the study and the data obtained, for sorting an unsorted array, the most optimal of the presented algorithms for sorting an array is fast sorting. Despite the longer run time, the algorithm consumes less memory, which can be important in large projects. However, algorithms such as sorting by selection, exchange, and insertion may be better suited for scientific purposes, for example, in training, where you do not need to process a huge amount of data. With a partially sorted array, the results are not much different; all sorting algorithms show a time of about 2-3 milliseconds less. However, when sorting a partially sorted array, quick sorting works much faster and consumes less memory.

Also popular now: