Sắp xếp ngoài

Có nhiều bạn hỏi tớ về vấn đề này, tiếc là do đã làm quá lâu nên không còn source code, nhưng ý tưởng thì như sau:

  • Giả sử tập các số cần sắp của bạn được lưu trong file a.txt, bạn đọc ra chừng 10000 số đầu tiên, chạy QuickSort để sắp chúng, rồi ghi 10000 số đã sắp ấy vào file b.txt
  • Tiếp theo lại đọc từ file a.txt 10000 số nữa, lại QuickSort, tiến hành trộn 10000 số đã được sắp đó với 10000 số (cũng đã được sắp) trong file b.txt, đương nhiên trộn 2 dãy đã sắp sẵn thì dễ dàng và truy xuất 2 dãy chỉ là truy xuất tuần tự từ đầu đến cuối (nên mới trộn với file b.txt được, do đọc file là đọc tuần tự mà). Ghi 20000 số đã được trộn vào file c.txt
  • Đến đây đã thấy quy luật: trong file a.txt mình đã đọc đến phần tử 20001, trong file c.txt đã có 20000 số đã sắp. Tiếp tục đọc ra 10000 số nữa từ a.txt, lại trộn với 20000 số kia được 30000 số đã sắp và ghi vào file b.txt, vai trò của b.txtc.txt được hoán đổi liên tục.
  • Lặp lại quá trình này cho đến khi đọc hết file a.txt và cuối cùng kết quả nằm trong 1 trong 2 file b.txt hoặc c.txt, tùy vào vòng lặp của ta dừng lại ở đâu.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s