Shulou(Shulou.com)06/01 Report--

This article introduces the relevant knowledge of "how to use brute force method to solve bubble sorting in C++". In the operation process of actual cases, many people will encounter such difficulties. Next, let Xiaobian lead you to learn how to deal with these situations! I hope you can read carefully and learn something!

Algorithm idea:

Compare adjacent elements in the list and swap their positions if they are in reverse order. After repeating this a few times, the largest element moves to the last position. The second pass moves the second element to the next-to-last position, and so on until n-1 passes later, the list is complete.

C++#includeusing namespace std;int main(){ int i,j,temp,N; cin>>N; int *Arr=new int[N]; for(i=0;i>Arr[i]; for(i=0;ifor(j=0;jif(Arr[j]>Arr[j+1])//if reverse order, swap { temp=Arr[j]; Arr[j]=Arr[j+1]; Arr[j+1]=temp; } } } for(i=0;i" "; return 0;}

Algorithm analysis: the size of the input is completely determined by N, the basic operation is to compare: Arr[j]>Arr[j+1], time complexity C(n)=Θ(n2).

But the number of key swaps depends on the particular input, and the worst case is the reverse of what we want, where the number of key swaps = the number of key comparisons =Θ(n2).

But in the case of some inputs, if after comparing the list once, there are no elements exchanged, then the list is ordered and we can stop the algorithm. The specific improved versions are as follows:

#includeusing namespace std;int main(){ int i,j,temp,N; bool change=false; cin>>N; int *Arr=new int[N]; for(i=0;i>Arr[i]; for(i=0;ifalse; for(j=0;jif(Arr[j]>Arr[j+1])//if reverse order, swap { temp=Arr[j]; Arr[j]=Arr[j+1]; Arr[j+1]=temp; change=true; } } if(! change)//no change occurred, so there is no need to continue comparing. { break; } } for(i=0;i" "; return 0;}

But in the worst case, the time complexity is still Θ(n2).

"C++ how to use brute force to solve bubble sort" content is introduced here, thank you for reading. If you want to know more about industry-related knowledge, you can pay attention to the website. Xiaobian will output more high-quality practical articles for everyone!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.