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

Được sửa bởi littlelee ngày Thu 18 Mar 2010, 12:43; sửa lần 1.

Thuật toán sắp xếp nhanh thuộc loại thuật toán thuộc tư tưởng chia để trị. Trong thuật toán này, ta sẽ chọn một phần tử (pt) mốc, sau đó chuyển toàn bộ các phần tử nhỏ hơn về phía trước, chuyển toàn bộ các pt lớn hơn về phía sau. Sau đó ta tiếp tục chọn mốc trong các phần đã chia để tiếp tục xếp và chia tiếp. Cứ làm như vậy cho đến khi mỗi phần chỉ còn lại 1 pt. Khi đó mảng đã được xếp.

Bài cụ thể:

Code:: uses crt;
var a:array[1..100] of integer;
i,n:integer;

procedure nhap;
begin
clrscr;
write('nhap so phan tu cua mang: ');readln(n);
for i:=1 to n do
begin
write('a[',i,']='); readln(a[i]);
end;
end;

procedure xep(d,c:integer);
var g,h,k,l:integer;
begin
if c-d>0 then
begin
k:=(d+c) div 2;
g:=d; h:=c;
repeat
while a[g]<a[k] do inc(g);
while a[h]>a[k] do dec(h);
if g<=h then
begin
if g<h then begin l:=a[g]; a[g]:=a[h];a[h]:=l; end;
inc(g); dec(h);
end;
until g>h;
xep(d,h);xep(g,c);
end;
end;

begin
nhap;
xep(1,n);
for i:=1 to n do write(a[i],' ');
readln;
end.

Chỉ cần 1 đoạn code chủ yếu thôi. Ko cần cả bài đâu.

hoangtin14 đã viết:: Chỉ cần 1 đoạn code chủ yếu thôi. Ko cần cả bài đâu.

Uhm, cũng đúng, nhưng đối với các bạn yếu hơn thì............còn hên xui. Vì dù sao đi chăng nữa, cách này chạy nhanh nhất và code cũng rắc rối nhất. Rắc rối nhất là ở phân đoạn. Ở cách này, ta dùng đệ quy là hay nhất, nếu ko thì phải dùng thêm mảng, tốn kém lắm, lại phí bộ nhớ nữa vì mỗi đoạn chỉ cần hai chỉ số đầu và cuối mà mỗi cặp chỉ số ấy chỉ dùng có 1 lần duy nhất. Nếu dùng hai biến thì lại.........ko đủ.

- Bài toán:
Cho trước 1 dãy số a có không quá 10^8 phần tử. Các phần tử là các số nguyên có trị tuyệt đối không quá 10.000. Hãy sắp xếp các phần tử trong dãy a theo thứ tự không giảm.

- Phân tích:
Đối với bài này thì quick sort không phải là giải thuật tốt nhất. Hay nói cách khác là không thể dùng ý tưởng chia để trị như bạn nói được. Vì thế ta không nên kết luận quick sort là thuật toán tốt nhất dùng để sắp xếp.

- Câu đố:
Đố các bạn giải thuật sắp xếp nào nhanh nhất để giải bài toán trên? Very Happy

Chắc bài này cỡ thi olympic quá. Khó thật. Với kiến thức của những học sinh lớp 9 thì đúng là không giải được bài này thật. Có lẽ bài này phải dùng một cấu trúc nào đó.

Bài này không dùng cấu trúc dữ liệu đặc biệt gì cả. littlelee nghĩ kỹ xem

- Chú ý: nếu dùng quick sort thì dữ liệu cực đại chạy khoảng 10 giây (không thể chấp nhận)

Bài này đúng khó thật.

hoangtin14 và littlelee thấy dễ quá không chịu làm rồi affraid

.

Còn các bạn khác thử giải đi. không chơi với hoangtin14 và littlelee nữa affraid

Chắc phải mở 1 topic cho anh administrators dạy pascal cho mình quá Nhân ơi. Đưa pic lên chú ý luôn :)

Không biết là hoangtin14 nói thiệt hay nói chơi nữa. Nhưng thôi cứ giải luôn.

Đó là dùng phương pháp thống kê. Có độ phức tạp là O(n) nhanh hơn quick sort O(nlogn)

{Nhập từ bàn phím cho đơn giản}

var a:array[-10000..10000] of longint;
n,k,i,j:longint;
begin

readln(n);
for i:=1 to n do
begin
readln(k);
inc(a[k]);
end;

for i:= -10000 to 10000 do
for j:=1 to a[i] do
write(i,' ');

end.

Nhìn vào đoạn code trên mặc dù ta nhìn thấy 2 vòng for nhưng trên thực tế tổng các bước lặp của nó không quá 20.000 + n.

Nghĩa là với số liệu cực đại chương trình trên chạy không quá 1s.

(Cách tính thời gian đại khái như thế này
for i:=1 to ba trăm triệu do
i:=i;
thì turbo pascal hoặc là free pascal đều chạy sắp sĩ khoảng 1 giây)

Câu nhận xét trên chưa chắc đúng. Các bạn hãy kiểm chứng lại trước khi tin điều đó là sự thật.

Có thẻ là shellsort ko nhỉ. Mà đây là một thuật toán mới hay là một kĩ thuật vậy administrators.

Thuật toán có đọ phức tạp O(NlongN) nè:
Thuật toán này là quick sort:

Code:: Var N,i:longint;
A:Array[1..100000] of longint;
Procedure Sort(L,R:longint);
Var i,j,Key,Tam:longint;
Begin
If L>=R then Exit;
i:=L;
j:=R;
Key:=A[(L+R) div 2];
Repeat
While A[i]<Key do Inc(i);
While A[j]>Key do Dec(j);
If i<=j then
Begin
Tam:=A[i];
A[i]:=A[j];
A[j]:=Tam;
Inc(i);
Dec(j);
End;
Until i>j;
Sort(i,R);
Sort(L,j);
End;
BEGIN
Readln(N);
For i:=1 to N do
Begin
Read(A[i]);
End;
Sort(1,N);
For i:=1 to N do Write(A[i],' ');
END.

Cái này hay nha, trước giờ toàn trung thành với quicksort hôm nay mới được cao thủ chỉ giáo, mà cái này bạn administrator tìm ở đâu thế hình như chưa gặp bao h