NHẬP TỪ KHÓA BẠN QUAN TÂM VÀO KHUNG BÊN DƯỚI
LIKE ỦNG HỘ GOCCAY.VN NHA CÁC BẠN ^_^
TRUYỆN XEM NHIỀU NHẤT
Đấu Phá Thương Khung
Đấu La Đại Lục
Cực Phẩm Gia Đinh
Tân Tác Long Hổ Môn
Phong Thần Ký III
Tuyệt Thế Vô Song
Thời Đại X Long
Thiên Địa Long Hồn
Chu Tước Ký
Bàn Long
Thôn Phệ Tinh Không
Chín Chín Tám Mốt
Mãng Hoang Ký
Hắc Khuyển
+ Trả Lời Ðề Tài
Trang 1/2 1 2 cuốicuối
kết quả từ 1 tới 10 trên 12

Ðề tài: Các thuật toán sắp xếp

  1. #1
    Tham gia ngày
    Oct 2011
    Bài gởi
    69
    Thanks
    9
    Thanked 41 Times in 23 Posts

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

    Tổng quan về thuật toán sắp xếp

    Một trong những vấn đề nền tảng của khoa học máy tính là sắp xếp một tập các phần tử cho trước theo thứ tự nào đó. Có rất nhiều các giải pháp cho vấn đề này, được biết đến như là các thuật toán sắp xếp (sorting algorithms). Bên cạnh các thuật toán sắp xếp đơn giản và rất rỏ ràng, như là sắp xếp nổi bọt (bubble sort). Một số khác, như phương pháp sắp xếp nhanh (quick sort) thì lại rất phức tạp nhưng đổi lại có kết quả thực thi nhanh hơn một cách đáng kể.

    Dưới đây là liên kết tới các mô tả, phân tích, và mã nguồn cho 7 thuật toán sắp xếp quan trọng, phổ biến nhất hiện nay.

    Bubble sort
    Heap sort
    Insertion sort
    Merge sort
    Quick sort
    Selection sort
    Shell sort

    Những thuật toán sắp xếp quen thuộc này có thể được chia thành hai nhóm dựa theo độ phức tạp của chúng. Độ phức tạp của thuật toán (Algorithmic complexity) là một chủ đề khá rắc rối đòi hỏi sự tưởng tượng mà sẽ tốn nhiều thời gian để giải thích, nhưng ở đây có thể hiểu thông qua mối tương quan trực tiếp giữa độ phức tạp của thuật toán và hiệu quả của nó. Độ phức tạp của thuật toán thường được kí hiệu bởi một hàm O, trong đó O biểu diễn độ phức tạp của thuật toán đi kèm với một giá trị n biểu diễn kích thước của số lần chạy tối đa mà thuật toán đó dựa vào để xử lý trên dữ liệu.

    Ví dụ, O(n) có nghĩa là thuật toán có độ phức tạp tuyến tính. Cụ thể hơn , nó sẽ mất thời gian gấp 10 lần cho việc xử lý trên tập dữ liệu có 100 phần tử so với tập chỉ có 10 phần tử (10 * 10 = 100). Nếu độ phức tạp là O(n2) (quadratic complexity), thì nó sẽ phải tiêu tốn thời gian gấp 100 lần để xử lý trên tập 100 phần tử so với tập dữ liệu chỉ gồm 10 phần tử.

    Hai nhóm thuật toán sắp xếp được phân như sau: nhóm thứ nhất có độ phức tạp là O(n2) bao gồm bubble, insertion, selection, và shell sorts; Nhóm thứ hai có độ phức tạp là O(n log n) gồm heap, merge, và quick sorts.

    Bên cạnh độ phức tạp của thuật toán, tốc độ của các thuật toán sắp xếp có thể được so sánh dựa vào kinh nghiệm có được từ việc thử trên các tập dữ liệu. Vì tốc độ sắp xếp có thể thay đổi rất nhiều tùy theo đặc điểm của dữ liệu, nên để các kết quả thống kê chính xác dựa trên kinh nghiệm đòi hỏi việc chạy các thuật toán nhiều lần trên các dữ liệu khác nhau và tính trung bình. Thông thường tập dữ liệu kiểm tra được tạo ngẫu nhiên.

    Trong các biểu đồ thể hiện mức độ hiệu quả của thuật toán dưới đây, đường thấp nhất là "tốt nhất". Ghi nhớ rằng "tốt nhất" ở đây là một khái niệm không tuyệt đối vì nó còn tùy vào trường hợp sử dụng của bạn - nếu nhìn biểu đồ bạn sẽ thấy quick sort có lẽ là thuật toán nhanh nhất, nhưng nếu sử dụng nó để sắp xếp một tập 20 phần tử thì cũng giống như đem dao mổ trâu đi cắt hành.


    Đồ thị trên đã thể hiện khá rỏ, Bubble sort là giải pháp cực kì không hiệu quả, và shell sort là sự cải tiến tạo ra cuộc bứt phá hết sức ngoạn mục. Chú ý rằng vào đường ngang đầu tiên của khu vực đồ thị thể hiện thời gian 100 giây- bạn sẽ thấy rằng không có thuật toán nào trong số này mà bạn muốn sử dụng cho tập dữ liệu lớn của một ứng dụng tương tác. Ngay cả khi dùng shell sort, người sử dụng cũng có nguy cơ ngồi bấm móng tay nếu bạn cố gắng sắp xếp nhiều hơn 10,000 phần tử.

    Nhìn từ phương diện tươi sáng hơn, tất cả những thuật toán thuộc nhóm O(n2) đều đơn giản một cách không ngờ (có thể shell sort là một ngoại lệ hơi phức tạp hơn). Với những chương trình dùng kiểm tra nhanh, những mẩu thử nghiệm gấp, hay các phần mềm dành cho người sử dụng nội bộ, chúng không phải là những lựa chọn tồi nếu bạn không đặt quá nặng về hiệu năng.


    Trong trường hợp tốc độ là ưu tiên hàng đầu, những giải thuật thuộc nhóm O(n log n) nên được sử dụng. Chú ý rằng thời gian trong đồ thị ngay trên đây được đo theo từng phần 10 của giây thay vì từng trăm giây như đồ thị của nhóm O(n2).

    Tuy nhiên mọi thứ thì không thật sự dễ dàng với các ứng dụng thực tiễn, bạn phải đứng trước sự lựa chọn cân bằng (trade-offs) giữa các yếu tố. Những thuật toán thuộc nhóm O(n log n) thì rất nhanh, nhưng tốc độ đó có được do phải trả giá cho sự phức tạp trong triển khai. Trong trường hợp đệ quy, các cấu trúc dữ liệu nâng cao, mảng đa chiều - việc sử dụng những thuật toán này sẽ tạo ra nhiều vấn đề phát sinh rất khó chịu.

    View more latest threads same category:

    thay đổi nội dung bởi: tonghai_it; 10-27-2011 lúc 08:37 AM

  2. The Following 5 Users Say Thank You to tonghai_it For This Useful Post:

    admin (11-23-2011), cachua (03-05-2012), camyvevn (11-11-2011), phongvan (02-09-2012), quangvinh (02-04-2012)

  3. Circuit advertisement
    Tham gia ngày
    Always
    Bài gởi
    Many
  4. #2
    Tham gia ngày
    Oct 2011
    Bài gởi
    602
    Thanks
    439
    Thanked 984 Times in 275 Posts

    Thuật toán sắp xếp Đổi chỗ (Interchange Sort)

    Giải thuật
    ý tưởng chính của thuật toán Interchane Sort hay còn gọi là thuật toán sắp xếp đổi chổ trực tiếp là xuất phát từ đầu danh sách, xét tất cả các cặp phần tử trong dãy, nếu phần tử sau nhỏ hơn phần tử trước (hoặc lớn hơn phần tử trước nếu sắp giảm) thì tiến hành hoán vị 2 phần tử này.

    Cài đặt
    Code:
    void InterchangeSort(int a[], int N)
    {
        for (int i = 0; i < N - 1; i++)
            for (int j = i + 1; j < N; j++)
                if (a[j] < a[i]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
    }

  5. The Following 2 Users Say Thank You to quangvinh For This Useful Post:

    cachua (03-05-2012), phongvan (02-09-2012)

  6. #3
    Tham gia ngày
    Oct 2011
    Bài gởi
    69
    Thanks
    9
    Thanked 41 Times in 23 Posts

    Thuật toán Heap sort

    Heap sort là thuật toán chậm nhất trong số các thuật toán sắp xếp thuộc nhóm có độ phức tạp O(n log n), nhưng không giống như Merge và Quick sort nó không đòi hỏi sự đệ quy phức tạp hay nhiều mảng dữ liệu để xử lý. Điều này làm cho nó trở thành một lựa chọn hấp dẫn với tập dữ liệu rất lớn hàng triệu phần tử. Tuy nhiên sự lựa chọn thích hợp lúc nào cũng còn tùy thuộc vào kết cấu hạ tầng và mục tiêu của ứng dụng.

    Heap sort hoạt động cũng như sự gợi ý trong tên gọi - nó bắt đầu bằng việc xây dựng một heap out của tập dữ liệu, và sau đó loại phần tử lớn nhất và đặt nó vào vị trí cuối của mảng được sắp xếp. Sau việc xóa phần tử lớn nhất, nó tái cấu trúc heap và di chuyển phần tử lớn nhất kế tiếp còn lại và đặt nó vào vị trí mở kế cuối của mảng được sắp xếp. Thao tác này được lặp lại cho tới khi không còn phần tử bên trái trong heap và mảng được sắp xếp đã đầy. Cách triển khai căn bản đòi hỏi hai mảng dữ liệu - một giữ heap và một giữ những phần tử đã được sắp xếp.

    Việc thực hiện tiến trình sắp xếp chỉ trong một mảng duy nhất nhằm tiết kiệm không gian của mảng thứ hai là cần thiết, giải thuật sau đây dùng một ít kỉ xảo để chỉ sử dụng cùng một mảng cho lưu trử Heap và mảng đã được sắp xếp. Bất cứ khi nào một phần tử được xóa khỏi Heap, nó giải phóng một không gian lưu trử ở cuối mảng mà phần tử bị xóa có thể được đặt vào.

    Cài đặt
    Code:
    //doi cho
    void Swap(int &a,int &b)
    {
    	int t;
    	t=a;
    	a=b;
    	b=t;
    }
    //thu tuc hieu chinh heap
    void Shift(int a[],int r,int l)
    {
    	int i,j,x;
    	i=l;
    	j=2*i; //phan tu lien doi
    	x=a[i];
    	while(j<=r)
    	{
    		if(j<r)
    		if(a[j]<a[j+1]) //xac dinh phan tu lien doi lon hon
    		j++;
    		if(a[j]<=x)
    			break; //thoa quan he lien doi,dung
    		else
    		{
    			a[i]=a[j];
    			i=j;
    			j=2*i;
    			a[i]=x;
    		}
    	}
    }
    //hieu chinh day ban dau thanh heap
    void CreateHeap(int a[],int n)
    {
    	int l;
    	l=(n-1)/2;
    	while(l>=0)
    	{
    		Shift(a,n-1,l);
    		l--;
    	}
    }
    
    //phuong phap cay
    void HeapSort(int a[],int n)
    {
    	int r;
    	CreateHeap(a,n);
    	r=n-1; //vi tri phan tu cuoi mang
    	while(r>0)
    	{
    		Swap(a[0],a[r]);
    		r--;
    		Shift(a,r,0);
    	}
    }
    Video minh họa thuật toán

  7. The Following 4 Users Say Thank You to tonghai_it For This Useful Post:

    cachua (03-05-2012), phongvan (02-11-2012), quangvinh (02-04-2012), trùmspam (02-09-2012)

  8. #4
    Tham gia ngày
    Oct 2011
    Bài gởi
    602
    Thanks
    439
    Thanked 984 Times in 275 Posts

    Thuật toán sắp xếp nổi bọt (Bubble sort)

    Thuật toán sắp xếp nổi bọt là một trong các thuật toán phổ biến nhất với những lập trình viên mới bắt đầu sự nghiệp. Thuật toán này vận hành dựa trên việc so sánh liên tục các phần tử cạnh nhau của một mảng các số chưa được sắp xếp và cho phép phần tử nào nhẹ hơn sẽ được nổi lên trên (chuyển vị trí sang trái hoặc phải tùy theo việc muốn sắp xếp theo thứ tự tăng dần hay giảm dần). Bubble sort là thuật toán dễ triển khai nhưng cũng là một trong các thuật toán sắp xếp có hiệu suất kém nhất (độ phức tạp lên tới O(n2)). Để có thể xem minh họa về thuật toán này, bạn có thể truy cập trang Algolist (trang web chuyên minh họa về các thuật toán). Tuy vậy, có một cách hay hơn và dễ hiểu hơn để biết về thuật toán nổi tiếng (về sự đơn giản và chậm chạp) này là xem video dưới đây do các thành viên thuộc trường đại học Sapientia (Romania) trình diễn :

    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.

    Mô tả:


    Cài đặt
    Code:
    void doicho(int &a,int &b)
    {
    	int t;
    	t=a;
    	a=b;
    	b=t;
    } 
    void noibot(int a[],int n)
    {
    	for(int i = 0; i < n-1; i++)
    		for(int j = n-1; j > i; j--)
    			if (a[j-1] > a[j])
    	doicho(a[j], a[j-1]);
    }
    Độ phức tạp
    - Về thời gian: O(n2)
    - Về dữ liệu: Không tốn thêm vùng nhớ

    Video minh họa thuật toán


  9. The Following 2 Users Say Thank You to quangvinh For This Useful Post:

    camyvevn (11-11-2011), trùmspam (02-09-2012)

  10. #5
    Tham gia ngày
    Oct 2011
    Bài gởi
    602
    Thanks
    439
    Thanked 984 Times in 275 Posts

    Thuật toán sắp xếp Nhanh (Quick-sort)

    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 a[1..n] 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.

    Phần tử chốt (pivot)

    Kỹ thuật chọn phần tử chốt ảnh hưởng khá nhiều đến khả năng rơi vào các vòng lặp vô hạn đối với các trường hợp đặc biệt. Tốt nhất là chọn phần tử chốt là trung vị của danh sách. Khi đó sau log2(n) lần phân chia ta sẽ đạt tới kích thước danh sách bằng 1. Tuy nhiên điều đó rất khó. Có các cách chọn phần tử chốt như sau:

    - Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.
    - Chọn phần tử đứng giữa danh sách làm phần tử chốt.
    - Chọn phần tử trung vị trong 3 phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt.
    - Chọn phần tử ngẫu nhiên làm phần tử chốt. (Cách này có thể dẫn đến khả năng rơi vào các trường hợp đặc biệt)

    Thuật giải

    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: a[k1,k2] thành hai danh sách.

    Cài đặt

    Code:
    void doicho(int &a,int &b)
    {
    	int t;
    	t=a;
    	a=b;
    	b=t;
    } 
    
    void sapxepnhanh(int a[],int l,int r)
    {
    	int i,j,x;
    	x=a[(l+r)/2]; //chon phan tu trung vi lam moc
    	i=l;
    	j=r;
    	do
    	{
    		while(a[i]<x) //cac vi tri cua day <x
    		i++;
    		while(a[j]>x) //cac vi tri cua day >x
    		j--;
    		if(i<=j)
    		{
    			doicho(a[i],a[j]);
    			i++;
    			j--;
    		}
    	} while(i<=j);
    	if(l<j)
    		Quick(a,l,j);
    	if(i<r)
    		Quick(a,i,r);
    	}
    
    void sapxep(int a[],int n)
    {
    	sapxepnhanh(a,0,n-1);
    }
    Độ phức tạp
    -Về thời gian: O(nlog n)
    - Về dữ liệu: Khác nhau tùy vào cách hiện thực

    Video minh họa thuật toán


  11. The Following 2 Users Say Thank You to quangvinh For This Useful Post:

    admin (11-23-2011), trùmspam (02-09-2012)

  12. #6
    Tham gia ngày
    Oct 2011
    Bài gởi
    602
    Thanks
    439
    Thanked 984 Times in 275 Posts

    Lightbulb Thuật toán sắp xếp trộn (Merge-sort)

    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.

    Giải thuật

    Các bước thực hiện thuật toán trộn tự nhiên như sau:

    Code:
        Bước 1 : // Chuẩn bị
            r = 0; // r dùng để đếm số đường chạy
    
        Bước 2 :
            Tách dãy a1, a2, ..., an thành 2 dãy b, c theo nguyên tắc luân phiên từng đường chạy:
    
            Bước 2.1 :
                Phân phối cho b một đường chạy; r = r+1;
                Nếu a còn phần tử chưa phân phối
                Phân phối cho c một đường chạy; r = r+1;
    
            Bước 2.2 :
                Nếu a còn phần tử: quay lại bước 2.1;
    
        Bước 3 :
            Trộn từng cặp đường chạy của 2 dãy b, c vào a.
    
        Bước 4 :
            Nếu r <= 2 thì trở lại bước 2;
            Ngược lại: Dừng;


    Ưu và nhược điểm

    Thuật toán trộn tự nhiên khác thuật toán trộn trực tiếp ở chỗ thay vì luôn cứng nhắc phân hoạch theo dãy con có chiều dài k, việc phân hoạch sẽ theo đơn vị là đường chạy. ta chỉ cần biết số đường chạy của a sau lần phân hoạch cuối cùng là có thể biết thời điểm dừng của thuật toán vì dãy đã có thứ tự là dãy chi có một đường chạy.

    Một nhược điểm lớn nữa của thuật toán trộn là khi cài đặt thuật toán đòi hỏi thêm không gian bộ nhớ để lưu các dãy phụ b, c. Hạn chế này khó chấp nhận trong thực tế vì các dãy cần sắp xếp thường có kích thước lớn. Vì vậy thuật toán trộn thường được dùng để sắp xếp các cấu trúc dữ liệu khác phù hợp hơn như danh sách liên kết hoặc file.

    Cài đặt
    Code:
    void sapxep(int a[],int k1,int k2,int k3)
    {   int i,j,k,T[k3-k1+1];
        i=k1;
        j=k2;
        k=k1;
      while (i<k2&&j<=k3)
       {
         if (a[i]<=a[j])
         {
             T[k]=a[i];
             i=i+1;
         }
           else 
           {
             T[k]=a[j];
             j=j+1;
           }
        k=k+1;
       }
       if (i>=k2)
            while (k<=k3) 
            {
               T[k]=a[j];
               j=j+1;
               k=k+1;
           }
       if (j>k3)
            while (k<k2)
             {
               T[k]=a[i];
               i=i+1;
               k=k+1;
             }
        for (k=k1;k<=k3;k++)
              a[k]=T[k];
    
    }
    void sapxeptron(int a[],int k1,int k2)
    {
         t++;
       int k3;
       if(k1<k2)
       {
           k3=int((k1+k2)/2);
           sapxeptron(a,k1,k3);
           sapxeptron(a,k3+1,k2);
           sapxep(a,k1,k3+1,k2);
       }
    
    }
    Độ phức tạp
    - Về thời gian: O(nlog n)
    - Về dữ liệu: Cần vùng nhớ trung gian khác nhau tùy loại

    Video minh họa thuật toán



    thay đổi nội dung bởi: quangvinh; 11-10-2011 lúc 10:10 PM

  13. The Following 2 Users Say Thank You to quangvinh For This Useful Post:

    camyvevn (11-11-2011), trùmspam (02-09-2012)

  14. #7
    Tham gia ngày
    Oct 2011
    Bài gởi
    602
    Thanks
    439
    Thanked 984 Times in 275 Posts

    Thuật toán sắp xếp Chọn (Selection sort)

    Giải thuật

    Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

    Các bước tiến hành như sau:

    Bước 1: i=1

    Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]

    Bước 3: Hoán vị a[min] và a[i]

    Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2

    Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.

    Ví dụ: Cho dãy a = (12,2,8,5,1,6,4,15)

    12 2 8 5 1 6 4 15

    Bước 1: 1 2 8 5 12 6 4 15

    Bước 2: 1 2 8 5 12 6 4 15

    Bước 3: 1 2 4 5 12 6 8 15

    Bước 4: 1 2 4 5 12 6 8 15

    Bước 5: 1 2 4 5 6 12 8 15

    Bước 6: 1 2 4 5 6 8 12 15

    Bước 7: 1 2 4 5 6 8 12 15

    Cài đặt

    Code:
    void doicho(int &a,int &b)
    {
    	int t;
    	t=a;
    	a=b;
    	b=t;
    } 
    void sapxepchon(int a[], int n)
    {
    	int min;
    	for(int i=0;i<n-1;i++)
    	{
    		min = i;
    		for (int j = i+1; j < n; j++)
    			if (a[j] < a[min]) 
    				min = j;
    		doicho(a[min],a[i]);
    	}
    }
    Độ phức tạp
    - Về thời gian: O(n2)
    - Về dữ liệu: Không tốn thêm vùng nhớ

    Video minh họa thuật toán


  15. #8
    Tham gia ngày
    Oct 2011
    Bài gởi
    602
    Thanks
    439
    Thanked 984 Times in 275 Posts

    Thuật toán sắp xếp Chèn (Insertion sort)

    Thuật toán sắp xếp chèn làm việc cũng giống như tên gọi - Nó thực hiện việc quét một tập dữ liệu, với mỗi phân tử, thủ tục kiểm tra và chèn phần tử đó vào vị trí thích hợp trong danh sách đích (chứa các phần tử đứng trước nó đã được sắp xếp) được tiến hành.

    Phương pháp dễ dàng nhất để thực hiện thuật toán này là dùng hai vùng chứa dữ liệu khác nhau - tập dữ liệu nguồn và tập dữ liệu mà các phần tử đã sắp xếp được chèn vào. Tuy nhiên để tiết kiệm bộ nhớ, hầu hết các ứng dụng đều chỉ sử dụng một tập dữ liệu duy nhất. Thuật toán được tiến hành bằng cách dịch chuyển phân tử hiện tại đang xét tuần tự qua những phân tử ở vùng dữ liệu phía trước đã được sắp xếp, phép hoán vị nó với phần tử liền kề được thực hiện một cách lặp lại cho tới khi tiến tới được vị trí thích hợp.

    Do với mỗi phân tử, insertion sort cần thực hiện so sánh với các phần tử trước nó nên tối đa số lần duyệt dữ liệu là !N. Vì vậy cũng giống như Bubble sort, Insertion sort được coi là có độ phức tạp O(n2). Mặc dù có cùng độ phức tạp, Insertion sort hiệu quả hơn gần như hai lần so với Bubble sort, tuy nhiên vẫn không hiệu quả với tập dữ liệu lớn.

    Mô tả:


    Cài đặt
    Code:
    void doicho(int &a, int &b)
    {
    	int t;
    	t=a;
    	a=b;
    	b=t;
    } 
    void sapxepchen(int a[], int n)
    {
    	int x, j;
    	for(int i = 0; i < n; i++)
    	{
    		x = a[i];
    		j = i-1;
    		while ((j >= 0) && (a[j] > x))
    		{
    			a[j+1] = a[j];
    			j--;
    		}
    		a[j+1] = x;
    	}
    }
    Độ phức tạp

    Video minh họa thuật họa thuật toán


  16. The Following User Says Thank You to quangvinh For This Useful Post:

    admin (11-23-2011)

  17. #9
    Tham gia ngày
    Oct 2011
    Bài gởi
    602
    Thanks
    439
    Thanked 984 Times in 275 Posts

    Thuật toán Shell-sort

    Được phát minh bởi Donald Shell vào năm 1959, Shell sort là thuật toán hiệu quả nhất trong nhóm các thuật toán sắp xếp có độ phức tạp O(n2). Đương nhiên, Shell sort cũng phức tạp nhất trong các thuật giải thuộc lớp này.

    Shell sort là sự cải tiến của Insertion sort dựa vào hai nhận xét sau đây:

    Insertion sort sẽ rất hiệu quả nếu dữ liệu đầu vào hầu như đã được sắp xếp (đã được xếp trong từng khoảng cục bộ).
    Insertion sort hoạt động kém hiệu quả vì nó di chuyển các giá trị phần tử mỗ i lần chỉ một vị trí.

    Shell sort là môt thuật toán sắp xếp với số gia giãm dần, thường được biết đến như là "comb sort" dành cho những khối chương trình hỗn độn chưa được làm sạch. Thuật toán tạo ra nhiều luồng chạy duyệt qua danh sách dữ liệu, và mỗi lần sắp xếp một số trong những tập dữ liệu được định kích cở như nhau (tập phân đoạn được tách ra từ tập dữ liệu ban đầu) dùng Insertion sort. Sau mỗi lần duyệt qua hết bộ dữ liệu thông qua các phân đoạn (có kích thước giãm dần >= 1) , kích thước của tập được sắp xếp trở nên lớn hơn, cho tới khi nó chứa toàn bộ danh sách dữ liệu. (Chú ý rằng do kích thước của tập tăng lên, số lượng tập dữ liệu cần được sắp xếp sẽ giảm dần) Điều này làm cho Insertion sort đạt tới trường hợp tối ưu nhất, chạy mỗi vòng lặp với độ phức tạp tiến tới O(n).

    Các phần tử chứa trong mỗi tập phân đoạn thì không liền kề nhau - cụ thể hơn, nếu có i tập phân đoạn thì mỗi tập chứa các phần tử thứ i liên tiếp kể từ điểm xuất phát của tập đó. Ví dụ, nếu có 3 tập phân đoạn thì tập đầu tiên sẽ chứa những phần tử tại các vị trí 1, 4, 7 và cứ như thế tiếp tục. Tập thứ hai sẽ chứa những phần tử tại các vị trí 2, 5, 8, và cứ thế tiếp tục về sau; trong khi tập thứ ba sẽ chứa các phần tử ở vị trí 3, 6, 9, và tương tự kế đó.


    Kích thước của tập dữ liệu được sử dụng trong mỗi lần duyệt dữ liệu có ảnh hưỡng lớn tới hiệu quả của việc sắp xếp. Vài nhà nghiên cứu hàng đầu về khoa học máy tính, trong đó có cả Donald Knuth và Robert Sedgewick đã phát triển những phiên bản phức tạp hơn cho shell sort nhằm nâng cao hiệu quả tính toán bằng việc xử lý một cách cẩn thận những tập phân đoạn sao cho có kích thước tốt nhất để dùng cho danh sách dữ liệu được cho.

    Cài đặt

    Code:
    void ShellSort(int a[],int n)
    {
    	int h[]={5,3,1},k=3;
    	int buoc,x,t;
    	for(int j=0;j<k;j++)
    	{
    		buoc=h[j];
    		for(int i=buoc;i<n;i++)
    		{
    			x=a[i];
    			t=i-buoc;
    			while((x<a[t]) && (t>=0))
    			{
    				a[t+buoc]=a[t];
    				t=t-buoc;
    			}
    			a[t+buoc]=x;
    		}
    	}
    }
    Độ phức tạp: O(n2)

    Video minh họa thuật họa thuật toán




  18. The Following 3 Users Say Thank You to quangvinh For This Useful Post:

    admin (11-23-2011), baongoc (11-13-2011), camyvevn (11-11-2011)

  19. #10
    Tham gia ngày
    Oct 2011
    Bài gởi
    590
    Thanks
    42
    Thanked 216 Times in 141 Posts

    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 (Ví dụ: Với mảng 1 3 5 6 9 8 khi chạy đến vị trí số 3 (số 6) thì do các số sau không cần sắp xếp nên k sẽ dừng ở vị trí số 4) để tiết kiệm thời gian.

    Cài đặt
    Code:
    void ShakerSort(int a[], int N)
    {
       int i, k, left, right;
    
       k = 0;
       left = 0;
       right = N - 1;
       while (left < right) {
           for (i = right; i > left; i--)
               if (a[i] < a[i - 1]) {
                   Swap(a[i], a[i - 1]); // Hoan vi a[i], a[i - 1]
                   k = i; // Dung bien k danh dau de bo qua doan da co thu tu.
               }
           left = k;
           for (i = left; i < right; i++)
               if (a[i] > a[i + 1]) {
                  Swap(a[i], a[i + 1]);
                  k = i;
              }
          right = k;
       }
    }
    Ưu điểm: Sắp xếp 2 chiều.

    Nhược điểm: Tuy phức tạp hơn bubble nhưng tốc độ dường như ngang nhau.

  20. The Following 3 Users Say Thank You to soningham For This Useful Post:

    admin (11-23-2011), quangvinh (02-04-2012), trùmspam (02-09-2012)

+ Trả Lời Ðề Tài
Trang 1/2 1 2 cuốicuối

Quuyền Hạn Của Bạn

  • Bạn không thể tạo chủ đề mới
  • Bạn không thể trả lời bài viết
  • Bạn không thể gửi file đính kèm
  • Bạn không thể chỉnh sửa bài viết