Sắp xếp (Sorting)

Sorting

Bài toán: Sắp xếp các phần tử

  1. Dạng đơn giản: sắp xếp dãy số theo thứ tự tăng hoặc giảm dần
  2. Dạng phức tạp: sx dãy các phần tử theo một tính chất/ thuộc tính nào đó tăng hoặc giảm dần

Yêu cầu:

  1. Thành thạo 2 phương pháp sắp xếp phổ biến và hiệu quả: SX nổi bọt (Bubble Sort) và SX nhanh (Quicksort). 
  2. Đối với các bài toán có kích thước đầu vào <5000 nên dùng pp sx nổi bọt; khi kích thước lớn >=5000 nên dùng Quicksort.

Luyện tập trên NTU Coders: 1.3.4.6.7.9.11.14.15

1
TILE
Chồng gạch
2
CASO
Cặp số bằng nhau
3
NHGA
Nhà gần nhất
4
VASU
Vắt sữa bò
5
SXCHON
Sắp xếp chọn
6
CDIE
Cắm điện
7
DOANP2
Chiều dài phủ
8
SXNHANH
Sắp xếp nhanh
9
KIVU
Khiêu vũ
10
BNHAN
Bảng nhân
11
GIDA
Giao đấu (OLP 2014)
12
SXTRON
Sắp xếp trộn
13
SXCHEN
Sắp xếp chèn
14
LUTA
Luyện tập (OLPCĐ 2011)
15
LIXI
Lì xì
16
NHOM
Phân nhóm (Jakarta 2014 - A)
17
CBOX
Hộp đựng tiền
18
BUBE
Búp bê gỗ
19
LUDI
Lưu diễn
20
KIVU2
Khiêu vũ 2
21
TIVI2
Truyền hình 2 (OLPCĐ 2011)
22
KSAN
Khách sạn
23
SXHEAP
Sắp xếp vun đống
24
RANDOM
Sinh số
25
DOANP
Đoạn phủ
26
GEN
GENOME (OLP 2010)
27
LUCKYRE
LUCKYRE

Comments

Post a Comment

Popular posts from this blog

Bài toán dãy tìm con liên tiếp

Image
Thuật toán chia để trị: ta chia bài toán cần giải quyết thành nhiều bài toán con, giải quyết từng bài toán con, sau đó ta tổng hợp lại để giải bài toán lớn. Thuật toán chia để trị được biết đến tiêu biểu qua giải thuật merge-sort… Mặc dù nó được ứng dụng khá nhiều, nhưng nó không có một cách giải quyết tổng quát cho các bài toán. Ta phải hiểu tư tưởng của nó và áp dụng vào từng trường hợp cụ thể. Trong bài viết này, tôi sẽ trình bày một trường hợp áp dụng thuật toán chia để trị, tuy chỉ là một trường hợp áp dụng, nhưng dạng này ta gặp rất thường xuyên. Ta sẽ đi đi từ bài toán tổng quát, rồi áp dụng vào ví dụ cụ thể. Bài toán tổng quát : ta tìm một dãy con liên tiếp trong dãy đã cho để thỏa mãn một tính chất nào đó. Cách giải quyết : Thông thường với kích thước của dãy khoảng N=10^3, ta dùng hai vòng lặp chạy lồng nhau với độ phức tạp O(N^2) để xét tất cả dãy con và tìm ra dãy con phù hợp nhất. Khi N lớn hơn một chút, tầm khoảng N=10^5, ta phải có một giải thuậ...
Read more

Hướng dẫn cách Debug trong Free Pascal

Image
Trong quá trình lập trình, chắc hẳn trong chúng ta ai cũng sẽ không tránh được các lỗi trong chương trình của mình (lỗi cú pháp, lỗi thuật toán, . . . ). Nhưng máy tính thì thực hiện những đoạn chương trình của chúng ta rất nhanh có thể là trong vài giây thậm chí vài mili giây. Vậy thì làm sao chúng ta có thể phát hiện ra những dòng code lỗi trong hàng trăm, hàng nghìn dòng code mà ta đã viết ??? Rất may mắn là trong hầu hết các IDE của các ngôn ngữ lập trình đều hỗ trợ một chức năng rất hay được gọi là Debug, bạn có thể gọi là “bắt bọ” hay chạy từng bước đều được  :)  . Trong bài viết này, tôi sẽ hướng dẫn các bạn làm thế nào để Debug trong IDE Free Pascal. Để Debug được thì bạn cần nắm một số thuật ngữ cơ bản sau : Debug : bắt lỗi, “dò bọ”, “bắt bọ”. Watch : nơi bạn xem sự thay đổi giá trị của các biến. BreakPoint : điểm (dòng) mà bạn sẽ bắt IDE dừng ở đó để bạn xem trạng thái hiện tại của chương trình hay giá trị của các biến. Để bắt đầu quá trình Debug thì...
Read more

Tìm kiếm nhị phân (Binary Search)

Image
Bài toán tìm kiếm một đối tượng trong dãy đối tượng mà có khóa bằng một khóa cho trước. Binary Search Thuật toán tìm kiếm nhị phân dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp, ví dụ như trong một danh bạ điện thoại sắp xếp theo tên, có thể tìm kiếm số điện thoại của một người theo tên người đó. Thuật toán tìm kiếm nhị phân chạy nhanh hơn tìm kiếm tuyến tính nhưng cũng có một số nhược điểm. Tìm kiếm nhị phân có thể chậm hơn bảng băm. Nếu nội dung danh sách bị thay đổi thì danh sách phải được sắp xếp lại trước khi sử dụng tìm kiếm nhị phân. Thao tác này thường tốn nhiều thời gian. Tham khảo thêm tại blog's KienNTT Một số bài tập luyện tập VN.SPOJ.VN http://vn.spoj.com/problems/MOVE12/ http://vn.spoj.com/problems/LEM1/ http://vn.spoj.com/problems/CRUELL2/ http://vn.spoj.com/problems/NDCCARD/ http://vn.spoj.com/problems/TOTALODD/ http://vn.spoj.com/problems/VOPIG/ http://vn.spoj.com/problems/NKSGAME/ http://vn.spoj.com/problems/QBROBOT/ http://vn.s...
Read more