Sort is simple to implement, simple and detailed (source code attached)

Simple implementation of sort

This article is intended for beginners and is designed to help them understand the implementation of sort.
Providing a detailed process and attaching the source code is also to encourage your own progress and encourage others.

Introduction

Read this article The basis is quick sorting and its optimization Click to jump, quick sorting and its optimization

Sorting algorithms are a fundamental problem in computer science, and there are many different ways to implement them. In this article, we will introduce a simple sort based on the implementation of a sorting algorithm that combines quick sort and insertion sort. This algorithm combines the efficiency of quick sort with the simplicity of insertion sort and is suitable for most data sets.

Algorithm implementation

First, we defined a namespace zhu and implemented the comparison function cmp, a comparison class CMP and the input and output function input. Next, we implemented quick sort _quick_sort and insertion sort insertion_sort, and finally, we combined the two in the Sort function.

include<iostream>
#include<functional>
using namespace std;

#define BEGINS(x) namespace x{
#defineENDS(x)}

BEGINS(zhu)

// comparison function
bool cmp(int a, int b){
    return a > b;
}

// Comparison class
class CMP{
public:
    bool cmp(int a, int b){
        return a < b;
    }
};

//Input and output functions
void input(int *first, int *last, const char *g){
    while(first != last){
        cout << *first << " ";
         + + first;
    }
    cout << endl;
}

// constant
const int length = 16;
//Quick sort
void _quick_sort(int *first, int *last, function<bool(int, int)> cmp = less<int>()){
    while(last - first > length){
        int *l = first, *r = last - 1;
        int v = *first;
        do{
        while(cmp(v, *l)) + + l;
        while(cmp(*r, v)) --r;
        if(l <= r) swap(*(l + + ), *(r--));
        }while(l <= r);
         _quick_sort(l, last, cmp);
          last = r + 1;
    }
    return;
}

// insertion sort
void inserion_sort(int *first, int *last, function<bool(int, int)> cmp = less<int>()){
    int *l = first;
    for(int *i = first + 1; i < last; i + + ){
        if(cmp(*i, *(i - 1))) l = i;
    }
    while(l != first){
        swap(*l, *(l - 1));
        l--;
    }
    for(int *i = first + 2; i < last; i + + ){
        int *j = i;
        while(cmp(*j, *(j - 1))){
            swap(*j, *(j - 1));
            j--;
        }
    }
    return;
}

//Combined sorting
void Sort(int *first, int *last, function<bool(int, int)> cmp = less<int>()){
    _quick_sort(first, last, cmp);
    insertion_sort(first, last, cmp);
}

ENDS(zhu)

Main function

In the main function, we demonstrate how to sort an array using our sorting algorithm. The user inputs the length and elements of the array, then calls the Sort function to sort, and finally outputs the result.

int main(){
    int a[100], n;
    cin >> n;
    for(int i = 1; i < n; i + + ){
        cin >> a[i];
    }
    zhu::Sort(a, a + n, zhu::cmp);
    zhu::input(a, a + n, "cmp:");
    return 0;
}

Complete code

Let us demonstrate our sorting algorithm with a simple example.

#include<iostream>
#include<functional>
using namespace std;

#define BEGINS(x) namespace x{
#defineENDS(x)}

BEGINS(zhu)

bool cmp(int a, int b){
    return a > b;
}

class CMP{
    public:
    bool cmp(int a, int b){
        return a < b;
    }

};

void input(int *first, int *last,const char *g){
    while(first != last){
        cout << *first << " " ;
         + + first;
    }
    cout << endl;
}

const int length = 16;
void _quick_sort(int *first, int *last, function<bool(int, int)> cmp = less<int>()){
    while(last - first > length){
        int *l = first, *r = last - 1;
        int v = *first;
        do{
        while(cmp(v, *l)) + + l;
        while(cmp(*r, v)) --r;
        if(l <= r) swap(*(l + + ), *(r--));
        }while(l <= r);
         _quick_sort(l, last, cmp);
          last = r + 1;
    }
    return;
}

void inserion_sort(int *first, int *last, function<bool(int, int)> cmp = less<int>()){
    int *l = first;
    for(int *i = first + 1; i < last; i + + ){
        if(cmp(*i, *(i - 1))) l = i;
    }
    while(l != first){
        swap(*l, *(l - 1));
        l--;
    }
    for(int *i = first + 2; i < last; i + + ){
        int *j = i;
        while(cmp(*j, *(j - 1))){
            swap(*j, *(j - 1));
            j--;
        }
    }
    return;
}
void Sort(int *first, int *last, function<bool(int, int)> cmp = less<int>()){
    _quick_sort(first, last, cmp);
    insertion_sort(first, last, cmp);
    return;

}

int main(){
    int a[100], n;
    cin >> n;
    for(int i = 1; i < n; i + + ){
        cin >> a[i];
    }
    Sort(a, a + n, cmp);
    input(a, a + n, "cmp:");
    return 0;
}

ENDS(zhu)

int main(){
    zhu::main();
    return 0;
}

Through the above, we have an in-depth understanding of the sorting algorithm based on the combination of quick sort and insertion sort, and implemented the corresponding sort code. This combined sorting approach may in some cases be more efficient than using quicksort or insertion sort alone. Readers can better understand the implementation and application of this sorting algorithm by reading the code and running examples

