Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: Các thuật toán sắp xếp trong lập trình C | Cấu trúc dữ liệu và giải thuật

  1. #1
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    168

    Mặc định Các thuật toán sắp xếp trong lập trình C | Cấu trúc dữ liệu và giải thuật

    Các thuật toán sắp xếp trong lập trình C


    Sắp xếp các nút của một cấu trúc theo thứ tự tăng dần (hay giảm dần) là một công việc được thực hiện thường xuyên. Với một cấu trúc đã được sắp xếp chúng ta rất thuận tiện khi thực hiện các tác vụ trên cấu trúc như tìm kiểm, trích lọc, duyệt cấu trúc ....
    Có hai loại giải thuật sắp xếp được dùng phổ biến trong khoa học máy tính là sắp xếp nội (internal sorting) và sắp xếp ngoại (external sorting):
    1. Với loại sắp xếp nội thì toàn bộ dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, do vậy kich thước dữ liệu cần sắp xếp không lớn, tuy nhiên thời gian sắp xếp được thực hiện rất nhanh.
    2. Với loại sắp xếp ngoại thì chỉ một phần nhỏ dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, phần lớn dữ liệu còn lại được lưu ở bộ nhớ ngoài (như đĩa từ băng từ, ...), kích thước dữ liệu cần sắp xếp lúc này rất lớn (phụ thuộc vào kích thước của đĩa từ, băng từ, ...), và thời gian sắp xếp thực hiện rất chậm.

    Sau đây ta chỉ nguyên cứu về giải thuật sắp xếp nội
    (giới thiệu qua để cho các bạn có một cái nhìn khoa học hơn về giải thuật sắp xếp, he he nghe có vẻ to tát nhể nhưng thật ra chẳng có gì cả ke ke )

    Nội dung sẽ trình bầy:
    1. Bubble sort.
    2. Quick sort.
    3. Simple selection sort.
    4. Heap sort.
    5. Simple insertion sort.
    6. Shell sort.
    7. Merge sort.

    (các phần sẽ dần dần được post lên đề nghị các bạn không chen ngang khi tác giả chưa hoàn thành seri bài viết)
    Đã được chỉnh sửa lần cuối bởi iamvtn : 03-03-2008 lúc 11:12 PM.

  2. #2
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    168

    Mặc định Bubble sort (sắp xếp bằng cách đổi chỗ)

    Bubble sort (sắp xếp bằng cách đổi chỗ)

    I. Mô tả phương pháp:

    Phương pháp này sẽ duyệt danh sách nhiều lần, trong mỗi lần duyệt sẽ lần lượt so sánh cặp nút thứ i và thứ i+1 và đổi chỗ hai nút này nếu chúng không đúng thứ tự.
    Ví dụ cho một dãy số đơn giản và sắp xếp cho nó tăng dần.
    25 55 45 90 10
    Và đây sẽ minh họa quá trình so sánh và đổi chỗ trong lần duyệt đầu tiên.
    So sánh nút thứ i với nút thứ i+1 nếu nút thứ i > nút i+1 thì đổi chỗ 2 nút với nhau. Nếu không tiếp tục so sánh tiếp.
    1. So sánh 25 với 55:kiểm tra 25 < 55 -> Sai không đổi chỗ.
    2. So sánh tiếp 55 với phần tử tiếp theo là 45: 55 > 45 -> Đúng đổi chỗ 45 với 55
    3. So sánh tiếp 55 với 90: 55 < 90 -> sau không đổi chỗ.
    4. So sánh tiếp 90 với 10: 90 > 10 -> đúng đổi chỗ 90 cho 10.

    Danh sách sau khi biến đổi lần thứ nhất.
    25 45 55 10 90.
    Ta nhận thấy phần tử 90 lớn nhất được đưa về cuối danh sách, cứ tuần tự kiểm tra n lần như vậy ta sẽ được một danh sách tăng dần.

    OK chắc các bạn hiểu ý tưởng rồi chứ (dễ như ăn kẹo) .

    Tiếp giờ ta sẽ Mô Tả Giải Thuật Bubble Sort
    C++ Code:
    1. Dữ liệu nhập: Danh sách n nút chưa sắp xếp.
    2. Dữ liệu xuất: Danh sách n nút đã sắp xếp.
    3. Biến tạm: doicho
    4. Hành động:
    5. Gán doicho = true;
    6. for(int i = 1;i < n && doicho = true;i++)
    7.  {
    8.       Gán doicho = flase;
    9.       for(j = 0;i < n-1; j++)
    10.           if(nodes[j] > nodes[j+1]))
    11.           {
    12.                 Gán doicho = true;  
    13.                 Đỗi chỗ cho hai nút tại vị trí j và j+1
    14.           }
    15.  }
    16. Kết thúc

    Cài đặt giải thuật Bubble sort
    C++ Code:
    1. void BubbleSort(int nodes[],int n)  // n la so phan tu trong mang nodes[]
    2. {
    3.     int temp,i,j;
    4.    bool doicho = true;
    5.    for(i = 1; i < n && doicho == true; i++)
    6.    {
    7.     doicho = false;
    8.       for(j = 0;j < n-i; j++)
    9.             if(nodes[j] < nodes[j+1])
    10.         {
    11.             doicho = true;
    12.             temp = nodes[j];
    13.             nodes[j] = nodes[j+1];
    14.             nodes[j+1] = temp;
    15.         }
    16.    }
    17. }
    Nhận xét: Giải thuật bubble sort dễ hiểu nhưng không tối ưu vì thời gian thực hiện giải thuật chậm.

    cheer! (bắt trước anh ccom phát )
    (còn tiếp)
    Đã được chỉnh sửa lần cuối bởi iamvtn : 04-03-2008 lúc 12:29 AM.

  3. #3
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    168

    Mặc định Quick Sort - Sắp xếp nhanh

    Quick Sort


    Quick sort là phương pháp đổi chỗ từng phần (partition exchange), đây là phương pháp rất hiệu quả, rất thông dụng..
    Nội dung của phương pháp này như sau:
    Chọn một nút bất kỳ trong danh sách(Giả sử là nút đầu tiên) gọi là nút làm trục (pivot node), xác định vị trí hợp lệ của nút này trong danh sách (gọi là vị trí pivot).
    Tiếp theo chúng ta phân hoạch các nút còn lại trong danh sách cần sắp xếp sao cho từ vị trí 0 đến vị trí pivot-1 đều có nội dung nhỏ hơn hoặc bằng nút làm trục, các nút từ vị trí pivot+1 đến n-1 đều có nội dung lớn hơn nút làm trục.
    Quá trình lại tiếp tục như thế với hai danh sahs con từ trị trí 0 đến vị trí pivot-1 và từ vị trí pivot+1 đến vị trí n-1, ... Sau cùng chúng ta sẽ được danh sách có thứ tự.

    Mô tả giải thuật Quick sort
    Alg Code:
    1. Giai thuat: QuickSort(nodes[], low, up)
    2. Mo Ta; Giair thuat QuickSort, dung phuong phap de qui sawp xep va cac nut trong danh sach giua hai vi tri
    3.         low va up
    4. Du Lieu nhap:
    5.     - Danh sach cac nut chua sap xep (giua hai vi tri low va up)
    6.         - low va up
    7. Du Lieu Xuat:
    8.     Danh sach cac nut (giua hai vi tri low va up) da duoc sap xep
    9.  
    10. Hanh dong
    11.     if(low >= up) // dieu kien dung
    12.     ket thuc giai thuat
    13.    if(low < up)
    14.     - Phan hoach: partition(nodes[], low, up, pivot)
    15.         + partition phan danh sach thanh ba phan:
    16.             * nut lam truc: nodes[low] tro thanh nodes[pivot]
    17.             * danh sach con 1: nodes[i] <= nodes[pivot]
    18.                 (voi i < pivot)
    19.             * danh sach con 2: nodes[i] > nodes[pivot]
    20.                 (voi i > pivot)
    21.       - Goi de qui: QuickSort(nodes[], low, pivot-1)
    22.       - Goi de qui: QuickSort(nodes[], pivot+1, up)
    23. Ket Thuc
    Giải thuật Partion
    vấn đề tiếp theo là giải thuật partition giúp phân danh sách làm ba phần:
    • Nút đầu (nút làm trục) đặt ở vị trí pivot
    • Danh sách con 1 từ vị trí low đến pivot-1 có nội dung nhỏ hơn hay bằng nút làm trục.
    • Danh sách con 2 từ vị trí low đến pivot+1 có nội dung lớn hơn hay bằng nút làm trục.

    Người ta xử lý giải thuật partition theo mô tả như sau:
    1. Chọn nodes[low] (nút đầu tiền) là nút làm trục.
    2. Quét danh sách theo hai hướng để đổi chỗ các cặp nút "sai" vị trí, nơi gặp nhau của hai hướng quét chính là vị trí pivot:
    Quét từ low lên: con trỏ l xuất phát từ vị trí low và tăng dần lên, dừng lại khi gặp nút có nội dung lớn hơn nút làm trục, ghi nhận vị trí l lúc này.
    • Quét từ up xuống: con trỏ u xuất phát từ vị trí up và giảm dần xuống, dừng lại khi gặp nút có nội dung nhỏ hơn hay bằng nút làm trục, ghi nhận vị trí u lúc này.
    • Đổi chỗ hai nút tại vi trí l và u.
    • Cứ tiếp tục quét theo hai hướng và đổi chỗ các cặp nút "sai" vị trí, quá trình này dừng lại khi l = u (hai hướng quét gặp nhau), nợi gặp nhau chính là vị trí pivot (pivot = u = l).

    3. Đổi chỗ hai nút tại vị trí low (nút làm trục) và nút tại vị trí pivot.

    Sau đây là giải thuật partition
    Alg Code:
    1. Giai Thuat: partition(nodes[], low, up, pivot)
    2. Mo Ta: Giai thuat partition, phan danh sach thanh 3 phan ...
    3. Du Lieu Nhap:
    4.     Danh sach cac nut trong khoang vi tri tu low den up.
    5. Du Lieu Xuat:
    6.     Dua nut lam truc ve vi tri pivot, doi cho cac nut trong danh sach
    7.    sao cho cac nut co noi dung nho hon hay bang nut lam truc duoc
    8.    bo tri truoc nut lam truc, cac nut co noi dung lon hon nut lam
    9.    truc duoc bo tri sau nut lam truc.
    10. Hanh Dong
    11.     1. Chon nodes[low] la nut lam truc
    12.         Gan: l = low;
    13.           u = up;
    14.    2.   while(l < u) // vong lap xu ly hai huong quet
    15.     {
    16.            Quet huong tu low len, dung lai khi gap nut lon hon nut lam truc,
    17.            ghi nhan vi tri l luc nay
    18.  
    19.            Quet huong tu up xuong, dung lai khi gap nut nho hon hay bang
    20.            nut lam truc, ghi nhan vi tri u luc nay
    21.  
    22.            Doi cho hai nut tai hai vi tri l va u
    23.       }
    24.  
    25.    3.   Doi cho hai nut tai hai vi tri low va u (luc nay pivot = u)
    26. Ket Thuc

    Cài đặt giải thuật QuickSort
    Sau đây là hàm QuickSort() dùng phương pháp đệ qui, hàm này có gọi hàm partition() để phân hoạch danh sách con thành 3 phần.
    Hàm QuickSort()
    C++ Code:
    1. void QuickSort(int nodes[], int low, int up)
    2. {
    3.    int pivot;
    4.    if(low >= up)   // dieu kien dung
    5.     return;
    6.  
    7.    if(low < up)
    8.    {
    9.         partition(nodes, low, up, &pivot);
    10.        QuickSort(nodes, low, pivot - 1);
    11.        QuickSort(nodes, pivot + 1, up);
    12.    }
    13. }
    Hàm partition():
    C++ Code:
    1. void partition(int nodes [], int low, int up, int *pivot)
    2. {
    3.    int nuttruc, l, u, temp;
    4.    nuttruc = nodes[low]; // Chon nut dau lam nut truoc
    5.    l = low;
    6.    u = up;
    7.    while(l < u)
    8.    {
    9.       while(nodes[l] <= nuttruc && l < up)
    10.             l++;
    11.       while(nodes[u] > nuttruc)
    12.            u--;
    13.       if(l < u)
    14.       {
    15.         // doi cho cap nut sai vi tri
    16.          temp = nodes[l];
    17.          nodes[l] = nodes[u];
    18.          nodes[u] = temp;
    19.       }
    20.    }
    21.    // doi cho hia nut tai low va u (luc nay u la vi tri nut truc)
    22.    nodes[low] = nodes[u];
    23.    nodes[u] = nuttruc;
    24.    *pivot = u;
    25. }

    Nhận xét, so sánh
    • Quick Sort phức tạp hơn Bubble Sort nhưng hiệu quả hơn.
    • Quick Sort thích hợp cho danh sách ban đầu chưa có thứ tự.
    • Quick Sort kém hiệu quả khi danh sách ban đầu gần có thứ tự. Đặc biệt với danh sách dã có thứ tự (lớn dần hoặc nhở dần) lại là trường hợp xấu nhất của giải thuật Quick Sort.



    Chương trình minh họa sắp xếp một mảng kiểu int
    C++ Code:
    1. #include <iostream.h>
    2. #include <conio.h>
    3. void partition(int nodes [], int low, int up, int *pivot);
    4. void QuickSort(int nodes[], int low, int up)
    5. {
    6.     int pivot;
    7.    if(low >= up)   // dieu kien dung
    8.     return;
    9.    if(low < up)
    10.    {
    11.         partition(nodes, low, up, &pivot);
    12.       QuickSort(nodes, low, pivot - 1);
    13.       QuickSort(nodes, pivot + 1, up);
    14.    }
    15. }
    16.  
    17. void partition(int nodes [], int low, int up, int *pivot)
    18. {
    19.     int nuttruc, l, u, temp;
    20.    nuttruc = nodes[low]; // Chon nut dau lam nut truoc
    21.    l = low;
    22.    u = up;
    23.    while(l < u)
    24.    {
    25.         while(nodes[l] <= nuttruc && l < up)
    26.         l++;
    27.       while(nodes[u] > nuttruc)
    28.         u--;
    29.       if(l < u)
    30.       {
    31.         // doi cho cap nut sai vi tri
    32.          temp = nodes[l];
    33.          nodes[l] = nodes[u];
    34.          nodes[u] = temp;
    35.       }
    36.    }
    37.    // doi cho hia nut tai low va u (luc nay u la vi tri nut truc)
    38.    nodes[low] = nodes[u];
    39.    nodes[u] = nuttruc;
    40.    *pivot = u;
    41. }
    42.  
    43.  
    44. void main()
    45. {
    46.     int mang[7];
    47.    for(int i = 0;i < 7;i++)
    48.    {
    49.     cout<<"Nhap vao phan tu thu "<<(i+1)<<": ";
    50.         cin>>mang[i];
    51.    }
    52.    cout<<endl;
    53.    for(int i = 0;i < 7;i++)
    54.    {
    55.         cout<<mang[i]<<"  ";
    56.    }
    57.    QuickSort(mang, 0, 7);
    58.    cout<<endl<<endl<<"danh sach sau khi da sap xep: ";
    59.    for(int i = 0;i < 7;i++)
    60.    {
    61.         cout<<mang[i]<<"  ";
    62.    }
    63.     getch();
    64. }
    Đã được chỉnh sửa lần cuối bởi iamvtn : 04-03-2008 lúc 10:10 AM.

  4. #4
    Ngày gia nhập
    07 2007
    Bài viết
    7

    Mặc định Simple selection sort

    Viết tiếp hộ vtn
    Simple selection sort.


    Tư tưởng:


    Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

    Các bước tiến hành như sau:

    Bước 1: i=1

    Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]

    Bước 3: Hoán vị a[min] và a[i]

    Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2

    Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.

    Ví dụ: Cho dãy a = (12,2,8,5,1,6,4,15)

    12 2 8 5 1 6 4 15

    Bước 1: 1 2 8 5 12 6 4 15

    Bước 2: 1 2 8 5 12 6 4 15

    Bước 3: 1 2 4 5 12 6 8 15

    Bước 4: 1 2 4 5 12 6 8 15

    Bước 5: 1 2 4 5 6 12 8 15

    Bước 6: 1 2 4 5 6 8 12 15

    Bước 7: 1 2 4 5 6 8 12 15

    Code

    C++ Code:
    1. #include <iostream.h>
    2.  
    3. void selectionSort(int *array,int length)//selection sort function
    4. {
    5.     int i,j,min,minat;
    6.     for(i=0;i<(length-1);i++)
    7.     {
    8.         minat=i;
    9.         min=array[i];
    10.  
    11.             for(j=i+1;j<(length);j++) //select the min of the rest of array
    12.         {
    13.           if(min>array[j])   //ascending order for descending reverse
    14.           {
    15.               minat=j;  //the position of the min element
    16.               min=array[j];
    17.           }
    18.         }
    19.         int temp=array[i] ;
    20.         array[i]=array[minat];  //swap
    21.         array[minat]=temp; 
    22.     }
    23. }
    24. void printElements(int *array,int length) //print array elements
    25. {
    26.     int i=0;
    27.     for(i=0;i<10;i++)
    28.        cout<<array[i]<<endl;
    29. }
    30.  
    31.  
    32. void main()
    33. {
    34.  
    35.     int a[]={9,6,5,23,2,6,2,7,1,8};   // array to sort
    36.         selectionSort(a,10);                 //call to selection sort  
    37.     printElements(a,10);               // print elements
    38. }

  5. #5
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    168

    Mặc định Heap Sort

    Heap Sort


    Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).
    Xem thêm chi tiết tại đây: uit.edu.vn/data/gtrinh/TH103/Htm/Bai04.htm

    C++ Code:
    1. #include < iostream.h >
    2. #include < conio.h >
    3. int heapSize = 10;
    4. void print(int a[])
    5. {
    6.   for (int i = 0; i <= 9; i++)
    7.  {
    8.     cout << a[i] << "-";
    9.   }
    10.   cout << endl;
    11. }
    12.  
    13. int parent(int i)
    14. {
    15. if(i==1)
    16. return 0;
    17.  
    18. if(i%2==0)
    19.     return ( (i / 2)-1);
    20. else
    21.     return ( (i / 2));
    22. }
    23.  
    24. int left(int i)
    25. {
    26.   return (2 * i) + 1;
    27. }
    28.  
    29. int right(int i)
    30. {
    31.   return (2 * i) + 2;
    32. }
    33.  
    34. void heapify(int a[], int i)
    35. {
    36.   int l = left(i), great;
    37.   int r = right(i);
    38.   if ( (a[l] > a[i]) && (l < heapSize))
    39.  {
    40.     great = l;
    41.   }
    42.   else {
    43.     great = i;
    44.   }
    45.   if ( (a[r] > a[great]) && (r < heapSize))
    46.  {
    47.     great = r;
    48.   }
    49.   if (great != i)
    50.  {
    51.     int temp = a[i];
    52.     a[i] = a[great];
    53.     a[great] = temp;
    54.     heapify(a, great);
    55.   }
    56. }
    57.  
    58. void BuildMaxHeap(int a[])
    59. {
    60.  for (int i = (heapSize - 1) / 2; i >= 0; i--)
    61.  {
    62.     heapify(a, i);
    63.     print(a);
    64.   }
    65. }
    66.  
    67. void HeapSort(int a[]) {
    68.   BuildMaxHeap(a);
    69.   for (int i = heapSize; i > 0; i--)
    70.  {
    71.     int temp = a[0];
    72.     a[0] = a[heapSize - 1];
    73.     a[heapSize - 1] = temp;
    74.     heapSize = heapSize - 1;
    75.     heapify(a, 0);
    76.   }
    77.  
    78. }
    79.  
    80. void main()
    81. {
    82.   int arr[] = {2, 9, 3, 6, 1, 4, 5, 7, 0, 8};
    83.   HeapSort(arr);
    84.   print(arr);
    85. }
    In code we trust

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    1

    Mặc định Các thuật toán sắp xếp trong lập trình C | Cấu trúc dữ liệu và giải thuật

    thanks mấy bro. còn mấy mảng nữa sao ko ai viết nữa vậy?

  7. #7
    Ngày gia nhập
    12 2012
    Bài viết
    1

    k có sắp xếp chuyển phần tử min về đầu dòng của C sao chủ thớt? mình k học C++

  8. #8
    Ngày gia nhập
    01 2015
    Bài viết
    19

    Trích dẫn Nguyên bản được gửi bởi iamvtn Xem bài viết
    Bubble sort (sắp xếp bằng cách đổi chỗ)

    I. Mô tả phương pháp:

    Phương pháp này sẽ duyệt danh sách nhiều lần, trong mỗi lần duyệt sẽ lần lượt so sánh cặp nút thứ i và thứ i+1 và đổi chỗ hai nút này nếu chúng không đúng thứ tự.
    Ví dụ cho một dãy số đơn giản và sắp xếp cho nó tăng dần.
    25 55 45 90 10
    Và đây sẽ minh họa quá trình so sánh và đổi chỗ trong lần duyệt đầu tiên.
    So sánh nút thứ i với nút thứ i+1 nếu nút thứ i > nút i+1 thì đổi chỗ 2 nút với nhau. Nếu không tiếp tục so sánh tiếp.
    1. So sánh 25 với 55:kiểm tra 25 < 55 -> Sai không đổi chỗ.
    2. So sánh tiếp 55 với phần tử tiếp theo là 45: 55 > 45 -> Đúng đổi chỗ 45 với 55
    3. So sánh tiếp 55 với 90: 55 < 90 -> sau không đổi chỗ.
    4. So sánh tiếp 90 với 10: 90 > 10 -> đúng đổi chỗ 90 cho 10.

    Danh sách sau khi biến đổi lần thứ nhất.
    25 45 55 10 90.
    Ta nhận thấy phần tử 90 lớn nhất được đưa về cuối danh sách, cứ tuần tự kiểm tra n lần như vậy ta sẽ được một danh sách tăng dần.

    OK chắc các bạn hiểu ý tưởng rồi chứ (dễ như ăn kẹo) .

    Tiếp giờ ta sẽ Mô Tả Giải Thuật Bubble Sort
    C++ Code:
    1. Dữ liệu nhập: Danh sách n nút chưa sắp xếp.
    2. Dữ liệu xuất: Danh sách n nút đã sắp xếp.
    3. Biến tạm: doicho
    4. Hành động:
    5. Gán doicho = true;
    6. for(int i = 1;i < n && doicho = true;i++)
    7.  {
    8.       Gán doicho = flase;
    9.       for(j = 0;i < n-1; j++)
    10.           if(nodes[j] > nodes[j+1]))
    11.           {
    12.                 Gán doicho = true;  
    13.                 Đỗi chỗ cho hai nút tại vị trí j và j+1
    14.           }
    15.  }
    16. Kết thúc

    Cài đặt giải thuật Bubble sort
    C++ Code:
    1. void BubbleSort(int nodes[],int n)  // n la so phan tu trong mang nodes[]
    2. {
    3.     int temp,i,j;
    4.    bool doicho = true;
    5.    for(i = 1; i < n && doicho == true; i++)
    6.    {
    7.     doicho = false;
    8.       for(j = 0;j < n-i; j++)
    9.             if(nodes[j] < nodes[j+1])
    10.         {
    11.             doicho = true;
    12.             temp = nodes[j];
    13.             nodes[j] = nodes[j+1];
    14.             nodes[j+1] = temp;
    15.         }
    16.    }
    17. }
    Nhận xét: Giải thuật bubble sort dễ hiểu nhưng không tối ưu vì thời gian thực hiện giải thuật chậm.

    cheer! (bắt trước anh ccom phát )
    (còn tiếp)
    Code minh họa không đúng với tư tưởng nhé.

  9. #9
    Ngày gia nhập
    01 2013
    Bài viết
    1,462

    ^ Đồng ý, nhưng mà để thêm cái điều kiện đấy sẽ nhanh hơn.

    Có điều câu này hơi bị...
    Giải thuật bubble sort dễ hiểu nhưng không tối ưu vì thời gian thực hiện giải thuật chậm.
    Nên so sánh với insertion

Các đề tài tương tự

  1. Thuật toán C Giải thích lỗi sai trong thuật toán cấu trúc cây
    Gửi bởi duythuanIT trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 1
    Bài viết cuối: 06-05-2013, 09:19 AM
  2. Bài tập C Cần giải giúp 3 câu trong đề thi kĩ thuật lập trình C và Cấu trúc dữ liệu và giải thuật
    Gửi bởi nguyenthi0602 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2012, 08:42 PM
  3. cây AVL trong cấu trúc dữ liệu và giải thuật
    Gửi bởi heaven_love9491 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 18-11-2010, 11:36 PM
  4. Thế nào là cấu trúc dữ liệu, thuật giải, thuật toán...??
    Gửi bởi duanvcd trong diễn đàn Kinh nghiệm CNTT
    Trả lời: 3
    Bài viết cuối: 17-06-2007, 10:07 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn