Bubble sort

Summary

This chapter introduces bubble sorting in sorting algorithm , Focus on the idea of bubble sorting .

Catalog
1.  Introduction to bubble sort
2.  Bubble sort graphic description
3.  The time complexity and stability of bubble sorting
4.  Bubble sort implementation
4.1 Bubble sort C Realization
4.2 Bubble sort C++ Realization
4.3 Bubble sort Java Realization

Reprint please indicate the source ： Bubble sort - If the sky doesn't die - Blog Garden

---

More ： Data structure and algorithm series Catalog

Introduction to bubble sort

Bubble sort (Bubble Sort), Also known as bubble sort or foam sort .

It is a relatively simple sorting algorithm . It will traverse several secondary sequences , Every time I traverse , It will compare the size of two adjacent numbers from front to back ; If the former is bigger than the latter , Then swap their positions . such , After a traversal , The largest element is at the end of the sequence ！ When traversing again in the same way , The second largest element is arranged before the largest element . Repeat this operation , Until the whole sequence is in order ！

Bubble sort graphic description

Bubble sort C Achieve one

void bubble_sort1(int a[], int n)
{
    int i,j;

    for (i=n-1; i>0; i--)
    {
        //  take a[0...i] The largest data in is placed at the end 
        for (j=0; j<i; j++)
        {
            if (a[j] > a[j+1])
                swap(a[j], a[j+1]);
        }
    }
}