Sort optimization

When we write algorithms involving iterators, in order to enhance the flexibility and scalability of the code, we usually define some custom iterators. In the code you provided, the RandomIter class is an example of a simulated iterator

class RandomIter{
    public:
    RandomIter(int *ptr) : ptr(ptr){}
    int operator-(const RandomIter & amp;iter) {return ptr - iter.ptr;}
    int & amp;operator*(){return *ptr;}
    RandomIter & amp;operator + + (){ ptr + + ; return *this;}
    RandomIter & amp;operator--(){ ptr--; return *this;}
    RandomIter operator + (int x){return RandomIter(ptr + x);}
    RandomIter operator-(int x){return RandomIter(ptr - x);}
    RandomIter & amp;operator + + (int){ptr + + ; return *this;}
    RandomIter operator--(int){return RandomIter(ptr + 1);}
    bool operator<(const RandomIter & amp;iter) const {
        return ptr < iter.ptr;
    }
    bool operator<=(const RandomIter & amp;iter) const {
        return !(iter < *this);
    }
    bool operator==(const RandomIter & amp;iter) const{
        return !(iter < *this) & amp; & amp; !(*this < iter);
    }
    bool operator!=(const RandomIter & amp;iter) const {
        return !(iter == *this);
    }
    private:
    int *ptr;
};

Function analysis

• The BEGINS and ENDS macros are used to define the namespace. In this example, the namespace is zhu.
• The RandomIter class simulates the basic functions of iterators and is used to represent iterators in sorting algorithms.
• The CMP class defines a functor that can be used to compare elements.
• The _quick_sort function implements the quick sort algorithm, while the insertion_sort function implements the insertion sort algorithm.
• The sort function is an interface function that allows users to choose to use different comparison functions.
• The main function demonstrates how to use different comparison functions for sorting.

Full code:

#include
#include
using namespace std;

#define BEGINS(x) namespace x{
#defineENDS(x)}

BEGINS(zhu)
bool cmp(int a, int b){
    return a > b;
}

class CMP{
    public:
    bool operator()(int a, int b){
        return a < b;
    }
};

void output(int *first, int * last, const char * g){
    cout << g << endl;
    while(first != last){
        cout << *(first + + ) << " ";
    }
    cout << endl;
}

const int threshold = 16;


class RandomIter{
    public:
    RandomIter(int *ptr) : ptr(ptr){}
    int operator-(const RandomIter & amp;iter) {return ptr - iter.ptr;}
    int & amp;operator*(){return *ptr;}
    RandomIter & amp;operator + + (){ ptr + + ; return *this;}
    RandomIter & amp;operator--(){ ptr--; return *this;}
    RandomIter operator + (int x){return RandomIter(ptr + x);}
    RandomIter operator-(int x){return RandomIter(ptr - x);}
    RandomIter & amp;operator + + (int){ptr + + ; return *this;}
    RandomIter operator--(int){return RandomIter(ptr + 1);}
    bool operator<(const RandomIter & amp;iter) const {
        return ptr < iter.ptr;
    }
    bool operator<=(const RandomIter & amp;iter) const {
        return !(iter < *this);
    }
    bool operator==(const RandomIter & amp;iter) const{
        return !(iter < *this) & amp; & amp; !(*this < iter);
    }
    bool operator!=(const RandomIter & amp;iter) const {
        return !(iter == *this);
    }
    private:
    int *ptr;
};
void _quick_sort(RandomIter first, RandomIter last, function cmp = less()){
    while(last - first > 16){
        RandomIter l = first, r = last;
        int v = *first;
        do{
            while(cmp(v, *l)); + + l;
            while(cmp(*r, v)); --r;
            if(l <= r) swap(*(l + + ), *(r--));
        }while(l <= r);
        _quick_sort(l, last, cmp);
        last = r + 1;
    }
    return;
}

void inserion_sort(RandomIter first, RandomIter last, function cmp =less()){
    RandomIter ind = first;
    for(RandomIter i = first + 1; i < last; + + i){
        if(cmp(*i, *ind)) swap(*i, *ind);
    }

    while(first != ind){
        swap(*ind, *(ind - 1));
        --ind;
    }

    for(RandomIter i = first + 2; i < last; + + i){
        RandomIter j = i;
        while(cmp(*j, *(j - 1))){
            swap(*j, *(j - 1));
            --j;
        }
    }

    return;
}

void sort(RandomIter first, RandomIter last, function cmp = less()){
    _quick_sort(first, last, cmp);
    insertion_sort(first, last, cmp);
    return;
}
int main(){
    int a[100], x;
    cin >> x;
    for(int i = 0; i < x; i + + ){
        cin >> a[i];
    }
    sort(a, a + x, cmp);
    output(a, a + x, "cmp:");
    CMP cmp1;
    sort(a, a + x, cmp1);
    output(a, a + x, "cmp1:");
    return 0;
}
ENDS(zhu)

int main(){
    zhu::main();
    return 0;
}

Conclusion

This sorting algorithm example demonstrates a flexible and extensible sorting implementation in C++. By customizing the comparison function, users can flexibly choose the sorting strategy according to actual needs, making the code more versatile.

I hope this simple example will help you understand sorting algorithms and custom comparison functions in C++. If you have any questions or suggestions, please leave a message and let me know!