Sắp xếp bong bóng php

Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong sê-ri thuật toán sắp xếp có minh họa mã sử dụng ngôn ngữ lập trình C++

Ở bài viết này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp bong bóng. Nội dung bài viết bao gồm các phần sau

• Ý tưởng của thuật toán
• Ví dụ minh họa
• Minh họa thuật toán sử dụng ngôn ngữ C++
• Đánh giá thuật toán

Lưu ý. Bài viết chỉ mô tả cho công việc sắp xếp dãy số tăng dần. Sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu

NỘI DUNG BÀI VIẾT

• Ý tưởng của thuật toán sắp xếp bong bóng
• Ví dụ minh họa
• Minh họa thuật toán sử dụng ngôn ngữ C++
• Đánh giá thuật toán sắp xếp sắp xếp bong bóng

Ý tưởng của thuật toán sắp xếp bong bóng

Thuật toán sắp xếp sắp xếp bong bóng thể thứcj sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nếu chúng đứng sai thứ tự(số sau bé hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi dãy

Ví dụ minh họa

Giả sử chúng ta cần sắp xếp dãy số [5 1 4 2 8] tăng dần này.
Tuần lặp đầu tiên.
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Tại đây, thuật toán sẽ so sánh hai phần tử đầu tiên và đổi chỗ cho nhau do 5 > 1.
( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Đổi chỗ làm 5 > 4
( 1 4 5 2 8 ) –> .
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Ở đây, hai phần tử đang xét đã đúng thứ tự (8 > 5), vậy ta không cần đổi chỗ.

Lần thứ 2.
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ) . Thuật toán sẽ cần thêm một lần lặp nữa để kết luận các dãy sắp xếp khi nó đi từ đầu đến cuối mà không có bất kỳ lần chuyển đổi nào được thực hiện.
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )
Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện.

Lần thứ 3.
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Minh họa thuật toán sử dụng ngôn ngữ C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

// Mã từ https. //nguyenvanhieu. vn

#include

void hoán đổi(int &x, int &y)

{

    int temp = x;

    x = y;

    y = nhiệt độ;

}

// Hàm sắp xếp sắp xếp bong bóng

void bubbleSort(int arr[], int n)

{

    int i, j;

    bool haveSwap = false;

    cho (i = 0; i < n-1; i++){

   // i phần tử cuối cùng sắp xếp

        có Hoán đổi = false;

        cho (j = 0; j < n-i-1; j++){

            if (arr[j] > arr[j+1]){

                        hoán đổi(arr[j], arr[j+1]);

                        có Hoán đổi = true; // Kiểm tra lần lặp này có swap không

            }

        }

        // Nếu không có hoán đổi nào được thực hiện => sắp xếp. Not to allow more

        nếu(có Hoán đổi == false){

            nghỉ;

        }

    }

}

/* Hàm xuất mảng */

void printArray(int arr[], int size)

{

    int i;

    cho (i=0; i < size; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

// Chương trình điều khiển để kiểm tra các chức năng trên

int chính()

{

    int arr[] = {64, 34, 25, 12, 22, 11, 90};

    int n = sizeof(arr)/sizeof(arr[0]);

    sắp xếp bong bóng(arr, n);

    printf("Mảng đã sắp xếp. \n");

    printArray(arr, n);

    return 0;

}

Ở đây, trong hàm bubbleSort, tôi sử dụng thêm một biến haveSwap để kiểm tra tại một lần thực hiện có xảy ra trường hợp thay đổi hai số không. Nếu không, ta có thể kết luận các mảng đã sắp xếp mà không cần phải thêm một lần nữa

Kiểm tra kết quả

1

2

Đã sắp xếp mảng.

11 12 22 25 34 64 90

Đánh giá thuật toán sắp xếp sắp xếp bong bóng

Độ phức tạp thuật toán

• Trường hợp tốt. Trên)
• trung bình. O(n^2)
• Bad Case. O(n^2)

Use not space memory. Ô(1)

Nếu bạn đang cần học lập trình ngôn ngữ lập trình, hay tìm đến các từ khóa học hay mà tôi chia sẻ ở mục từ khóa học nhé. Bạn hãy để lại những thắc mắc, ý kiến ​​đóng góp nếu có xuống mục bình luận ở cuối bài viết nhé

• THẺ
• C++
• giải thuật
• sắp xếp thuật toán

Facebook

Twitter

Pinterest

WhatsApp

Nguyễn Văn Hiếu

Sáng lập cộng đồng Lập Trình Không Khó với mong muốn giúp đỡ các bạn trẻ trên con đường trở thành những lập trình viên tương lai. Tất cả những gì tôi viết ra đây chỉ đơn giản là cơ sở thích ghi lại các kiến ​​thức mà tôi tích lũy được