Comparison of sorting algorithms
This article discusses array sorting algorithms. To begin with, the algorithms selected for testing are presented with a brief description of their work, after which the testing is performed directly, the results of which are recorded in a table and the final conclusions are made.
Sorting algorithms are very widely used in programming, but sometimes programmers do not even think about which algorithm works best of all (the term “best of all” means the 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 algorithms presented will sort an integer array of 200 elements. The computer on which the testing will be conducted has the following characteristics: AMD A6-3400M 4x1.4 GHz processor, 8 GB RAM, Windows 10 x64 build 10586.36 operating system.
The following sorting algorithms were selected for the study:
')
Selection sort (sorting by choice) - the essence of the algorithm is to go through the array from beginning to end in the search for the minimum element of the array and move it to the beginning. The complexity of this algorithm is O (n2).
Bubble sort (bubble sort) - this algorithm reverses 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 (sorting by inserts) - the algorithm sorts an array as it goes 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 (quick sort) - the essence of the algorithm consists in dividing an array into two sub-arrays, the middle line is an element that is located in the very center of the array. In the course of the algorithm, elements smaller than the average will be moved to the left, and large ones to the right. The same action will occur recursively and from a sub-array; they will be divided into two more sub-arrays until something is divided (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, it is O (n × log2n).
Comb sort (comb sorting) - the idea of the algorithm is very similar to exchange sorting, but the main difference is that not two neighboring elements are compared, but elements on an interval, for example, in five elements. This ensures that small values are not eliminated at the end, which speeds up the sorting in large arrays. The first iteration is performed in increments 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 in steps (current step) / (reduction factor) and will occur 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 made and the best time will be chosen. The best time and the memory used will be listed in the table. There will also be tested the speed of sorting an array of 10, 50, 200 and 1000 elements in size to determine for which tasks a specific algorithm is intended.
Fully unsorted array:
Partially sorted array (half of the elements are ordered):
Results provided in graphs:
Findings:
As a result of the study and the obtained data, for sorting an unsorted array, the most optimal of the presented algorithms for sorting an array is a quick sort. Despite the longer execution time, the algorithm consumes less memory, which can be important in large projects. However, such algorithms as sorting by selection, exchange and inserts may be better suited for scientific purposes, for example, in training, where there is no need to process a huge amount of data. With a partially sorted array, the results are not very different, all sorting algorithms show a time about 2-3 milliseconds less. However, when sorting a partially sorted array, fast sorting works much faster and consumes less memory.
Sorting algorithms are very widely used in programming, but sometimes programmers do not even think about which algorithm works best of all (the term “best of all” means the 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 algorithms presented will sort an integer array of 200 elements. The computer on which the testing will be conducted has the following characteristics: AMD A6-3400M 4x1.4 GHz processor, 8 GB RAM, Windows 10 x64 build 10586.36 operating system.
The following sorting algorithms were selected for the study:
')
Selection sort (sorting by choice) - the essence of the algorithm is to go through the array from beginning to end in the search for the minimum element of the array and move it to the beginning. The complexity of this algorithm is O (n2).
Bubble sort (bubble sort) - this algorithm reverses 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 (sorting by inserts) - the algorithm sorts an array as it goes 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 (quick sort) - the essence of the algorithm consists in dividing an array into two sub-arrays, the middle line is an element that is located in the very center of the array. In the course of the algorithm, elements smaller than the average will be moved to the left, and large ones to the right. The same action will occur recursively and from a sub-array; they will be divided into two more sub-arrays until something is divided (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, it is O (n × log2n).
Comb sort (comb sorting) - the idea of the algorithm is very similar to exchange sorting, but the main difference is that not two neighboring elements are compared, but elements on an interval, for example, in five elements. This ensures that small values are not eliminated at the end, which speeds up the sorting in large arrays. The first iteration is performed in increments 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 in steps (current step) / (reduction factor) and will occur 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 made and the best time will be chosen. The best time and the memory used will be listed in the table. There will also be tested the speed of sorting an array of 10, 50, 200 and 1000 elements in size to determine for which tasks a specific algorithm is intended.
Fully unsorted array:
Partially sorted array (half of the elements are ordered):
Results provided in graphs:
Findings:
As a result of the study and the obtained data, for sorting an unsorted array, the most optimal of the presented algorithms for sorting an array is a quick sort. Despite the longer execution time, the algorithm consumes less memory, which can be important in large projects. However, such algorithms as sorting by selection, exchange and inserts may be better suited for scientific purposes, for example, in training, where there is no need to process a huge amount of data. With a partially sorted array, the results are not very different, all sorting algorithms show a time about 2-3 milliseconds less. However, when sorting a partially sorted array, fast sorting works much faster and consumes less memory.
Source: https://habr.com/ru/post/274017/
All Articles