Top Ad unit 728 × 90

Latest news

recent

Sắp xếp Counting

Đây là một thuật toán sắp xếp đơn giản có độ phức tạp O(n), thường được dùng để sắp xếp một tập các phần tử có khóa (key: giá trị mà ta dựa vào để xếp thứ tự) là những giá trị nguyên nhỏ. Thuật toán có thời gian thực hiện tuyến tính, các phần tử sắp xếp thuộc về một tập giới hạn, cố định và đã biết trước. Ý tưởng chính của thuật toán là thực hiện việc ánh xạ giá trị key của các phần tử cần sắp xếp thành chỉ mục, thống kê số lần xuất hiện của phần tử sau đó dựa vào thông tin đã có này để chuyển các phần tử từ tập đầu vào sang tập kết quả với vị trí đã sắp xếp. Cụ thể như sau:
Dữ Liệu Vào:
  • A[0 .. n-1]: tập đầu vào có n phần tử với A[m] là số nguyên có giá trị 0 <= A[m] <= K; 0 <= m <= n-1;
  • B[0 .. n-1]: tập kết quả có n phần tử.
  • C[0 .. K]: tập chứa thông tin thống kê và chỉ mục tạm
 Xử lý thuật toán:
  1. Khởi tạo C[0 .. K] có giá trị 0 ở mọi C[m]; 0 <= m <= K;
  2. Đếm số lần xuất hiện của mỗi phần tử trong A và gán vào chỉ mục có giá trị tương ứng với giá trị đó trong C: C[A[m]] = số phần tử có giá trị A[m];
  3. Thực hiện tính tích lũy giá trị các phần tử trong C sao cho C[m] = sum(C[0 .. m]); Về bản chất quá trình này chính là quá trình tính vị trí cuối mới cho loạt các phần tử giống nhau của A trong B.
  4. Chuyển các phần tử từ tập A sang B (đi từ cuối tập hợp) dựa vào vị trí đã tính trong C, mỗi lần chuyển xong một phần tử thì giá trị của C tương ứng phải giãm 1. 
Ví dụ:
  • A[3, 1, 0, 3, 0, 4, 3, 3, 1, 0, 2, 3, 5, 4, 1, 5], K = 5, n = 16
  • Sau bước 1: C[0, 0, 0, 0, 0, 0]
  • Sau bước 2: C[3, 3, 1, 5, 2, 2]
  • Sau bước 3: C[3, 6, 7, 12, 14, 16]
  • Sau bước 4: B[0, 0, 0, 1, 1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5]
Mã nguồn C
Binh Nguyen - Bioz
Sắp xếp Counting Reviewed by Bioz Nguyen on 3:29:00 PM Rating: 5
All Rights Reserved by IEEV © 2009 - 2016
Powered By Blogger, Designed by Sweetheme

Contact Form

Name

Email *

Message *

Powered by Blogger.