Course design of data structure -- exchange sequencing assignment

Title Requirements:
Comparison of exchange sort
[basic requirements]
(1) Generate a set of random numbers to store in order and output.
(2) One way bubble sorting and two-way bubble sorting are used for sorting, and the comparison times and movement times of each algorithm are counted at the same time, and the results are displayed.
(3) The fast sorting method is used for sorting, and the number of comparison and movement are counted at the same time to display the results.
(4) Determine whether a set of data is in order.
(5) Set all odd numbers before even.
(6) Choose to do: find a set of data in the k-th position by value size (no need to sort).

#include<iostream>
#include<stdio.h>
#include<time.h>//Used to generate random numbers 
#include<stdlib.h> 
using namespace std;
#define maxsize 20
#define elemtype int
int a[maxsize],a1[maxsize],a2[maxsize],a3[maxsize];
int move1=0,com1=0,move2=0,com2=0,com3=0,move3=0; 

void swap(int *a,int *b){
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}
void bubble_sort(){
	int i,j,temp;
	bool mark=true;
	for(i=0;i<maxsize-1;i++){
		temp=false;
		for(j=0;j<maxsize-1-i;j++){
			if(a[j+1]<a[j]){
				swap(&a[j+1],&a[j]);
				move1++; 
				com1++;
				mark=true;
				}
				else{
					com1++;
				}
			if(mark==false)
				break;
		}
	}
}
void Double_Bubble_sort(){
	int i=0,j;
	bool mark=true;
	while(mark)
	{
		mark=false;
		for(j=i;j<maxsize-i-1;j++)//Scanning right
		{
			if(a1[j]>a1[j+1])
			{
				mark=true;
				swap(&a1[j],&a1[j+1]);
				move2++;com2++;
			}else com2++;
		}
		for(j=maxsize-i-1;j>i;j--)//Left scan
		{
			if(a1[j]<a1[j-1])
			{
				mark=true;
				swap(&a1[j],&a1[j-1]);
				move2++;com2++;
			}else com2++;
		}
		i++;//At the end of each scan, you can determine the location of an element at both ends
	}
}
void display(int b[]){
	for(int i=0;i<maxsize;i++){
		if(i!=maxsize-1)cout<<b[i]<<" ";//End space 
		else cout<<b[i]<<endl;
	}
} 
int get_mid(int b[],int left,int right){
	int pivot=b[left];
	while(left<right){
		while(b[right]>=pivot&&left<right) 
		{
			right--;
			com3++;
		}
		b[left]=b[right];
		com3++;move3++; 
		while(b[left]<=pivot&&left<right) 
		{
			left++;
			com3++;
		}
			b[right]=b[left];
			com3++;move3++;
		}  
	b[left]=pivot;
	move3++;
	return left;
}
void quick_sort(int b[],int left,int right){
	if(left<right){
	int mid=get_mid(b,left,right);
	quick_sort(b,left,mid-1);
	quick_sort(b,mid+1,right);                                                
	}
}
bool judgement_num(){
	int cc1[maxsize],i=0;
	 while(1){
	 	cin>>cc1[i];
	 	if(cc1[i]==-99999)break; 
	 	i++;
	 }
	 for(int j=0;j<i;j++){
	 	cout<<cc1[j]<<" ";
	 }
	 printf("\n");
	int temp=1;
	for(int j=0;j<i-1;j++){
		cout<<cc1[j+1]<<" "<<cc1[j];
		if(cc1[j+1]>cc1[j])cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		
		if(cc1[j+1]<cc1[j]){
			temp=0;
			break;
		}
	}
	if(temp==1)
		return true;
	else return false;  
}
void change_num(){
	int cc1[maxsize],i=0;
	 while(1){
	 	cin>>cc1[i];
	 	if(cc1[i]==-99999)break; 
	 	i++;
	 }
	 for(int j=0;j<i;j++){
	 	cout<<cc1[j]<<" ";
	 }
	 printf("\n");
	 int mark1=0,mark2=i-1;
	 while(1){
	 	while(cc1[mark1]%2!=0)mark1++;
	 	while(cc1[mark2]%2==0)mark2--;
	 	if(mark1>=mark2)
	 		break;
	 	swap(cc1[mark1],cc1[mark2]);
	 }
	 cout<<"The exchange is successful. Now all odd numbers are ahead of even numbers"<<endl;
	 for(int j=0;j<i;j++){
	 	cout<<cc1[j]<<" ";
	 }
	 printf("\n");
	 }
int find_max(int q[],int len){
	int max=0,i; 
	for(i=0;i<len;i++){
		if(q[i]>q[max])max=i;
	}	
	return max;
}
void find_k_num(){
	int cc1[maxsize],i=0,k,fre=0;
	 while(1){
	 	cin>>cc1[i];
	 	if(cc1[i]==-99999)break; 
	 	i++;
	 }
	 for(int j=0;j<i;j++){
	 	cout<<cc1[j]<<" ";
	 }
	 printf("\n");
	 cout<<"Please input K value"<<endl;
	 cin>>k;
	 while(fre<k-1){
	 	int ii=find_max(cc1,i);
	 	cc1[ii]=-77777;
	 	fre++;
	 }
	 int kk=find_max(cc1,i);
	 cout<<"Rank number one"<<k<<"The number of bits is"<<cc1[kk]<<endl; 
}

int main(){
 	srand((unsigned)time(NULL));//Generate random number 
 	cout<<"The original randomly generated array is:"; 
	for(int i=0;i<maxsize;i++){
		a[i]=rand()%100;
		a1[i]=a[i];a2[i]=a[i];a3[i]=a[i];
		if(i!=19)cout<<a[i]<<" ";//End space 
		else cout<<a[i]<<endl;
	}
	cout<<"One way bubble sorting array is:";
	bubble_sort();
	display(a);
	
	cout<<"The comparison times of unidirectional foaming are"<<com1<<endl;
	cout<<"The number of one-way bubbling movements is"<<move1<<endl; 
	
	
	cout<<"The original randomly generated array is:"; 
	display(a1);
	cout<<"The two-way bubble sorting array is:";
	Double_Bubble_sort();
	display(a1);
	cout<<"The comparison times of two-way bubbling are"<<com2<<endl;
	cout<<"The number of two-way bubbling movements is"<<move2<<endl; 
	cout<<"The original randomly generated array is:";
	display(a2);
	cout<<"The quick sort array is:";
	quick_sort(a2,0,maxsize-1);
	display(a2);
	cout<<"The comparison times of two-way bubbling are"<<com3<<endl;
	cout<<"The number of two-way bubbling movements is"<<move3<<endl; 
	cout<<"Please enter an array to judge the order(order)(-99999 End)"<<endl;
	bool aaa=judgement_num();
	if(aaa) cout<<"The array is an ordered array"<<endl;
	else cout<<"The array is unordered"<<endl;
	cout<<"Please enter an array of even and odd numbers to be swapped(order)(-99999 End)"<<endl;
	change_num(); 
	cout<<"Please enter the number of k Bit array(order)(-99999 End)"<<endl;
	find_k_num();
	return 0;
}
Published 3 original articles, won praise 4, visited 1182
Private letter follow

Posted on Tue, 17 Mar 2020 09:27:40 -0700 by SiMiE