Thuật toán sắp xếp

1.Selection Sort
2.Insertion Sort
3.Quick Sort
4.Buble Sort
5.Heap Sort

//////Cac thuat toan sap xep///////

int nCmp=0;

//SelectionSort//Sap xep theo thu tu tang dan

void  SelectionSort(int A[],int n)//Mang A gom n phan tu

{

      for(int i=0;i<n-1;i++)

      {

            int m=i;

            for(int j=i+1;j<n;j++)

            {

                  if(A[j]<A[m])

                        m=j;

                  nCmp++;

            }

            if(m!=i) swap(A[i],A[m]);

      }

}

///InsertionSort///

void InsertionSort(int A[],int n)

{

      for(int i=1;i<n;i++)

      {

            int X=A[i];

            int j=i-1;///Phep so sanh dich dan sang trai

            while(j>=0&&A[j]>X)

            {

                  A[j+1]=A[j--];

                  nCmp++;

            }

            A[j+1]=X;//Correct

      }

}

///BubleSort////////

void BubbleSort(int A[],int n)

{

      for(int i=0;i<n-1;i++)

            for(int j=n-1;j>i;j--)

            {

                  if(A[j]<A[j-1])

                  {

                        swap(A[j],A[j-1]);nCmp++;

                  }

            }

}

////Thuat toan QuickSort/////////

///////Viet ham part

///////////Viet code cho ham Part////

int part(int A[],int lb,int ub)

{

      int X=A[lb];

      int i=lb+1;

      int j=ub;

      while(i<=j)

      {

            while(i<=j&&A[i]<X) i++;

            while(i<=j&&A[j]>X) j--;

            if(i<j) {

                  swap(A[i++],A[j--]);

                  nCmp++;}

      }

      swap(A[j],A[lb]);nCmp++;

      return j;

}

void QuickSort(int A[],int lb,int ub)

{

      if(lb<ub)

      {

            int j=part(A,lb,ub);

            QuickSort( A,lb,j-1);

            QuickSort( A,j+1,ub);

            nCmp++;

      }

}

////Thuat toan HeapSort/////

void BuildHeap(int A[],int n)//Su dung voi cac cay day du hoac hoan chinh

{

      for(int i=(n/2)-1;i>=0;i--)

      {

            int left=2*i+1;

            int right=2*i+2;

            int max;

            if(A[left]>A[i]) max=left;

            else max=i;

            if(A[right]>A[i]&&A[right]>A[left]) max=right;

            if(max!=i) swap(A[i],A[max]);

      }

}///Correctly

void HeapSort(int A[],int n)

{

            BuildHeap(A,n);

      while(n>=1)

      {

            swap(A[0],A[n]);

            n--;//Loai phan tu lon nhat ra khoi cay

            BuildHeap(A,n);

      }

}