Thuật toán Sắp xếp nổi bọt - Thuật toán Bubble Sort trong C++

Thảo luận trong 'C/C++/C#' bắt đầu bởi Trương Minh Dương, 18/11/15.

Lượt xem: 603

  1. Trương Minh Dương

    Trương Minh Dương Đầy tớ nhân dân

    Thuật toán Sắp xếp nổi bọt (Bubble Sort) là một thuật toán sắp xếp đơn giản. Thuật toán sẽ đi so sánh các phần tử cạnh nhau, nếu đúng thứ tự sẽ so sánh các phần tử kế tiếp, ngược lại sẽ đổi chỗ 2 phần tử đó. Cứ lặp lại như vậy, đến phần tử cuối cùng của danh sách (hoặc mảng).


    [​IMG]
    thuat toan sap xep noi bot



    Thuật toán sắp xếp nổi bọt có thể gọi là thuật toán sắp xếp bằng so sánh trực tiếp.


    http://www.mediafire.com/?nh5g8be463brqnb



    Ý tưởng thuật toán:

    Xuất phát từ phần tử đầu tiên của danh sách (hay của mảng) đã cho ban đầu. Chúng ta so sánh với phần tử liền kề sau nó. Nếu phần tử đầu tiên nhỏ hơn phần tử đang xét thì đổi chỗ 2 phần tử đó với nhau và giữ nguyên vị trí nếu đúng.

    Lặp lại bước so sánh này đến phần tử thứ n-1 của danh sách (hay của mảng) ta sẽ thu được một danh sách được sắp theo thứ tự không giảm.



    Ví dụ: Sử dụng thuật toán Bubble Sort sắp xếp dãy số {3, 10, 4, 6, 2, 6, 15, 3, 9,7} theo thứ tự tăng dần.


    [​IMG]
    Sau 9 bước lặp ta thu được dãy đã được sắp xếp: {2, 3, 3, 4, 6, 6, 7, 9, 10, 15}


    Cài đặt thuật toán:

    Mã:
    void bubbleSort(int a[], int n){
        int swapped;
        do {
            swapped = 0;
            for (int i = 0; i < n; i++)
                if (a[i] > a[i+1]){
                    swap(a[i], a[i+1]);
                    swapped = 1;
                }
        } while (swapped == 1);
    }

    Thông tin chung:

    • Phân loại: Giải thuật sắp xếp
    • Cấu trúc dữ liệu: Ngẫu nhiên
    • Độ phức tạp: O(n²)
    • Phức tạp dữ liệu: Không tốn thêm vùng nhớ
    • Tối ưu: Không


    Cài đặt thuật toán sắp xếp nổi bọt (thuật toán Bubble Sort) đầy đủ
    Mã:
    #include <stdio.h>
    #include <stdlib.h>
    //#include <algorithm>
    
    //using namespace std;
    
    int* a;
    int n;
    
    void readData (char* fn){ //Doc du lieu dau vao
        FILE* f = fopen (fn,"r");
        fscanf (f,"%d",&n);
        a = new int [n+1];
        for (int i = 1; i <= n; i++)
            fscanf (f,"%d",&a[i]);
        fclose (f);
    }
      
    void print (){ //In ra danh sach
        for (int i = 1; i <= n; i++)
            printf("%d  ", a[i]);
    }
    
    void swap(int &a, int &b){
      int tmp = a;
      a = b;
      b = tmp;
    }
    
    void bubbleSort(int a[], int n){ //Thuat toan Bubble Sort
        int swapped;
        do {
            swapped = 0;
            for (int i = 0; i < n; i++)
                if (a[i] > a[i+1]){
                    swap(a[i], a[i+1]);
                    swapped = 1;
                }
        } while (swapped == 1);
    }
    
    int main (int argc, char** argv){
        char* filename = argv[1];
        readData(filename);
        printf("day ban dau la: ");
        print();
        printf ("n");
        bubbleSort(a,n);
        printf("day sau khi xep su dung Bubble Sort la: ");
        print();
    }

    LƯU Ý: Đây là code mình viết trên trình Notepad++ và sử dụng Cygwin (Phần mềm giả lập Linux) để dịch chương trình. Các bạn có thể theo dõi cách sử dụng Cygwin và cách sử dụng Cygwin để dịch chương trình C/C++ tại đây:

    http://minhduongit.com/huong-dan-su-dung-cygwin-dich-chuong-trinh-cc-bang-cygwin/

    Chúc các bạn học tập tốt !!!
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN

    Bình Luận Bằng Facebook

Chia sẻ trang này

Text Link: |Ban iPhone cu |Jailbreak iOS 9.3.3 |Tai lieu Swift Tieng Viet |Tao Boot USB |Antamedia Hotspot 4 Full Crack |Proshow Producer 7 Full Crack |Chu ky mau dep |Kiem tien tren mang |Ghost win 7 Full Soft |Ghost win 10 Full Soft |Ghost win XP Full Soft |Game Offline cho PC |Game Sex Offline |Game nhap vai luyen level |Game ban sung Offline |Game dan tran Offline |Game nhap vai hay |Hack Asphalt 8 |Hack ban ga 5 |Hack ban ga 6 |Game dua xe Offline |Tool tăng view Youtube |Kiếm tiền trên Youtube |SEO đề xuất Youtube |Kháng cáo Youtube |Lắp đặt internet viettel giá rẻ |Đăng ký cáp quang viettel miễn phí |lắp đặt Cáp Quang Viettel tại TPHCM |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack |Poke Map |Táo Quân 2017 |Hài Tết 2017 |Sitemap