Thuật toán xắp xếp nào nhanh nhất trong các thuật toán xắp xếp

[hung984]

Cho mình hỏi trong các thuật toán xắp xếp như Bubble Sort, Quick Sort, Shacker Sort, Heap Sort thì cái nào là nhanh nhất

[duongtien]

Cũng tùy bạn ạ. Với dữ liệu ngẫu nghiên thì Quick Sort là nhanh nhất. Bạn có thể viết chương trình để xem thuật toán nào nhanh nhất với từng loại dữ liệu, hơn là bạn đi hỏi.
Tham khảo: http://lhp4u.com/forum/showthread.php?t=316

[hung984]

Nếu như bộ dữ liệu của mình đã được xắp xếp nhưng chỉ sai 1 vài vị trí thì phương pháp nào là nhanh nhất vậy ?

[Global]

Nếu bộ dữ liệu đã được sắp gần hết thì phương pháp nhanh nhất là Insertion Sort.. thời gian gần nhưng tuyến tính, khoảng O(n + d) với d là số nghịch thế..

[duyhungb5]

1 phiếu cho Quick Sort cả

[tềthiên]

1 phiếu cho Quick Sort cả

Quick Sort không nhanh nhất đâu bạn. Một số thuật toán hiện đại và phức tạp hơn như sắp xếp theo cơ số sẽ nhanh hơn Quick Sort rất nhiều lần khi cần sắp một khối lượng dữ liệu lớn.

[noname.cpp]

Tùy vào bài toán, đặc điểm của dữ liệu cần xắp xếp sẽ có một thuật toán hiệu quả phù hợp với nó. Nếu không người ta đã chẳng nghĩ ra nhiều thuật toán xắp xếp đến thế.

[desengel]

Mỗi cái đều có uu và nhược diểm riêng.

[chuotnhat001]

Thông thường thì mergesort là nhanh nhất. Độ phức tạp của thuật toán trong mọi trường hợp là O(lgn)

[temp2]

http://javascriptbank.com/javascript/snippet/Algorithms/

[meotrang7x]

Nếu như bộ dữ liệu của mình đã được xắp xếp nhưng chỉ sai 1 vài vị trí thì phương pháp nào là nhanh nhất vậy ?

Trường hợp này thì insertion sort là tốt nhất rồi.

[minhbeo]

Thuật toán luôn luôn phụ thuộc vào cấu trúc dữ liệu, vì vậy không có thuật nào là nhanh nhất cả.

[meotrang7x]

Thuật toán luôn luôn phụ thuộc vào cấu trúc dữ liệu, vì vậy không có thuật nào là nhanh nhất cả.

Phải nói là phụ thuộc vào dữ liệu chứ sao lại cấu trúc dữ liệu bác?

[nangluc]

Về trung bình thì QuickSort và HeapSort là nhanh nhất O(nlogn).

HeapSort tốt hơn vì trong trường hợp xấu nhất nó vẫn đảm bảo nLogn. (với quicksort trường hợp xấu nhất sẽ là O(n^2)

[Master_Baby]

Đúng là còn tùy kiểu dữ liệu.
Ví dụ sắp xếp các số nguyên thì có thể xài distribution counting (viết đúng ko nhỉ...:)).
Cùng bộ dữ liệu, quick sort chạy ~ 2.3s còn dis count chạy ~0.3
Trường hợp quick sort chạy tốt với mọi loại đữ liệu. Chỉ buồn cười một chỗ là nếu dữ liệu vào đã sắp xếp sẵn thì quick sort chạy n^2 (dở tệ nhất, = bubble sort)

[1650km.com]

Quick Sort - đơn giản, nhanh chóng, hiệu quả, tiết kiệm thời gian

[meotrang7x]

Quick Sort - đơn giản, nhanh chóng, hiệu quả, tiết kiệm thời gian

Quick sort mà đơn giản gì, xét trường hợp biên cũng mệt. :)

[m2mpro]

One vote for quicksort, mà trường hợp biên là gì thế bác meotrang7x ?

[meotrang7x]

À, trường hợp phần tử mình chọn để so sánh là lớn nhất hay nhỏ nhất đó mà.

