C++ implements bubble, select, hill, quicksort algorithm and comparison

preface

Compare the efficiency of several sorting algorithms, 100,000 random numbers.

Run a screenshot

code

#include <iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;
void display(int *arr,int n)
{
    for(int i=0; i<n; i++)cout<<arr[i]<<"";
    cout<<"\n";
}
// Copy the array
int *copyArr(int *arr,int n)
{
    int *num= (int *) malloc(sizeof(int)*(n+10));// Array initialization;
    for(int i=0; i<n; i++) { num[i]=arr[i]; }return num;
}
// Get the reverse array
int *getReverseArr(int *arr,int n)
{
    int *num= (int *) malloc(sizeof(int)*(n+10));// Array initialization;
    for(int i=n- 1,j=0; i>=0; i--,j++) { num[j]=arr[i]; }return num;
}
// Get the random group
void getRandomArr(int *arr,int n)
{

    for(int i=0; i<n; i++) arr[i]=rand()%n;// Generate a random number between 0 and n
}
// Bubble sort
void miaoSort(int *arr,int n)
{
    for(int i=0; i<n; i++)for(int j=1; j<n-i; j++) {if(arr[j- 1]>arr[j])
            {
                arr[j- 1] = arr[j- 1]^arr[j];
                arr[j] = arr[j- 1]^arr[j];
                arr[j- 1] = arr[j- 1]^arr[j]; }}}// Select sort
void xuanSort(int *arr,int n)
{
    for(int i=0; i<n; i++) {int index = i;
        for(int j=i+1; j<n; j++) {if(arr[index]>arr[j]) { index = j; } } arr[index] = arr[i]^arr[index]; arr[i] = arr[i]^arr[index]; arr[index] = arr[i]^arr[index]; }}// Hill sort
void sellSort(int *arr,int n)
{
    int step = n/5+1;// Set the step size

    while(step)
    {
        for(inti=step; i<n; i++) {int num = arr[i];
            int j = i;
            while(j>=step&&num<arr[j-step])
            {
                arr[j]=arr[j-step];
                j=j-step;
            }
            arr[j]=num;
        }


        step/=5;// divided by delta}}int position(int *arr,int left,int right)
{
       if(left>=right)
    {
        return left;

    }

    int i,j,base;
    i = left,j = right;
    base = arr[left];
    while(i! =j) {while(arr[j]>=base&&i<j)
            j--;
        while(arr[i]<=base&&i<j)
            i++;
        if(i<j)
        {

            arr[i] = arr[i]^arr[j];
            arr[j] = arr[i]^arr[j];
            arr[i] = arr[i]^arr[j];
        }
    }

    arr[left] = arr[i];
    arr[i] = base;

    return i;
}
// Quicksort is not recursive, because the reverse sort recurses too deeply and overflows
void quickSort(int *arr,int left,int right,int n)
{
    int *stackArr = (int*)malloc(sizeof(int) *10*n);
    int top = 0;

    int par = position(arr,left,right);

     / / into the stack
    if(par>left+1){
        stackArr[top++]=left;
        stackArr[top++]=par- 1;
    }
    if(par<right- 1){
        stackArr[top++]=par+1;
        stackArr[top++]=right;
    }
    while(top>0)
    {
        right=stackArr[--top];
        left=stackArr[--top];
        par=position(arr,left,right);
        if(par>left+1){
            stackArr[top++]=left;
            stackArr[top++]=par- 1;
        }
        if(par<right- 1){
            stackArr[top++]=par+1; stackArr[top++]=right; }}}int main(a)
{

    int *arrTemp;
    int n = 100000;
    int *arr=(int *) malloc(sizeof(int)*(n+10));// Array initialization
    clock_t startTime,endTime;
    srand((unsigned)time(NULL)); // Random number initialization
    getRandomArr(arr,n);


    cout<<"-------------- Bubble sort ------------------"<<endl;
    arrTemp = copyArr(arr,n);
    startTime = clock();
    miaoSort(arrTemp,n);
    endTime = clock();
    cout<<"Array size n="<<n<<", algorithm running time :"< < ((double)(endTime-startTime)/CLOCKS_PER_SEC)<<"s"<<endl;
    arrTemp = getReverseArr(arrTemp,n);
    startTime = clock();
    miaoSort(arrTemp,n);
    endTime = clock();
    cout<<"Array completely out-of-order run time :"< < ((double)(endTime-startTime)/CLOCKS_PER_SEC)<<"s"<<endl;


    cout<<"\n-------------- Select sort ------------------"<<endl;
    arrTemp = copyArr(arr,n);
    startTime = clock();
    xuanSort(arrTemp,n);
    endTime = clock();
    //display(arrTemp,20);
    cout<<"Array size n="<<n<<", algorithm running time :"< < ((double)(endTime-startTime)/CLOCKS_PER_SEC)<<"s"<<endl;
    arrTemp = getReverseArr(arrTemp,n);
    startTime = clock();
    xuanSort(arrTemp,n);
    endTime = clock();
    cout<<"Array completely out-of-order run time :"< < ((double)(endTime-startTime)/CLOCKS_PER_SEC)<<"s"<<endl;

    cout<<"\n-------------- ordered by Hill ------------------"<<endl;
    arrTemp = copyArr(arr,n);
    startTime = clock();
    sellSort(arrTemp,n);
    endTime = clock();
    //display(arrTemp,20);
    cout<<"Array size n="<<n<<", algorithm running time :"< < ((double)(endTime-startTime)/CLOCKS_PER_SEC)<<"s"<<endl;
    arrTemp = getReverseArr(arrTemp,n);
    startTime = clock();
    sellSort(arrTemp,n);
    endTime = clock();
    cout<<"Array completely out-of-order run time :"< < ((double)(endTime-startTime)/CLOCKS_PER_SEC)<<"s"<<endl;



    cout<<"\n-------------- Quicksort ------------------"<<endl;
    arrTemp = copyArr(arr,n);
    startTime = clock();
    quickSort(arrTemp,0,n- 1,n);
    endTime = clock();
    //display(arrTemp,20);
    cout<<"Array size n="<<n<<", algorithm running time :"< < ((double)(endTime-startTime)/CLOCKS_PER_SEC)<<"s"<<endl;
    arrTemp = getReverseArr(arrTemp,n);

    startTime = clock();
    quickSort(arrTemp,0,n- 1,n);
    endTime = clock();
    //display(arrTemp,20);
    cout<<"Array completely out-of-order run time :"< < ((double)(endTime-startTime)/CLOCKS_PER_SEC)<<"s"<<endl;

    return 0;
}




Copy the code