Trước khi chạy chương trình trong ví dụ sau, bạn tạo 1 file tên là n.txt là số các phần tử trong mảng và 1 file tên là day_so.txt lưu dãy số mà các bạn cần nhập vào. 2 file đó bạn lưu vào trong thư mục chứa project đang làm.
VD:
File n.txt có nội dung như sau:
------------------------------------------------------------------
10

------------------------------------------------------------------


File day_so.txt có nội dung như sau:
------------------------------------------------------------------
10
6
3
4
5
7
2
4
32
43
1
3
34
------------------------------------------------------------------

Code:


#include <iostream>
#include <fstream> // Thư viện nhập xuất file

using namespace std;
ifstream file1 ("n.txt"); // Hàm gọi file n.txt là file1
ifstream file2 ("day_so.txt"); // Hàm gọi file day_so.txt là file2
ofstream ket_qua ("Ket_qua.txt"); // Hàm gọi file kết quả ghi ra là ket_qua
int main ()
{

    int n;
    file1 >> n; // Đọc file trong n.txt
    int a[n];
    for (int i=0;i<n;i++)
        file2 >> a[i]; // Đọc file trong day_so.txt
    for (int i=0;i<n;i++)
    {
        ket_qua <<a[i] << "    "; //Ghi kết quả ra file Ket_qua.txt
        cout << a[i] <<endl;
    }
    return (0);
}

Thuật toán Shaker Sort

Thuật toán Shaker Sort là cải tiến của Bubble Sort nhưng được cải tiến từ sắp xếp 1 chiều thành 2 chiều.
Ý tưởng:
Giải thuật sẽ bắt đầu từ đầu hoặc cuối mảng,mỗi làn sắp xếp gồm 2 lượt: lượt đi và về. Ở lượt đi khi sắp xếp xong ta sẽ dùng biến k để đánh dấu trước vị trí đã được sắp xếp 

 

Code: 

#include <iostream>
using namespace std;
void sharer_sort(int a[], int n)
{
    int tg,ex;
     do
     {
        ex=0;
        for (int i=n-1; i>0;i--)
        {
         if (a[i-1]>a[i])
            {
            tg=a[i-1];
            a[i-1]=a[i];
            a[i]=tg;
            ex=1;
            }
        }
        for(int j=1; j<n;j++)
            {
            if (a[j-1]>a[j])
                {
                tg=a[j-1];
                a[j-1]=a[j];
                a[j]=tg;
                ex=1;
                }
            }
    }
    while(ex);
}
int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    sharer_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}

Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị. Nó được xếp vào thể loại sắp xếp so sánh.

Đọc thêm tại: Wikipedia


Code:

#include <iostream>
using namespace std;
void merge_sort(int a[], int n)
{
int i,j,k,low1,up1,low2,up2,size;
int dstam[100];size=1;
while(size<n)
    {
    low1=0;k=0;
    while(low1 +size <n)
        {
        low2=low1+size;
        up1=low2-1;
        if (low2+size-1< n)
            up2=low2+size-1;
        else
            up2=n-1;
        for(i=low1, j=low2; i<=up1 && j<=up2; k++)
            {
            if(a[i]<=a[j])
                dstam[k]=a[i++];
            else
                dstam[k] =a[j++];
            }
        for(;i<=up1;k++)
            dstam[k]=a[i++];
        for(;j<=up2;k++)
            dstam[k]=a[j++];
        low1=up2+1;
        }
    for (i=low1; k<n;i++)
        dstam[k++]=a[i];
    for(i=0;i<n;i++)
        a[i]=dstam[i];
    size*=2;
    }
}
int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    merge_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}

Sắp xếp vun đống (Heapsort) dựa trên một cấu trúc dữ liệu được gọi là đống nhị phân (binary heap), gọi đơn giản là đống. Trong mục này chỉ nói về đống trong bài toán sắp xếp.

Đọc thêm tại: Wikipedia


Code:

#include <iostream>
using namespace std;
void heap_sort(int a[], int n)
{
int k,x,s,f,ivalue;
for(k=1;k<n;k++)
    {
    x=a[k];
    s=k;
    f=(s-1)/2;
    while(s>0 && a[f]<x)
        {
        a[s]=a[f];
        s=f;
        f=(s-1)/2;
        }
    a[s]=x;
    }
for(k=n-1;k>0;k--)
    {
    ivalue=a[k];
    a[k]=a[0];
    f=0;
    if(k==1)
        s=-1;
    else
        s=1;
        if(k>2 && a[2]>a[1])
        s=2;
    while(s>=0 && ivalue<a[s])
        {
        a[f]=a[s];
        f=s;
        s=2*f +1;
        if (s+1<=k-1 && a[s]<a[s+1])
            s=s+1;
        if (s>k-1)
            s=-1;
        }
    a[f]=ivalue;
    }
}
int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    heap_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}