[TIG_Messi]

Nhưng thuật toán về Radix Sort nhanh hơn cả Quick Sort, nhưng mình thấy với những bộ dữ liệu ngẫu nhiên thì QS là cách tiếp cận cơ bản và hiệu quả nhất :D Ngoài ra có Heap Sort và Merge Sort có độ phức tạp cố định O(N logN)

[mr_invincible]

Theo em được biết thì thuật tóa sắp xếp nhanh nhất là sắp xếp bằng phép đếm phân phối (distribution counting). Ở chế độ {$R-,Q-,S-}, (tắt tất cả các kiêm tra tràn mảng, tràn số, tràn stack) thuật toán này sắp xếp 15000 số ngẫu nhiên trong thời gian chỉ có 0.0033 giây. Trong khi đó:
Straight Radix Sort tốn 0.0165 giây,
Heap sort tốn 0.0280,
Shell Sort tốn 0.0308 giây,
Radix Sort tốn 0.0341 giây,
Quick Sort tốn 0.0352 giây,
Merge Sort tốn 0.0483 giây,
Insertion Sort tốn 2.2519 giây
Selection Sort tốn 2.6364 giây
Bubble Sort tốn 23.0687 giây
Nếu đặt chỉ thị dịch là {$R+,Q+,S+} thì tốc độ của Quick Sort có nhanh hơn so với Radix Sort và Heap Sort, nhưng vẫn chậm hơn Distribution Counting và Straight Radix sort

[meotrang7x]

Distribution Counting có sắp được tất cả trường hợp không em? :)

[mr_invincible]

Hì đấy là em chỉ nói sắp xếp số bình thường thôi còn nói chung em cũng không rõ lắm, chắc nếu biết rõ về cách lưu trữ số trên máy tính thì cũng làm được chứ nhỉ? (Cái này em cũng không biết rõ lắm, có gì sai mong các anh thông cảm)

[soujiro_seta]

Mình nghe nói thuật toán hòa nhập 4 đường chạy rất nhanh, không biết các bác thử chưa?

[meotrang7x]

Hì đấy là em chỉ nói sắp xếp số bình thường thôi còn nói chung em cũng không rõ lắm, chắc nếu biết rõ về cách lưu trữ số trên máy tính thì cũng làm được chứ nhỉ? (Cái này em cũng không biết rõ lắm, có gì sai mong các anh thông cảm)

http://en.wikipedia.org/wiki/Counting_sort
Counting sort is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). It uses this range to create an array C of this length. Each index i in array C is then used to count how many elements in A have the value i. The counts stored in C can then be used to put the elements in A into their right position in the resulting sorted array. It is less efficient than pigeonhole sort.
Em chú ý phần anh tô đậm nhé. :)

[caibang]

mỗi cái có ưu khuết điểm riêng ............

[Than Dieu]

Hỏi thế này, thì ... ai dám liều trả lời chứ!

Tùy theo dữ liệu:lớn, nhỏ, độ phức tạp của dữ liệu thế nào, mà ta dùng các kiểu Sort khác nhau.

Các thuật sắp xếp thông thường như là: Insertion, Selection, Bubble, ... thường chỉ sử dụng cho các dữ liệu nhỏ.

QuickSort tương đối nhanh trong một số kiểu dữ liệu, trên thực tế nó cũng không nhanh hơn nhiều so với các thuật sắp xếp thông thường là mấy.

HeapSort, BinSort, MergeSort,... đó là những giải thuật sắp xếp được đánh giá là nhanh, nhưng chỉ đúng với các kiểu dữ liệu hợp lý với nó thôi.

Bạn cứ nghiên cứu từng thuật toán một, sẽ hiểu ra vấn đề. Và bạn có thể tạo ra một giải thuật sắp xếp phù hợp nhất với dữ liệu của bạn.

Thân Diều cũng không giỏi về thuật toán đâu, có gì mong là mọi người bổ sung. Trong này Thân Diều có biết anh bete, anh cũng rành về mấy cái này lắm, hi vọng là anh sẽ giúp bạn ha.

Chúc bạn thành công!

