Các thuật toán sắp xếp

Thuật toán Merge sort: Độ phức tạp T(n)=O(nlog₂n)

void Merge_sort(int a[], int left, int mid, int right){
 int i = left, j = mid + 1, k = 0, n = right - left + 1;
 int *B = new int[n];
 while ((i < mid + 1) && (j < right + 1)){
  if (a[i] < a[j]){
   B[k] = a[i];

   k++; i++;
  }
  else {
   B[k] = a[j];
   k++;
   j++;
  }
 }
 while (i < mid + 1){
  B[k] = a[i];
  i++; k++;
 }
 while (j < right + 1){
  B[k] = a[j];
  k++; j++;
 }
 i = left;
 for (int k = 0; k < n; k++){
  a[i] = B[k];
  i++;
 }
 delete[] B;

}
void Merge(int a[], int left, int right){
 if (left < right){
  int mid = (left + right) / 2;
  Merge(a, left, mid);
  Merge(a, mid + 1, right);
  Merge_sort(a, left, mid, right);
 }
}

Insertion Sort: Độ phức tạp T(n)=O(n² )

void Insertion_sort(int a[], int n){
int x;
for (int i = 1; i < n; i++){
x = a[i];
int pos = i - 1;
while (pos >= 0 && (a[pos]>x)){
a[pos + 1] = a[pos];
pos--;
}
a[pos + 1] = x;
}
}

Interchange Sort: Độ phức tạp: T(n)=O(n²)

for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;i++){
if(a[i]>a[j])
HoanVi(a[i],a[j]);
}
}

Quick Sort: Độ phức tạp

Đối với partition: T(n)=O(n)

Đối với quicksort

Tốt nhất: T(n)=O(nlog₂n)

Xấu nhất T(n)=O(n²)

Trung bình:  T(n)=O(nlog₂n)

int Partitition(int A[],int left,int right){
int X=a[left],t;
int i=left+1;
int j=right;
do{
while((i<=j)&&A[i]<=X)
i++;
while((i<=j)&&A[i]>X)
j--;
if(i<j){
t=A[i];
A[i]=A[j];
A[j]=t;
i++; j--;
}
}while(i<=j);
t=A[left];
A[left]=A[j];
A[j]=t;
return j;
}

void Quicksort(int A[],int left,int right){
int k;
if(left<right){
k=Partition(A,left,right);
Quicksort(A,left,k-1);
Quicksort(A,k+1,right);
}
}

Buble sort:

Độ phức tạp: T(n)=O(n²)

for(int i=0;i<n;i++){
for(int j=n-1;j>i;j--){
if(a[j]<a[j-1])
HoanVi(a[j],a[j-1]);
}
}

Heap sort

T(n)=O(nlog₂n)

void max_heapify(int heap[], int heapsize, int i)
{
 int left_child, right_child, largest;
 left_child = 2*i;
 right_child = 2*i + 1;
 if(left_child <= heapsize && heap[left_child] > heap[i]) 
  largest = left_child;
 else 
  largest = i;
  if(right_child <= heapsize && heap[right_child] > heap[largest]) 
  largest = right_child;
  if(largest != i)
 {
  swap(heap[i], heap[largest]);
  max_heapify(heap, heapsize, largest);
 }
}

void buildheap(int heap[], int heapsize, int a[], int n)
{
 heapsize = n;
 for(int i = 1; i <= n; i++)
  heap[i] = a[i];
 for(int i = n/2; i >= 1; i--)
        max_heapify(heap, heapsize, i);
}

void heapsort(int heap[], int heapsize, int a[], int n)
{
 buildheap(heap, heapsize, a, n);
 for(int i = n; i >= 2; i--)
 {
  swap(heap[1], heap[i]);
  max_heapify(heap, i - 1, 1);
 }
 for(int i = 1; i <= n; i++)
  a[i] = heap[i];
}

void input_array(int a[], int &n)
{
 cin>>n;
 for(int i = 1; i <= n; i++)
  cin>>a[i];
} 

void print_array(int a[], int n)
{
 for(int i = 1; i <= n; i++)
  cout<<a[i]<<" ";
 cout<<endl;
}