Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Độ phức tạp của thuật toán xắp xếp trong lập trình C

  1. #1
    Ngày gia nhập
    03 2008
    Bài viết
    2

    Mặc định Độ phức tạp của thuật toán xắp xếp trong lập trình C

    C Code:
    1. void selectsort( int number[], int size)
    2. {
    3.     int i, j, jmax;
    4.    int max;
    5.    for (i = 0; i < size - 1; i++)
    6.    {
    7.     max = number[0];
    8.       jmax = 0;
    9.       for (j = 1; j < size - i; j++)
    10.         if (number[j] > max)
    11.          {
    12.             max = number[j];
    13.             jmax = j;
    14.          }
    15.       if (jmax != size - i - 1)
    16.       {
    17.         max = number[size - i - 1];
    18.          number[size - i - 1] = number[jmax];
    19.          number[jmax] = max;
    20.       }
    21.    }
    22. }
    23. =============================================
    24. void bubblesort( int number[], int size)
    25. {
    26.     int i=0, j, done=0;
    27.    int temp;
    28.    while(i<size&&done==0)
    29.    {
    30.     done=1;
    31.     for (j = 0; j < size-i; j++)
    32.       {
    33.         if (number[j] > number[j+1])
    34.          {
    35.             temp = number[j];
    36.             number[j] = number[j+1];
    37.             number[j+1] = temp;
    38.             done=0;
    39.          }
    40.       }
    41.       i++;
    42.    }
    43. }
    44. ===============================
    45. void insertsort( int number[], int size)
    46. {
    47.     int i,j;
    48.    int temp;
    49.    for(i=1;i<size;i++)
    50.    {
    51.     int left=0;
    52.       int right=i-1;
    53.       while(left<right)
    54.       {
    55.         int middle=(left+right)/2;
    56.          if(number[i]>number[middle])
    57.             left=middle+1;
    58.          else
    59.             right=middle;
    60.       }
    61.       if(number[i]<number[left])
    62.         j=left;
    63.       else
    64.         j=left+1;
    65.       temp=number[i];
    66.       for(int k=0;k<i-j-1;k++)
    67.         number[i-k]=number[i-k-1];
    68.       number[j]=temp;
    69.    }
    70. }
    71.  
    72. =================================
    73. void quicksort( int number[], int low, int high)
    74. {
    75.     int i=low, j=high;
    76.    int  temp;
    77.    int x=number[(low+high)/2];
    78.    do
    79.    {
    80.     while (number[i]<x) i++;
    81.       while (number[j]>x) j--;
    82.       if (i<=j)
    83.       {
    84.         temp=number[i];
    85.          number[i]=number[j];
    86.          number[j]=temp;
    87.          i++; j--;
    88.       }
    89.     } while (i<=j);
    90.  
    91.     if (low<j) quicksort(number, low, j);
    92.     if (i<high) quicksort(number, i, high);
    93. }
    Bạn xem giúp minh xem từng thuật toán trên được dùng trong trường hợp nào,và độ phức tạp của nó! thank nha

    Lưu ý: Đưa code vào tag code. Đọc Nội quy để biết thêm chi tiết
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Đã được chỉnh sửa lần cuối bởi Kevin Hoang : 20-04-2008 lúc 11:03 PM. Lý do: Nhắc nhở

  2. #2
    Ngày gia nhập
    06 2007
    Nơi ở
    một nơi xa xăm...
    Bài viết
    127

    Đây là các giải thuật xắp xếp cơ bản.Độ phức tạp là O(n^2).Chý ý cho CODE vào tag nha bạn

  3. #3
    Ngày gia nhập
    05 2007
    Bài viết
    16

    QuickSort có thời gian chạy trung bình là NlgN,hieu quả nhất trong các thuật toán sắp xếp trên. Nếu khi sắp xếp trên danh sách đã có thứ tự thì thời gian chạy là O(n^2).
    InsertionSort và BubbleSort độc lập với input,thời gian chạy O(n^2).
    Kiến thức đệ chỉ có nhiêu đó. Mong mấy huynh chỉ giáo.
    C++,C#,Java muôn năm

  4. #4
    Ngày gia nhập
    03 2008
    Bài viết
    2

    Bạn ơi! các hàm trên được dùng trong các bài toán dạng nào thì ưu việt! và giải thích thời gian tình của từng hàm nhanh chậm thế nào?

  5. #5
    Ngày gia nhập
    12 2007
    Bài viết
    224

    Cũng tuỳ vào giải thuật nào tốt nhất với mảng cần sắp xếp nào .

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Độ phức tạp của thuật toán xắp xếp trong lập trình C

    Đây dùng C++ copy cái này vào, muốn dùng sort gì thì viết vào, rùi dựa vào assignments và comparisions mà so sánh độ phức tạp. Ở đây tui dùng quicksort của STL C++, cậu muốn viết bubble sort, insertion sort, hay merge sort thì tùy ý, cứ tạo đối tượng rùi trace y chang, cách này dùng để keep track các thuật toán sort rất hay :
    C++ Code:
    1. #include <iostream>
    2. #include <algorithm>
    3.  
    4. class tracer
    5. {
    6. private :
    7.   static int n_assigned;
    8.   static int n_compared;
    9.   int        value;
    10. public :
    11.   static
    12.   int comparisions( )
    13.   {
    14.     return n_compared;
    15.   }
    16.   static
    17.   int assignments( )
    18.   {
    19.     return n_assigned;
    20.   }
    21. public :
    22.   tracer( int value = 0 ): value( value )
    23.   {
    24.     //do nothing
    25.   }
    26.   tracer( const tracer& rhs ) : value( rhs.value )
    27.   {
    28.     //do nothing
    29.   }
    30.  
    31.   tracer& operator = ( const tracer& rhs )
    32.   {
    33.     ++n_assigned;
    34.     value = rhs.value;
    35.     return *this;
    36.   }
    37.  
    38.   ~tracer( )
    39.   {
    40.     std::cout << "\n\n Destroying data...\n\n";
    41.   }
    42.  
    43.   friend
    44.   bool operator < ( const tracer& lhs, const tracer& rhs )
    45.   {
    46.     n_compared++;
    47.     return lhs.value < rhs.value;
    48.   }
    49.  
    50.   int get_val( ) const
    51.   {
    52.     return value;
    53.   }
    54. };
    55.  
    56. int tracer::n_assigned  = 0;
    57. int tracer::n_compared  = 0;
    58.  
    59. int main( )
    60. {
    61.   int index;
    62.   tracer arry_data[ 10 ] = { 6, 7, 8, 2, 3, 4, 1, 19, 27, 20 };
    63.  
    64.   std::cout << "\n- [ Before Sort ]\n";
    65.   for( index = 0; index < 10; ++index )
    66.   {
    67.     std::cout << arry_data[ index ].get_val( ) << " ";
    68.   }
    69.  
    70.   int assignments_start  = tracer::assignments( );
    71.   int comparisions_start = tracer::comparisions( );
    72.  
    73.   std::sort< >( arry_data, arry_data + 9 );
    74.  
    75.   std::cout << "\n- [ After Sort ]\n";
    76.   for( index = 0; index < 10; ++index )
    77.   {
    78.     std::cerr << arry_data[ index ].get_val( ) << " ";
    79.   }
    80.  
    81.   std::cout << "\n -> [ Statictics ] \n";
    82.   std::cout << " + comparision = "
    83.             << tracer::comparisions( ) - comparisions_start
    84.             << "\n";
    85.   std::cout << " + assignments = "
    86.             << tracer::assignments( ) - assignments_start
    87.             << "\n";
    88.  
    89.   return 0;
    90. }
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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

  1. 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
    Gửi bởi iamvtn trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 8
    Bài viết cuối: 11-02-2017, 04:44 PM
  2. Lập trình C++ Thắc mắc về thuật toán trong giao thức thoả thuận khoá Station to station?
    Gửi bởi luongthienaz trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 05-12-2012, 09:56 AM
  3. Kỹ thuật in - Vai trò của kỹ thuật in trong thiết kế, in ấn
    Gửi bởi thongthanhhungland trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 18-11-2011, 01:04 PM
  4. Thuật toán trong C | Cẩm nang thuật toán | "Algorithims In C" của Robert Sedgewick
    Gửi bởi clementboy03 trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 3
    Bài viết cuối: 20-05-2009, 07:50 PM
  5. Trả lời: 6
    Bài viết cuối: 04-05-2008, 08:04 AM

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