Use brute force to solve bubble sort

Bubble sort is another classic embodiment of brute force method.

Algorithmic idea: Compare adjacent elements in the list, and if they are in reverse order, exchange their positions. After repeating it many times, the largest element is ranked last. The second operation moves the second element to the penultimate position, and the comparison continues until n-1 times, and the entire list is sorted.

The following is my code implementation: C

#include 
using namespace std;
int main()
{
    int i,j,temp,N;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;i<n for if>Arr[j+1])//如果逆序，就交换
            {
                temp=Arr[j];
                Arr[j]=Arr[j+1];
                Arr[j+1]=temp;
            }
        }
    }
 
    for(i=0;i<n cout return>
<p>Algorithm analysis: The size of the input is completely determined by N. The basic operation is comparison: Arr[j]>Arr[j 1], time complexity C(n)=Θ(n2).</p>
<p>But the number of key exchanges depends on the specific input. The worst case is the opposite of the sorting we require. At this time, the number of key exchanges = the number of key comparisons = Θ(n2).</p>
<p>But in some input situations, if after comparing the list, the positions of the elements are not exchanged, then the list is already in order, and we can stop the algorithm. The specific improved version is as follows: </p>
<pre class="brush:php;toolbar:false">#include 
using namespace std;
int main()
{
    int i,j,temp,N;
    bool change=false;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;i<n change="false;" for if>Arr[j+1])//如果逆序，就交换
            {
                temp=Arr[j];
                Arr[j]=Arr[j+1];
                Arr[j+1]=temp;
                change=true;
            }
        }
        if(!change)//没有发生交换，则不用继续比较了。
        {
            break;
        }
    }
 
    for(i=0;i<n cout return>
<p>But in the worst case, the time complexity is still Θ(n2).</p></n></n></n>

The above is the detailed content of Use brute force to solve bubble sort. For more information, please follow other related articles on the PHP Chinese website!