Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Các thuật toán sắp xếp |sắp xếp nhanh|   Tue 09 Mar 2010, 12:27

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.


Được sửa bởi littlelee ngày Thu 18 Mar 2010, 12:43; sửa lần 1.
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Sat 13 Mar 2010, 17:41

Chỉ cần 1 đoạn code chủ yếu thôi. Ko cần cả bài đâu.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Sun 14 Mar 2010, 22:02

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 đủ.
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Wed 17 Mar 2010, 16:42

- 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
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Wed 17 Mar 2010, 17:14

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 đó.
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Wed 17 Mar 2010, 17:34

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)
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Wed 17 Mar 2010, 17:39

Bài này đúng khó thật.
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Wed 17 Mar 2010, 17:44

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
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Wed 17 Mar 2010, 21:14

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 :)
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Wed 17 Mar 2010, 21:48

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.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Wed 17 Mar 2010, 21:57

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.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Mon 26 Jul 2010, 20:45

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.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
whatsgoingon
Gà nhỏ


Tổng số bài gửi : 30
Join date : 18/07/2010
Age : 21
Đến từ : Nơi tận cùng vũ trụ

Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Mon 26 Jul 2010, 21:26

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
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Các thuật toán sắp xếp |sắp xếp nhanh|   Today at 21:32

Về Đầu Trang Go down
 
Các thuật toán sắp xếp |sắp xếp nhanh|
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Những bài thuốc chữa nghẹt mũi
» Những phương thuốc Dân gian
» THUẬN NGHỊCH ĐỘC & vỸ TAM THANH
» Nghệ thuật làm dâu
» ẢO THUẬT

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến