Data structure sorting algorithm (simple selection, fast, half insertion sorting)

Table of Contents

1. Simple selection sorting

2. Quick sort

3. Half-way insertion sort

4. Data analysis

5. Source code analysis

1. Simple selection sort

//Simple selection sorting
void selection_sort(zstu &S,int sum){
bool desc;
cout<<"Please enter the sorting method (1 means from high to low and vice versa 0....):"<<endl;
cin>>desc;
      for(int i=0;i<sum-1;i + + ){
for(int j=i + 1;j<sum;j + + ){
if((desc & amp; & amp;S.snode[j]->grade>S.snode[i]->grade)||(!desc & amp; & amp;S.snode[j]->grade <S.snode[i]->grade)){
                 stu* temp=S.snode[i];
                S.snode[i]=S.snode[j];
S.snode[j]=temp;
}
}
}
} 

2. Quick sort

//Quick sort
int partition(zstu &S,int low,int high){
stu* val = S.snode[low];
while(low<high){
if(S.snode[high]->grade>val->grade){
high--;
}
S.snode[low]=S.snode[high];
\t  
      if(S.snode[low]->grade<val->grade){
low + + ;
}
S.snode[high]=S.snode[low];
}
S.snode[low]=val;
return low;
}

void QSort(zstu &S,int low,int high){
if(low<high){
//Save the data at the first position into stu*val
stu* val = S.snode[low];
\t\t
int pos=partition(S,low,high);
S.snode[pos] = val;
//Continue to recurse the data on the right after inserting val
QSort(S,low,pos-1);
//Recursively implement the data on the left
QSort(S,pos + 1,high);
}
}

3. Half-way insertion sort

//Sort by half insertion method
 void binary_insertion_sort(zstu & amp;S, int len, bool desc) {
    for (int i = 1; i <=len; i + + ) {
        stu*key = S.snode[i];
        int low = 0, high = i-1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if ((desc & amp; & amp;S.snode[mid]->grade<key->grade)||(!desc & amp; & amp;S.snode[mid]->grade>key->grade )) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for (int j = i-1; j >= high + 1; j--) {
            S.snode[j + 1] = S.snode[j];
        }
        S.snode[high + 1] =key;
    }
}

4. Data analysis

1. Input form and output value range;

Input form: Input students’ names and grades into a structure array. Output value range: The range of students’ grades is int type.

(1) Output form; output the three sorting results together. (2) The functions that the program can achieve: realize simple selection sorting function; realize quick sorting function; realize half insertion sorting function. (3) Test data: including correct input and output results and incorrect input and output results.

2. The flow of the main program and the calling relationship between each program module.

(1) Determine all functions that need to be implemented based on the experimental content.

Gradestroage(zstu &S): function to store student information;

selection_sort(zstu &S,int sum): simple selection sort;

partition(zstu & S, int low, int high): Find the position of the first data saved in stu*val (the right ones are smaller than this number and the left ones are larger than this number) and return this position

QSort(zstu & S, int low, int high): Execute recursive functions to perform quick sorting related operations;

Relevant code implementation:

void QSort(zstu &S,int low,int high){

if(low

//Save the data at the first position into stu*val

stu* val = S.snode[low];

int pos=partition(S,low,high);

S.snode[pos] = val;

//Continue to recurse the data on the right after inserting val

QSort(S,low,pos-1);

//Recursively implement the data on the left

QSort(S,pos + 1,high);

}

}

binary_insertion_sort(zstu & S, int len, bool desc): Algorithm implementation of half insertion sort

3. Function call flow chart in the program:

5. Source code analysis

#include
#include
#include
#include
#include
#include
#define OK 1
#define m 30
using namespace std;
typedef struct Student{
string name;
int grade;
}stu;
typedef struct S{
stu *snode[m];
}zstu;
//student data storage
static int sum=0;
void Gradestroage(zstu &S){
cout<<"Please enter the total number of students"<>sum;
system("cls");
     for(int i=0;i>S1->name>>S1->grade;
     S.snode[i]=S1;
}
}
//Simple selection sort
void selection_sort(zstu &S,int sum){
bool desc;
cout<<"Please enter the sorting method (1 means from high to low and vice versa 0....):"<>desc;
      for(int i=0;igrade>S.snode[i]->grade)||(!desc & amp; & amp;S.snode[j]->grade grade)){
                 stu* temp=S.snode[i];
                S.snode[i]=S.snode[j];
S.snode[j]=temp;
}
}
}
}
//quick sort
int partition(zstu &S,int low,int high){
stu* val = S.snode[low];
while(lowgrade>val->grade){
high--;
}
S.snode[low]=S.snode[high];
\t  
      if(S.snode[low]->gradegrade){
low + + ;
}
S.snode[high]=S.snode[low];
}
S.snode[low]=val;
return low;
}

void QSort(zstu &S,int low,int high){
if(lowname<<"\t"<grade<
It takes a lot of effort and hard work for bloggers to create articles, which is not easy! ! If it was helpful to you, please give it a like!
 Bloggers crave attention and appreciation from readers because it is the best recognition and encouragement for their hard work. 
Bloggers hope that readers can appreciate their professional knowledge and unique insights, and they also hope that readers can actively participate in discussions and share their opinions and experiences.
 Whether it's through likes, comments or shares, reader support is extremely important to bloggers. These affirmations and encouragement will motivate bloggers to work harder to create more valuable content and provide readers with practical technical guidance and industry insights.
 So, if you like the blogger’s articles, you might as well give them some attention and appreciation! Your support will become the driving force for their creation and will also make them more enthusiastic to bring you more exciting content. 
 ----------------
 Copyright statement: This article is an original article by CSDN blogger "Feng Yi Xiaoyi" and follows the CC 4.0 BY-SA copyright agreement. Please attach the original source link and this statement when reprinting.
 Original link: https://blog.csdn.net/m0_73620832/article/details/134070090


        The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57034 people are learning the system