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

[Fhuy]

void selectsort( int number[], int size){    int i, j, jmax;   int max;   for (i = 0; i < size - 1; i++)   {    max = number[0];      jmax = 0;      for (j = 1; j < size - i; j++)        if (number[j] > max)         {            max = number[j];            jmax = j;         }      if (jmax != size - i - 1)      {        max = number[size - i - 1];         number[size - i - 1] = number[jmax];         number[jmax] = max;      }   }}=============================================void bubblesort( int number[], int size){    int i=0, j, done=0;   int temp;   while(i<size&&done==0)   {    done=1;    for (j = 0; j < size-i; j++)      {        if (number[j] > number[j+1])         {            temp = number[j];            number[j] = number[j+1];            number[j+1] = temp;            done=0;         }      }      i++;   }}===============================void insertsort( int number[], int size){    int i,j;   int temp;   for(i=1;i<size;i++)   {    int left=0;      int right=i-1;      while(left<right)      {        int middle=(left+right)/2;         if(number[i]>number[middle])            left=middle+1;         else            right=middle;      }      if(number[i]<number[left])        j=left;      else        j=left+1;      temp=number[i];      for(int k=0;k<i-j-1;k++)        number[i-k]=number[i-k-1];      number[j]=temp;   }} =================================void quicksort( int number[], int low, int high){    int i=low, j=high;   int  temp;   int x=number[(low+high)/2];   do   {    while (number[i]<x) i++;      while (number[j]>x) j--;      if (i<=j)      {        temp=number[i];         number[i]=number[j];         number[j]=temp;         i++; j--;      }    } while (i<=j);     if (low<j) quicksort(number, low, j);    if (i<high) quicksort(number, i, high);}

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

[Alviss]

Đâ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

[fanshinichi]

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.

[Fhuy]

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?

[sieuphuong]

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 .

[rox_rook]

Đâ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 :

#include <iostream>#include <algorithm> class tracer{private :  static int n_assigned;  static int n_compared;  int        value;public :  static  int comparisions( )  {    return n_compared;  }  static  int assignments( )  {    return n_assigned;  }public :  tracer( int value = 0 ): value( value )  {    //do nothing  }  tracer( const tracer& rhs ) : value( rhs.value )  {    //do nothing  }   tracer& operator = ( const tracer& rhs )  {    ++n_assigned;    value = rhs.value;    return *this;  }   ~tracer( )  {    std::cout << "\n\n Destroying data...\n\n";  }   friend  bool operator < ( const tracer& lhs, const tracer& rhs )  {    n_compared++;    return lhs.value < rhs.value;  }   int get_val( ) const  {    return value;  }}; int tracer::n_assigned  = 0;int tracer::n_compared  = 0; int main( ){  int index;  tracer arry_data[ 10 ] = { 6, 7, 8, 2, 3, 4, 1, 19, 27, 20 };   std::cout << "\n- [ Before Sort ]\n";  for( index = 0; index < 10; ++index )  {    std::cout << arry_data[ index ].get_val( ) << " ";  }   int assignments_start  = tracer::assignments( );  int comparisions_start = tracer::comparisions( );   std::sort< >( arry_data, arry_data + 9 );   std::cout << "\n- [ After Sort ]\n";  for( index = 0; index < 10; ++index )  {    std::cerr << arry_data[ index ].get_val( ) << " ";  }   std::cout << "\n -> [ Statictics ] \n";  std::cout << " + comparision = "            << tracer::comparisions( ) - comparisions_start            << "\n";  std::cout << " + assignments = "            << tracer::assignments( ) - assignments_start            << "\n";   return 0;}