Sắp xếp nhanh (Quicksort), còn được gọi là sắp xếp kiểu phân chia (part sort) là một thuật toán sắp xếp phát triển bởi C.A.R. Hoare, dựa trên phép phân chia danh sách được sắp thành hai danh sách con. Khác với sắp xếp trộn, chia danh sách cần sắp xếp thành hai danh sách con có kích thước tương đối bằng nhau nhờ chỉ số đứng giữa danh sách, sắp xếp nhanh chia nó thành hai danh sách bằng cách so sánh từng phần tử của danh sách với một phần tử được chọn được gọi là phần tử chốt. Những phần tử nhỏ hơn hoặc bằng phần tử chốt được đưa về phía trước và nằm trong danh sách con thứ nhất, các phần tử lớn hơn chốt được đưa về phía sau và thuộc danh sách đứng sau. Cứ tiếp tục chia như vậy tới khi các danh sách con đều có độ dài bằng 1.

Thuật toán:
Sau khi phần tử chốt được chọn giải thuật phân chia nên tiến hành như thế nào?

• Một giải pháp đơn giản nhất cho vấn đề này là duyệt từ đầu đến cuối lần lượt so sánh các phần tử của danh sách với phần tử chốt. Theo cách này, ta phải tiến hành n phép so sánh, ngoài ra còn phải dành n đơn vị bộ nhớ để lưu giữ các giá trị trung gian.
• Một giải pháp khác được đề nghị là duyệt theo hai đường. Một đường từ đầu danh sách, một đường từ cuối danh sách. Theo cách này, ta tìm phần tử đầu tiên tính từ trái lớn hơn phần tử chốt và phần tử đầu tiên phía phải nhỏ hơn hoặc bằng phần tử chốt rồi đổi chỗ cho nhau. Tiếp tục như vậy cho đến khi hai đường gặp nhau.
• Để có thể gọi đệ quy ta xét bài toán phân chia một danh sách con của a: thành hai danh sách.

  Code:
#include <iostream>
using namespace std;
void qs(int a[], int left,int right)
{
int i,j, x,y;
i=left; j=right;
x= a[(left+right)/2];
do
    {
    while(a[i]<x && i<right) i++;
    while(a[j]>x && j>left) j--;
    if(i<=j)
        {
        y=a[i];a[i]=a[j];a[j]=y;
        i++;j--;
        }
    }
while (i<=j);
if (left<j) qs(a,left,j);
if (i<right) qs(a,i,right);
}
void quick_sort(int a[], int n)
{
qs(a,0,n-1);
}
int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    quick_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}
 

Sắp xếp nổi bọt (tiếng Anh: bubble sort) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap). Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang). Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.

Giải thuật:

Sắp xếp từ trên xuống
Giả sử dãy cần sắp xếp có n phần tử. Khi tiến hành từ trên xuống, ta so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử thứ hai và thứ ba và tiếp tục cho đến cuối tập hợp dữ liệu, nghĩa là so sánh (và đổi chỗ nếu cần) phần tử thứ n-1 với phần tử thứ n. Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy.
Sau đó, quay lại so sánh (và đổi chố nếu cần) hai phần tử đầu cho đến khi gặp phần tử thứ n-2....

Ghi chú: Nếu trong một lần duyệt, không phải đổi chỗ bất cứ cặp phần tử nào thì danh sách đã được sắp xếp xong.

Sắp xếp từ dưới lên
Sắp xếp từ dưới lên so sánh (và đổi chỗ nếu cần) bắt đầu từ việc so sánh cặp phần tử thứ n-1 và n. Tiếp theo là so sánh cặp phần tử thứ n-2 và n-1,... cho đến khi so sánh và đổi chỗ cặp phần tử thứ nhất và thứ hai. Sau bước này phần tử nhỏ nhất đã được nổi lên vị trí trên cùng (nó giống như hình ảnh của các "bọt" khí nhẹ hơn được nổi lên trên). Tiếp theo tiến hành với các phần tử từ thứ 2 đến thứ n.



Code:

#include <iostream>
using namespace std;
void bubble_sort(int a[], int n)
{
    int tg;
    for (int i=1; i<n; i++)
        {
        for (int j=n-1; j>=i; j--)
            {
            if (a[j-1]>a[j])
                {
                tg=a[j-1];
                a[j-1]=a[j];
                a[j]=tg;
                }
            }
        }
}
int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    bubble_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.

Thuật toán:
Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu . Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu đã được sắp. Để sắp xếp phần tử ta tìm vị trí thích hợp của nó trong dãy . Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

Các phần tử ≤x			Vị trí thích hợp	Các phần tử>x			Các phần tử chưa sắp
	...		x		...			...

Code:

#include <iostream>
using namespace std;
void insertion_sort(int a[], int n)
{
     int i,tg,x;
     for (i=1;i<n;i++)
      {
        tg=a[i];
        x=i-1;
        while((x>=0)&&(a[x]>tg))
            {
            a[x+1] = a[x];
            x--;
            }
        a[x+1] =tg;
     }
}
int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    insertion_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";
}