Holiday first \(Blog\) is Pigeon's first semester ranking 233

Here are some common sorting and optimizations ~

• Insert Sort\((Insertion\)
• Select Sort\((Selection\) (Sort)\)
• Bubble Sorting((Bubble\) Sort\)
• Hill Sort\((Shell\) Sort\)
• Heap Sorting((Heap\) Sort\)
• Quick Sort\((Quick\) Sort\)
• Merge Sort\((Merge\)
• Cardinality Sort\((Radix\) (Sort))
• Sorting of balanced trees based on median traversal\((BBST\)(Sort)\)

First of all, there are too many references on the Internet about sorting principles. I'm giving you the simplest possible version organized in my own language. Second, this \(Blog\) is just a summary of these sorting algorithms. The main point is that it also falls on sorting optimization.Therefore, the reader needs to have a preliminary understanding of these orderings.

For code, refer to the \(sort\) function of \(STL\)
All functions are

sort(int *head,int *tail,bool cmp(int,int))

Formal declaration

Indicates that the elements in ([head,tail)\) are sorted
Other similar functions also indicate operations on this sequence of semi-closed and semi-open intervals
The default \(cmp\) function is consistent with \(STL\)

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

Default macro definition

#define rep(i,l,u,d) for(register int i=(l);i<=(u);i+=(d))
#define reb(i,u,l,d) for(register int i=(u);i>=(l);i-=(d))

In addition, some of the simpler subfunctions are lazy to code here

With regard to partial ordering, to avoid troubles, the defau lt is \(<\)
Popular descriptions are used elsewhere, such as "the smallest dollar" directly called "the smallest value"

Insert sort, select sort, bubble sort are the three most basic sort algorithms

The principles are summarized in a few words, not to mention any more:
Insert Sort: Continuously insert elements of an unordered sequence into an ordered sequence
Select Sort: Continuously select the minimum (large) value
Bubble sort: continuously exchange two adjacent disordered elements (disordered pairs)

Complexity and stability analysis:

sort order	Time Complexity	Spatial Complexity	stability
Insert Sort	\(O(n^2)\)	\(O(1)\)	Stable
Select Sort	\(O(n^2)\)	\(O(1)\)	Instable
Bubble sort	\(O(n^2)\)	\(O(1)\)	Stable

Code

Insert Sort

void insertion_sort(int *head,int *tail,bool (*cmp)(int,int)){
    for(int *i=head+1;i<tail;i++){
        int *p=i-1;
        while(p>=head&&cmp(*i,*p)) p--;
        int tmp=*i;
        for(int *j=i;j>p+1;j--) *j=*(j-1);
        p[1]=tmp;
    }
}

When looking for insertion positions, you can dichotomize

p=upper_bound(head,i,*i)-1;

Select Sort

void selection_sort(int *head,int *tail,bool (*cmp)(int,int)){
    for(int *i=head;i<tail-1;i++){
        int *p=i;
        for(int *j=i+1;j<tail;j++)
            if(cmp(*j,*p)) p=j;
        if(i<p) swap(*i,*p);
    }
}

Bubble sort

void bubble_sort(int *head,int *tail,bool (*cmp)(int,int)){
    for(int *i=tail-1;i>head;i--)
        for(int *j=head;j<i;j++)
            if(cmp(j[1],*j)) swap(*j,j[1]);
}

Shell Sort

Principle: Insert sorting is grouped by increment (or step) and decreases incrementally to one (which is equivalent to performing an insert sort), so Hill sorting is also called reduced incremental sorting

The complexity is affected by how the Hill sort increment decreases. Here are several common incremental sequences

• \(Shell\) Increment: \({1,2,4,...,2^n}\)
• \(Hibbard\) Increment: \({1,3,7,...,2^n-1}\)
• \(Knuth\) Increment: \({1,4,13,...,\frac{3^n-1}{2}}\)

Complexity and stability analysis:
Time Complexity: \(Shell\) Increment: \(O(n^2)\), Increment, \(Hibbard\) Increment, \(Knuth\) Increment: \(O(n^{\frac{3}{2})\
Spatial Complexity: \(O(1)\)
Stability: Unstable

Code

void shell_sort(int *head,int *tail,bool (*cmp)(int,int)){
    //Hibbard increment: n=max{x|2^x-1<=tail-head}, for (int i=2^n-1; i; (--i)>=1)
    //Knuth increment: n=max{x|(3^x-1)/2<=tail-head}, for(int i=3^n-1;i;(--i)/=3)
    //Shell Increment
    for(int i=(tail-head)>>1;i;i>>=1)
        for(int *j=head;j<head+i;j++) insertion_sort(j,tail,i);
}

Heap Sorting

Principle: Large (small) root heap keeps taking roots.

Heap sorting generally takes the form of an array of heaps, without additional auxiliary space. The required operation is \(heapify\), which can be understood as a general heap sink operation.When building a heap, move forward \(heapify\) from the last parent node, swap the root with the end of the array (head) and \(heapify\) once each time the root is taken after building.

Complexity and stability analysis:
Time Complexity: \(O(nlogn)\)
Spatial Complexity: \(O(1)\)
Stability: Unstable

Code

void heap_sort(int *head,int *tail,bool (*cmp)(int,int)){
    reb(i,(tail-head)>>1,1,1) heapify(head,tail,head+i-1);
    for(int *i=tail-1;i>head;i--) swap(*head,*i),heapify(head,i,head);
}

void heapify(int *head,int *tail,int *rt){
    int far=rt-head,son=(far<<1)+1,tmp=*rt;
    while(son<tail-head){
        if(son+1<tail-head&&cmp(head[son],head[son+1])) son++;
        if(cmp(head[son],tmp)) break;
        head[far]=head[son],far=son,son=(far<<1)+1;
    }
    head[far]=tmp;
}

Quick Sort

Principle: Take an element in an unordered sequence as the base number, move elements smaller than it to its left, other elements to its right, and then recursively perform this operation on the sequences on both sides of it

Complexity and stability analysis:
Time Complexity: \(O(n^2)\), Average Case: \(O(nlogn)\)
Spatial Complexity: \(O(n)\), Best Case: (O(logn)\)
Stability: Unstable

Code

void quick_sort(int *head,int *tail,bool (*cmp)(int,int)){
    if(head>=tail-1) return;
    int *lef=head,*rig=tail;
    while(true){
        while(cmp(*(++lef),*head)&&lef<tail-1);
        while(!cmp(*(--rig),*head)&&rig>head);
        if(lef>=rig) break;
        swap(*lef,*rig);
    }
    if(head<rig) swap(*head,*rig);
    quick_sort(head,rig),quick_sort(rig+1,tail);
}

It is more advantageous to use another sort when the sequence elements are less than a certain number, such as insert sort

if(tail-head<=bound){insertion_sort(head,tail);return;}

Default Sequence First as Base Number
On this basis, the random number method can be used
The base number randomly selects any element in the sequence

int p=rand()%(tail-head);swap(*head,head[p]);

Or use the three-digit method
Take the first, the last and the middle of the sequence as the base number after sorting.
\(sorted \median\) function: Sorts the three pointers passed in to the elements, returns the pointer to the intermediate elements

int *mid=head+((tail-head)>>1)-1;
int *p=sorted_median(head,mid,tail);
swap(*(head+1),*p),lef=head+1,rig=tail-1;

Tail recursive optimization can perform better when data is more extreme
\(partition\) function: Select the base number and divide the left and right series, return the pointer of the base number (in this case, the base number is between the left and right series)

void quick_sort(int *head,int *tail,bool (*cmp)(int,int)){
    if(head>=tail-1) return;
    while(head<tail-1){
        int *pivot=partition(head,tail);
        if(pivot-head<tail-pivot) quick_sort(head,pivot),head=pivot+1;
        else quick_sort(pivot+1,tail),tail=pivot;
    }
}

Three-way slicing optimization, each time the elements equal to the base number are placed in the middle, and then the sequences on both sides are recursively manipulated

void quick_sort(int *head,int *tail,bool (*cmp)(int,int)){
    if(head>=tail-1) return;
    int *lef=head,*rig=tail-1,*p=head+1,val=*lef;
    while(p<=rig){
        if(cmp(*p,val)) swap(*p,*lef),p++,lef++;
        else if(cmp(val,*p)) swap(*p,*rig),rig--;
        else p++;
    }
    quick_sort(head,lef),quick_sort(rig+1,tail);
}

Merge Sort

Principle: Merge two ordered sequences into one ordered sequence with the smaller first one at a time, and complete the process recursively

Complexity and stability analysis:
Time Complexity: \(O(nlogn)\)
Spatial Complexity: \(O(n)\)
Stability: Stability

Code

\(merge\) function: combines left and right ordered sequences into one ordered sequence

void merge_sort(int *head,int *tail,bool (*cmp)(int,int)){
    if(head>=tail-1) return;
    int *pivot=head+((tail-head)>>1);
    merge_sort(head,pivot),merge_sort(pivot,tail),merge(head,pivot,tail);
}

void merge(int *lef,int *mid,int *rig,bool (*cmp)(int,int)){
    int *tmp=new int[rig-lef+1];
    int *i=lef,*j=mid,p=0;
    while(i<mid&&j<rig)
        if(!cmp(*j,*i)) tmp[++p]=*(i++);
        else tmp[++p]=*(j++);
    while(i<mid) tmp[++p]=*(i++);
    while(j<rig) tmp[++p]=*(j++);
    rep(i,1,p,1) lef[i-1]=tmp[i];
    delete[] tmp;
}

Non-recursive optimization, where continuous merging of sequences is actually a process of doubling the length of a sequence, can be written as non-recursive

void merge_sort(int *head,int *tail,bool (*cmp)(int,int)){
    int i=2,*j;
    for(;i<tail-head;i<<=1){
        for(j=head;j<=tail-i;j+=i) merge(j,j+(i>>1),j+i);
        if(j>tail-i) merge(j,j+((tail-j)>>1),tail);
    }
    merge(head,head+(i>>1),tail);
}

Triple inversion optimization, the merging of left and right sequences, can be seen as inserting whole blocks of smaller elements from the right sequence into the left sequence, which can be accomplished with a triple inversion
For example, to insert \([b,c]\) in front of \((a<b\)), we can invert \([a,b-1]\) and \([b,c]\), then invert \([a,c]\), and invert the intervals \([a,b-1]\) and \([b,c]\) to invert the

\(triple\reverse\) function: triple inversion, right-left interval

void merge(int *lef,int *mid,int *rig,bool (*cmp)(int,int)){
    int *i=lef,*j=mid,*idx;
    while(i<j&&j<rig){
        while(!cmp(*j,*i)) i++;
        if(i==j) break;
        idx=j;
        while(cmp(*j,*i)) j++;
        triple_reverse(i,idx,j),i+=j-idx;
    }
}

Cardinality sorting

Principle: Allocate elements into ordered barrels by partial keycodes, arrange the barrels in order, and keep this relative position between elements in order until all keycodes are the same

Complexity and stability analysis:
Time Complexity: \(O(d(n+r)\), General: \(d=digit(max\{x|x \in array\}), r=10\)
Spatial Complexity: \(O(n+r)\)
Stability: Stability

Code

const int radix=10;

void radix_sort(int *head,int *tail,bool (*cmp)(int,int)){
    int *tmp=new int[tail-head+1],*cnt=new int[radix];
    int p=1,d=maxbit(head,tail);
    rep(i,1,d,1){
        rep(j,0,radix-1,1) cnt[j]=0;
        for(int *j=head;j<tail;j++) cnt[*j/p%radix]++;
        rep(j,1,radix-1,1) cnt[j]+=cnt[j-1];
        for(int *j=tail-1;j>=head;j--) tmp[cnt[*j/p%radix]--]=*j;
        rep(j,1,tail-head,1) head[j-1]=tmp[j];
        p*=10;
    }
    delete[] tmp,cnt;
}

Keycodes can have either the lowest bit priority ((LSD)\) or the highest bit priority ((MSD)\)

Sorting balanced trees based on median traversal

Principle: Once the balance tree is built (left subtree smaller than parent node\(value\), the other right subtrees), the order of middle traversal is the order of sorting

Complexity and stability analysis:
Time Complexity: \(O(nlogn)\)
Spatial Complexity: \(O(n)\)
Stability: Unstable

The tree used here is \(AVL\)

Code

typedef struct _node{
    int val,dep;
    _node *son[2];
    _node(int v=0,int d=0,_node *lef=nullptr,_node *rig=nullptr);
}node;

node::_node(int v,int d,node *lef,node *rig):val(v),dep(d),son{lef,rig}{
}

void bbst_sort(int *head,int *tail,bool (*cmp)(int,int)){
    node *rt=nullptr;
    for(int *i=head;i<tail;i++) insert(rt,*i);
    int p=-1;
    mid_order(rt,head,p);
    tree_free(rt);
}

void insert(node *&rt,int val){
    if(rt==nullptr){rt=new node(val,1);return;}
    int x=0;
    if(!cmp(val,rt->val)) x=1;
    insert(rt->son[x],val);
    if(depth(rt->son[x])-depth(rt->son[!x])==2)
        if((!x&&cmp(val,rt->son[0]->val))||(x&&!cmp(val,rt->son[1]->val))) rotate(rt,!x);
        else binary_rotate(rt,x);
    update(rt);
}

void mid_order(node *rt,int *ary,int &p){
    if(rt==nullptr) return;
    mid_order(rt->son[0],ary,p),ary[++p]=rt->val,mid_order(rt->son[1],ary,p);
}

void tree_free(node *rt){
    if(rt==nullptr) return;
    tree_free(rt->son[0]),tree_free(rt->son[1]),delete rt;
}

inline int depth(node *rt){
    return rt?rt->dep:0;
}

inline void update(node *rt){
    rt->dep=max(depth(rt->son[0]),depth(rt->son[1]));
}

inline void rotate(node *&rt,int x){
    node *tmp=rt->son[!x];
    rt->son[!x]=tmp->son[x],tmp->son[x]=rt;
    update(rt),update(tmp),rt=tmp;
}

inline void binary_rotate(node *&rt,int x){
    rotate(rt->son[!x],x),rotate(rt,!x);
}

qwq above

Next semester's data structure seems to need to be adjusted as well. Here's a preview review

Next, I'm going to sort out and collect information about network streaming. ~Please look forward to the possibility that nobody will see it anyway