The following is a sequence of numbers {20,40,30,10,60,50} For example , Demonstrate its bubble sorting process ( Here's the picture ).

Let's first analyze the 1 Trip to sort
When i=5,j=0 when ,a[0]<a[1]. here , Do nothing ！
When i=5,j=1 when ,a[1]>a[2]. here , In exchange for a[1] and a[2] Value ; After the exchange ,a[1]=30,a[2]=40.
When i=5,j=2 when ,a[2]>a[3]. here , In exchange for a[2] and a[3] Value ; After the exchange ,a[2]=10,a[3]=40.
When i=5,j=3 when ,a[3]<a[4]. here , Do nothing ！
When i=5,j=4 when ,a[4]>a[5]. here , In exchange for a[4] and a[5] Value ; After the exchange ,a[4]=50,a[3]=60.

therefore , The first 1 After sorting , The sequence {20,40,30,10,60,50} Turned into {20,30,10,40,50,60}. here , The value at the end of the sequence is the largest .

According to this method ：
The first 2 After sorting , In sequence a[5...6] Is ordered .
The first 3 After sorting , In sequence a[4...6] Is ordered .
The first 4 After sorting , In sequence a[3...6] Is ordered .
The first 5 After sorting , In sequence a[1...6] Is ordered .

The first 5 After a sequence of times , The whole sequence is ordered .

Bubble sort C Achieve two

Observe the flow chart of bubble sorting above , The first 3 After a sequence of times , The data is already in order ; The first 4 Hu Hedi 5 There is no data exchange in this trip .
Let's optimize bubble sorting , Make it more efficient ： Add a tag , If an exchange occurs in a single pass , Then it is marked with true, Otherwise false. If there is no exchange on a certain trip , Indicates that the sorting is complete ！

void bubble_sort2(int a[], int n)
{
    int i,j;
    int flag;                 //  Mark 

    for (i=n-1; i>0; i--)
    {
        flag = 0;            //  The initialization flag is 0

        //  take a[0...i] The largest data in is placed at the end 
        for (j=0; j<i; j++)
        {
            if (a[j] > a[j+1])
            {
                swap(a[j], a[j+1]);
                flag = 1;    //  In case of exchange , Set the flag to 1
            }
        }

        if (flag==0)
            break;            //  If there is no exchange , The sequence is in order .
    }
}

The time complexity and stability of bubble sorting

Bubble sort time complexity

The time complexity of bubble sorting is O(N2).
Let's assume that the sequence being sorted has N Number . The time complexity of traversing a trip is O(N), How many times does it take to traverse ？N-1 Time ！ therefore , The time complexity of bubble sorting is O(N2).

Bubble sorting stability

Bubble sorting is a stable algorithm , It satisfies the definition of stable algorithm .
Algorithm stability -- Let's assume that there exists in a sequence a[i]=a[j], If before sorting ,a[i] stay a[j] front ; And after sorting ,a[i] Still in a[j] front . Then the sorting algorithm is stable ！

Bubble sort implementation

Bubble sort C Realization
Implementation code (bubble_sort.c)

/**
 *  Bubble sort ：C  Language 
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <stdio.h>

//  The length of the array 
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
//  Interactive values 
#define swap(a,b)    (a^=b,b^=a,a^=b)

/*
 *  Bubble sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void bubble_sort1(int a[], int n)
{
    int i,j;

    for (i=n-1; i>0; i--)
    {
        //  take a[0...i] The largest data in is placed at the end 
        for (j=0; j<i; j++)
        {
            if (a[j] > a[j+1])
                swap(a[j], a[j+1]);
        }
    }
}

/*
 *  Bubble sort ( Improved version )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void bubble_sort2(int a[], int n)
{
    int i,j;
    int flag;                 //  Mark 

    for (i=n-1; i>0; i--)
    {
        flag = 0;            //  The initialization flag is 0

        //  take a[0...i] The largest data in is placed at the end 
        for (j=0; j<i; j++)
        {
            if (a[j] > a[j+1])
            {
                swap(a[j], a[j+1]);
                flag = 1;    //  In case of exchange , Set the flag to 1
            }
        }

        if (flag==0)
            break;            //  If there is no exchange , The sequence is in order .
    }
}

void main()
{
    int i;
    int a[] = {20,40,30,10,60,50};
    int ilen = LENGTH(a);

    printf("before sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");

    bubble_sort1(a, ilen);
    //bubble_sort2(a, ilen);

    printf("after  sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");
}

Bubble sort C++ Realization
Implementation code (BubbleSort.cpp)

/**
 *  Bubble sort ：C++
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <iostream>
using namespace std;

/*
 *  Bubble sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void bubbleSort1(int* a, int n)
{
    int i,j,tmp;

    for (i=n-1; i>0; i--)
    {
        //  take a[0...i] The largest data in is placed at the end 
        for (j=0; j<i; j++)
        {
            if (a[j] > a[j+1])
            {
                //  In exchange for a[j] and a[j+1]
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

/*
 *  Bubble sort ( Improved version )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void bubbleSort2(int* a, int n)
{
    int i,j,tmp;
    int flag;                 //  Mark 

    for (i=n-1; i>0; i--)
    {
        flag = 0;            //  The initialization flag is 0

        //  take a[0...i] The largest data in is placed at the end 
        for (j=0; j<i; j++)
        {
            if (a[j] > a[j+1])
            {
                //  In exchange for a[j] and a[j+1]
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;

                flag = 1;    //  In case of exchange , Set the flag to 1
            }
        }

        if (flag==0)
            break;            //  If there is no exchange , The sequence is in order .
    }
}

int main()
{
    int i;
    int a[] = {20,40,30,10,60,50};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    bubbleSort1(a, ilen);
    //bubbleSort2(a, ilen);

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

Bubble sort Java Realization
Implementation code (BubbleSort.java)

/**
 *  Bubble sort ：Java
 *
 * @author skywang
 * @date 2014/03/11
 */

public class BubbleSort {

    /*
     *  Bubble sort 
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     n --  Length of array 
     */
    public static void bubbleSort1(int[] a, int n) {
        int i,j;

        for (i=n-1; i>0; i--) {
            //  take a[0...i] The largest data in is placed at the end 
            for (j=0; j<i; j++) {

                if (a[j] > a[j+1]) {
                    //  In exchange for a[j] and a[j+1]
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
    }

    /*
     *  Bubble sort ( Improved version )
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     n --  Length of array 
     */
    public static void bubbleSort2(int[] a, int n) {
        int i,j;
        int flag;                 //  Mark 

        for (i=n-1; i>0; i--) {

            flag = 0;            //  The initialization flag is 0
            //  take a[0...i] The largest data in is placed at the end 
            for (j=0; j<i; j++) {
                if (a[j] > a[j+1]) {
                    //  In exchange for a[j] and a[j+1]
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;

                    flag = 1;    //  In case of exchange , Set the flag to 1
                }
            }

            if (flag==0)
                break;            //  If there is no exchange , The sequence is in order .
        }
    }

    public static void main(String[] args) {
        int i;
        int[] a = {20,40,30,10,60,50};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        bubbleSort1(a, a.length);
        //bubbleSort2(a, a.length);

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }
}

above 3 The principle and output of the two implementations are the same . Here is their output ：

before sort:20 40 30 10 60 50 
after  sort:10 20 30 40 50 60