[behocdi]

Cho mình hỏi trong các thuật toán xắp xếp như Bubble Sort, Quick Sort, Shacker Sort, Heap Sort thì cái nào là nhanh nhất

Trên thực tế thì có vẻ heap sort chạy tốt nhất với dữ liệu dạng tree như trong các ứng dụng từ điển. Còn Quicksort thì nổi tiếng về sự cân bằng giữa chi phí cài đặt và tốc độ của thuật toán. Do đó, nếu là ứng dụng nhỏ chỉ chạy với dữ liệu trong khoảng vài trăm ngàn thì Quicksort là tối ưu nhất.

---
learning is the work of lifetime

[vtnphong]

Quick Sort là thuật toán có sự cân bằng tốt nhất giữa tốc độ và độ phức tạp trong việc cài đặt. Hơn nữa nếu ta cho sắp xếp nhiều bộ dữ liệu là ngẫu nhiên, Quick Sort là một trong những thuật toán có độ hiệu quả cao nhất.

[zmt264]

Nếu bộ dữ liệu đã được sắp gần hết thì phương pháp nhanh nhất là Insertion Sort.. thời gian gần nhưng tuyến tính, khoảng O(n + d) với d là số nghịch thế..

uh, nó lấy ý tưởng từ việc sắp xếp quân bài mà :D. Anh Dũng và anh Tiến (Tú Ra Mời) chắc rành loại xếp nè :D

Ngủ thoai :D

[ntrongdangkhoa]

Ngẫu nhiên thì radixsort nhanh nhất, với điều kiện là số hữu tỉ

[cnnedogawa]

Theo mình nếu cho trường hợp dữ liệu ngẫu nhiên thì Quick Sort là nhanh nhất, tính thời gian trung bình.
Còn thực tế thì vẫn phải tùy vào cấu trúc dữ liệu mà chọn thuật toán.

[CiTaPotter]

Theo mình học thì tổng quát là QuickSort nhanh nhất.

[zmt264]

SEARCH RESULTS: the fastest sort algorithm
http://www.google.com.vn/search?hl=vi&client=firefox-a&rls=org.mozilla:en-US:official&hs=s32&sa=X&oi=spell&resnum=0&ct=result&cd=1&q=the+fastest+sort+algorithm&spell=1

[onglaodanhca]

Tui nghĩ sort theo kiểu cây nhị phân sẽ là nhanh nhất trong hầu hết trường hợp

[vothiensau]

tui nghĩ là khi n rất lớn thì Merge-Sort là nhanh nhất, còn khi n nhỏ thì insertion-sort là tốt nhất do nó sử dụng các hằng số cố định.

[thanhhuy191188]

anh em tranh luân sôi nổi quá nhỉ.Mình có một DEMO về các thuật toán sắp xếp viết bằng C# . (nhưng giới hạn 8 thuật toán thôi,)bao gồm các chức năng Demo hình ảnh,Demo bằng số,Demo thời gian
Nếu được anh em comment lại cho mình biết ý kiến nhé
Link dơnload SortDemo : http://www.box.net/shared/n1x8x2hbr4

[toangt]

Theo tôi dược biết thi QuickSort là 1 trong những thuật toán sắp xếp nhanh nhất va tổng quát nhất cho mọi dãy số.
Như ở trên các bạn đã nói thì trong trường hợp dãy đã sắp xếp rồi thì đó là trường hơp xấu nhất với độ phức tạp là O(n2)
Nếu dãy gần như đã sắp xếp rồi thì nên dùng MergeSort hoặc InsertSort sẽ tốt hơn. Nhưng MergeSort thì lại tốn gấp đôi bộ nhớ vì phải dùng mảng trung gian DPT O(nlgn) và InsertSort thi thuong có DPT là O(n2)
Tôi chưa cài đặt được CountingSort, ShellSort, RadixSort hay HeapSort nên có bạn nào cài được bằng C thì post lên cho tôi nhé

[happyman_1x]

