1. Selection sort
Time complexity O(n^2)
Main processes:
Selection sort is to select next to each other and put it in front of the small one.
If you want to choose a small one, you need to have a comparative object.
The first number of selected arrays is the minimum value by default, and then compares with the latter one in order to get the subscript of the minimum value in the remaining arrays.
Then swap with the first number of the selected array to complete a selection
template <typename T>
void selectSort(T arr[], int n) {
for(int i =0 ; i < n; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if(arr[minIndex] > arr[j])
minIndex = j;
}
swap(arr[i], arr[minIndex]);
}
}
number = 10000
selectSort:0.117953s
number = 100000
selectSort:11.019439s From the above results, the computational complexity is increased by 10 times and the time is increased by 100 times, which accords with the time complexity of O(N^2).
2. Insertion sort
Time complexity O(n^2)
Main processes:
A little bit of order, that's it.
Place the first two numbers in order
Rearrange the first three numbers to make them orderly
Rearrange the first four numbers to make them orderly
...
...
At the end of the row. It's all in order.
The point to note in the implementation is that you can start the loop directly from subscript 1, because if there is only one number, it is orderly in itself.
Moreover, from small to large rows, if the number in front of the monitor is smaller than the current number,
Then you can jump out of the current cycle, after all, the previous is orderly.
template <typename T>
void insertSort(T arr[], int n) {
for(int i = 1; i < n; i++) {
// i ~ 0 is the first few that need to be sorted
for( int j = i; j > 0; j--) {
if( arr[j] < arr[j-1] ) {
swap(arr[j], arr[j-1]);
} else {
break;
}
}
}
}
///////////////////
number = 10000
selectSort:0.127038s
insertSort:0.145065s The above ordering has room for optimization, because one exchange equals three assignments, so try not to exchange. Instead, record where each new addition needs to be placed, and then all the subsequent numbers move one bit backwards. Finally, place the newly added number in the recorded position.
template <typename T>
void insertSort(T arr[], int n) {
for(int i = 1; i < n; i++) {
T e = arr[i];
int j;
for(j = i; j > 0; j--) {
if( arr[j-1] > e ) {
arr[j] = arr[j-1];
} else {
break;
}
}
arr[j] = e;
}
}
//And in order to be beautiful, you can mention the condition of if in for.
template <typename T>
void insertSort(T arr[], int n) {
for(int i = 1; i < n; i++) {
T e = arr[i];
int j;
for(j = i; j > 0 && arr[j-1] > e ; j--) {
arr[j] = arr[j-1];
}
arr[j] = e;
}
}
///////////////////
number = 10000
selectSort:0.116369s
insertSort:0.076550s
Insertion sort tends to be O(N) in dealing with near-ordered columns because it makes the next comparison as long as it judges that the front is ordered. So when dealing with near-ordered sequences, priority should be given.
3. Bubble Sorting
Time complexity is O(n^2)
Main processes:
When the first number is compared with the second number, the large number is exchanged, the second number is compared with the third number, and the large number is exchanged, so that the past is exchanged in turn, and the largest number will eventually be placed at the end of the array.
Then we compare the first number with the second one. If it is big, we will exchange it. If it is big, we will compare the second number with the third number. If it is big, we will exchange it. We will know that we will put the last-to-last number into the second-to-last number.
. . .
. . .
After the final comparison, from the back to the front, from the big to the small, it will be orderly.
template <typename T>
void bubbleSort(T arr[], int n) {
for(int i = 0; i < n; i++) {
for(int j = 1; j < n-i; j++ ) {
if(arr[j] < arr[j-1])
{
swap(arr[j], arr[j-1]);
}
}
}
}
///////
number = 10000
selectSort:0.117713s
insertSort:0.072229s
bubbleSort:0.306428s 4. Hill Sort
Time complexity: O(N*logN)
Hill sort is a special sort and an improved sort algorithm for insertion sort. Its step size is adjusted.
Main processes:
For example, the array is 653 1 8 7 2 4
When the initial step size is 3, there is no need to adjust 653 as the first three numbers. From the beginning, 1 jumps forward three times and comes to the position of 6. Comparing, 1 is smaller than 6.
So the positions of 1 and 6 are exchanged so that 1 reaches position 0 and the first three crosses the boundary, so the exchange process stops.
Array 1 5 3 6 8 7 2 4
In dealing with the number 8, the number 8 jumps forward three times is compared with the number 5. It is found that compared with the number 5, 8 > 5, the exchange process is stopped directly and the next number is compared.
So we came to the position of number 7, 7 jumped forward three times, found that 7 > 3, stopped again.
At the position of 2, 2 jumps forward three times, compared with 6, 2 < 6, SO 2 exchanges with 6, and 2 jumps forward three times. At this time, it is found that 2 should be compared with 1, 2 > 1, SO 2 stops in situ.
Array 1 5 3 2 8 7 6 4
Next, deal with the number 4, jump forward three times, come to the position of number 8, 4 < 8, exchange, 4 and jump forward three comparisons, found that 4 < 5, exchange, 4 came to position 1, can not jump forward.
So the insertion sort of step 3 is over.
After step 3, there is step 2, and finally step 1, which is a classic insertion sort.
The Hill sort ends with a step-size-1 sort.
The key of Hill ranking lies in the choice of step size. The better the choice of step size, the lower the time complexity and the worse the choice of step size, the closer to the level of time complexity O(n^2).
template<typename T>
void shellSort(T arr[], int n)
{
int h = 1;
while( h < n/3 )
h = 3 * h + 1;
// Calculate increment sequence: 1, 4, 13, 40, 121, 364, 1093...
while( h >= 1 ){
// h-sort the array
for( int i = h ; i < n ; i ++ ){
// For arr[i], arr[i-h], arr[i]-2*h], arr[i-3*h]... Use insert sort
T e = arr[i];
int j;
for( j = i ; j >= h && e < arr[j-h] ; j -= h )
arr[j] = arr[j-h];
arr[j] = e;
}
h /= 3;
}
}—————————— Complete code
#ifndef SORTTESTHELPER_H
#define SORTTESTHELPER_H
#include <iostream>
#include <ctime>
#include <cassert>
#include<iomanip>
using namespace std;
namespace SortTextHelper {
// Generate a random array of n elements, the range of elements [rangeL, rangeR]
int *generateRangeArray(int n, int rangeL, int rangeR) {
assert(rangeL <= rangeR);
int * arr = new int[n];
srand(time(NULL));
for(int i=0; i < n; i++){
arr[i] = rand() % (rangeR-rangeL+1) + rangeL;
}
return arr;
}
template <typename T>
void printArray(T arr[], int n) {
for(int i =0 ; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
template <typename T>
bool isSorted(T arr[], int n) {
for(int i = 0; i < n-1; i++) {
if( arr[i+1] < arr[i] ) {
return false;
}
}
return true;
}
template <typename T>
void testSort(const char *sortName,void (*sort)(T arr[], int ), T arr[], int n) {
clock_t startTime = clock();
sort(arr, n);
clock_t endTime = clock();
assert(isSorted(arr,n));
cout << sortName << ":" << setiosflags(ios::fixed) << double(endTime-startTime) / CLOCKS_PER_SEC << "s" << endl;
}
int * copyIntArray(int a[], int n) {
int *arr = new int[n];
copy(a, a+n, arr);
return arr;
}
}
#endif //SORTTESTHELPER_H
#include <iostream>
#include "SortTextHelper.h"
using namespace std;
template <typename T>
void selectSort(T arr[], int n) {
for(int i =0 ; i < n; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if(arr[minIndex] > arr[j])
minIndex = j;
}
swap(arr[i], arr[minIndex]);
}
}
template <typename T>
void insertSort(T arr[], int n) {
for(int i = 1; i < n; i++) {
T e = arr[i];
int j;
for(j = i; j > 0 && arr[j-1] > e; j--) {
arr[j] = arr[j-1];
}
arr[j] = e;
}
}
template <typename T>
void bubbleSort(T arr[], int n) {
for(int i = 0; i < n; i++) {
bool bSwapped = false;
for(int j = 1; j < n-i; j++ ) {
if(arr[j] < arr[j-1])
{
swap(arr[j], arr[j-1]);
bSwapped = true;
}
}
if(bSwapped == false) {
break;
}
}
}
template<typename T>
void shellSort(T arr[], int n){
int h = 1;
while( h < n/3 )
h = 3 * h + 1;
// Calculate increment sequence: 1, 4, 13, 40, 121, 364, 1093...
while( h >= 1 ){
// h-sort the array
for( int i = h ; i < n ; i ++ ){
// For arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... use Insertion Sort
T e = arr[i];
int j;
for( j = i ; j >= h && e < arr[j-h] ; j -= h )
arr[j] = arr[j-h];
arr[j] = e;
}
h /= 3;
}
}
int main(int argc, char *argv[])
{
int n = 10000;
cout << "number = " << n << endl;
int *arr = SortTextHelper::generateRangeArray(n, 0, n);
int *arr2 = SortTextHelper::copyIntArray(arr, n);
int *arr3 = SortTextHelper::copyIntArray(arr, n);
int *arr4 = SortTextHelper::copyIntArray(arr, n);
SortTextHelper::testSort("selectSort", selectSort, arr, n);
SortTextHelper::testSort("insertSort", insertSort, arr2, n);
SortTextHelper::testSort("bubbleSort", bubbleSort, arr3, n);
SortTextHelper::testSort("shellSort ", shellSort, arr4, n);
//SortTextHelper::printArray(arr, n);
delete[] arr;
delete[] arr2;
delete[] arr3;
delete[] arr4;
return 0;
}