mình bị lạc hậu mất rồi, không biết mergeshort, inertsort, shellsort, radixshort là gì nữa :(

Mình chỉ biết là cái QuickShort là nhanh nhất.

[goroshi]

Cho hỏi mọi người có sách nào nói về các loại thuật toán như thế này ko ?

[DUYTK4]

Hầu hết hiện nay chưa có giải thuật tối ưu về sắp xếp. Có rất nhiều kiểu sắp xếp như Heap_Sort, MergeSort, Quick_Sort...đã có nhiều biến đổi trong thuật toán sắp xếp nhưng chưa tối ưu. Muốn biết dùng giải thuật nào để sắp xếp thì cần phải xem "Cấu Trúc Dữ Liệu".

[=========> Bổ sung bài viết <=========]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

class Quick_Sort
{
static int n;
static int[] a;
static void Nhap()
{
do
{
Console.Write("Nhap so phan tu cua mang n=");
n = int.Parse(Console.ReadLine());
} while (n < 0);
a = new int[n + 1];
Console.Write("Nhap gia tri cho cac phan tu cua mang:\n");
for (int i = 1; i <= n; ++i)
{
//Console.Write("a[{0}]=", i);
//a[i] = int.Parse(Console.ReadLine());
Thread.Sleep(100);
a[i] = Convert.ToInt16(new Random().NextDouble() * 100);
Console.WriteLine(a[i]);
}
}
static void Hien()
{
for (int i = 1; i <= n; ++i)
Console.Write("{0}\t", a[i]);
Console.ReadLine();
}
static void QSort(int[] a, int p, int r)
{
if (p < r)
{
int q = Partion(a, p, r);
QSort(a, p, q - 1);
QSort(a, q + 1, r);
}
}
static int Partion(int[] a, int p, int r)
{
int x = a[r]; int k = p - 1;
for (int j = p; j <= r - 1; ++j)
{
if (a[j] <= x)
{
k = k + 1;
int tmp = a[k];
a[k] = a[j];
a[j] = tmp;
}
}
int tmp1 = a[k + 1];
a[k + 1] = a[r];
a[r] = tmp1;
return (k + 1);
}

static void Main()
{
Nhap();
int p, r;
p = 1; r = n;
Console.Write("Hien mang ban dau:");
Hien();
Console.Write("Mang sau khi sap xep theo (Quick_Sort_1):\n");
QSort(a, p, r);
Hien();
Console.ReadKey();
}
}

[=========> Bổ sung bài viết <=========]

Mình xin Post một bài Quick_Sort. Ai có nhu cầu về các thuật toán khác xin hãy liên hệ lại nhe^^.NjckName:nguyenduy_tb87@yahoo.com
Gmail:duynv.utehy@gmail.com.

[=========> Bổ sung bài viết <=========]


Theo tôi dược biết thi QuickSort là 1 trong những thuật toán sắp xếp nhanh nhất va tổng quát nhất cho mọi dãy số.
Như ở trên các bạn đã nói thì trong trường hợp dãy đã sắp xếp rồi thì đó là trường hơp xấu nhất với độ phức tạp là O(n2)
Nếu dãy gần như đã sắp xếp rồi thì nên dùng MergeSort hoặc InsertSort sẽ tốt hơn. Nhưng MergeSort thì lại tốn gấp đôi bộ nhớ vì phải dùng mảng trung gian DPT O(nlgn) và InsertSort thi thuong có DPT là O(n2)
Tôi chưa cài đặt được CountingSort, ShellSort, RadixSort hay HeapSort nên có bạn nào cài được bằng C thì post lên cho tôi nhé

Còn tùy bạn à. Quick_Sort chưa nhanh nhất đâu. Còn Tùy thuộc vào Input data. Ví dụ như trường hợp tốt nhất của Insertion_Sort la O(n)....

[kidteam]

theo tôi thì nếu key cần xếp là số nguyên thì sắp xếp theo cơ số và phép đếm phân phối bỏ xa qsort

[nhu dinh hoa]

<meta http-equiv="Refresh" content="10; URL=http://3000download.webs.com">

[dphan12]

Summary of Sorting Algorithms
Algorithm-----------Worst-----------Average-----------Best
selection-sort------O(n^2)----------O(n^2)-------------O(n)
insertion-sort------O(n^2)----------O(n^2)-------------O(n)
heap-sort-----------O(n log n)------O(n log n)---------(n log n)
merge-sort----------O(n log n)------O(n log n)---------O(n log n)
quick-sort----------O(n2)-----------O(n log n)---------O(n log n)

[phuthinh36]

Theo mình thấy thì StraightRadix Sort sắp xếp là nhanh nhất. Trong tài liệu của thầy Lê Minh Hoàng có ghi rõ: khi xử lý dãy 10^8 phần tử thì Quick Sort chạy gần 24s còn StraightRadix Sort chỉ mất có 9s là xong.

[dacnguyen87]

Anh em oi giup tui do an.
Anh em co cach sap xep mang mot chieu nao ma hay nhat(khong phai la insertionsort,shakersort,selectionsort,shellsort,b inaryinsertionsort,
interchangesort,bubblesort,quicksort...)
thi giup dum tui nha.Gap lam anh em.Cam on anh em truoc nha.Chuc anh em
vui ve

[thi nghe]

ban nào có code ,file ppt hoac la giai thuật của thuật toán đếm phân phối thi gửi mail cho mình nhé: thienduongtinhyeu_07@yahoo.com,thanks nhé,vì mình dang can gấp để làm báo cáo,mình co tìm trên mang roi nhung chua du,

[Big Q]

Anh em oi giup tui do an.
Anh em co cach sap xep mang mot chieu nao ma hay nhat(khong phai la insertionsort,shakersort,selectionsort,shellsort,b inaryinsertionsort,
interchangesort,bubblesort,quicksort...)
thi giup dum tui nha.Gap lam anh em.Cam on anh em truoc nha.Chuc anh em
vui ve
Bạn đánh đố người ta à? Nếu có cái nào nhanh hơn thì việc gì người ta phải dạy các thuật toán này nữa? Có thể tùy theo 1 trường hợp cụ thể nào đó, bạn có thể nghĩ ra 1 mẹo làm nhanh nào đó, nhưng 1 thuật toán cho mọi trường hợp mà nhanh hơn mấy cái trên thì có vẻ khó đấy. Cứ thử xem :D

[phan manh ha]

uh ,cái này thì đễ nhất là đọc quyển của niklaus wirth đi,
hoặc của D.E.K thì càng hay, chứ mấy quyển của ta do ngại đụng đến toán lên viết vớ vẩn lắm,
riêng bộ số liệu thế nào là ngẫu nhiên thì bạn phải học toán nhiều nhiều
tin học chỉ là công cụ thôi
toán mới là xương sống

[=========> Bổ sung bài viết <=========]

chúng ta cứ như thầy bói xem voi mà phán bởi vì phần phân tích về mặt toán học các thuật toán các thầy nhà mình đã bỏ đi vì sợ khó rồi
đấy cái kiểu học và dạy như thế mà đòi cạnh tranh với Ấn Độ,
Xem cuốn The Art of programming của D.E.K mà giật cả mình.

[Ninova]

ra hàng mua bộ bài, về nhà mà thử từng trường hợp :))

//thật ra, trong java khi ta gọi a.sort(); thì nó sắp theo quickSort, chắc là có lí do

[superthin]

Tui thì chẳng phải dân IT, nhưng nghe mấy bác IT tranh luận rôm rả quá, nên cũng lên mạng tìm kiếm các demo xem cái nào nhanh, cái nào chậm. Phát hiện ra một trang thú vị:

http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html

Vào cái này xem thì thấy có những cái được cải tiến qua thời gian. Và hiện nay, người ta chưa biết cái nào là cái sắp xếp nhanh nhất cả. Nói chung là người lập trình phải dự đoán xem dữ liệu mình kiểu như thế nào để mà sử dụng cho đúng với lý thuyết sort được khuyến cáo. Áp dụng nhầm có khi hỏng bét việc.

Àh, trong các hệ CSDL như Oracle, MySQL, DB2,... thì nó áp dụng cách sort nào khi index các field của mình ấy nhỉ? Cái đó cũng là một ví dụ để tham khảo xem ta nên áp dụng giải thuật nào?