Lên đầu trang

Algorithm Help & Documentation

Index
Tổng quát
1. Các biến tổng quát
2. Hàm addData()
3. Hàm addValue(value)
4. Hàm onMouse(obj,color)
5. Hàm clickMouse(obj,color)
6. Hàm paintRow(obj)
7. Hàm catchKeyPress()
8. Hàm setDIVPos() và moveDIVPos()
Về mã nguồn các giải thuật
Chi tiết các giải thuật
- Heap Sort
  1. Hàm heapSort(A)
  2. Hàm buildMaxHeap(A)
  3. Hàm exchange(pos1,pos2)
  4. Hàm maxHeapify(A,i)
  5. Hàm parent(i)
  6. Hàm leftChild(i)
  7. Hàm rightChild(i)
  8. Hàm Print(arr)
  9. Hàm randomValue()
  10. Hàm defValue()
  11. Hàm printit()
  12. Hàm checkNum(k,num)
- Quick Sort
  1. Hàm QuickSort(arr,left,right)
  2. Hàm Partition(arr,left,right)
  3. Hàm checkArray(i)
  4. Hàm randomValue()
  5. Hàm defValue()
  6. Hàm printit()
  7. Hàm Print(stat,x)
- Counting Sort
  1. Hàm CountingSort(A,B,k)
  2. Hàm findMax(arr)
  3. Hàm Print(arr)
  4. Hàm randomValue()
  5. Hàm defValue()
  6. Hàm printit()
- Radix Sort
  1. Hàm RadixSort(A,d)
  2. Hàm insertRadix(A,i)
  3. Hàm Sort(A,B,d)
  4. Hàm printProcess(tableProcess)
  5. Hàm Print(arr,k)
  6. Hàm randomValue()
  7. Hàm defValue()
  8. Hàm printit()
  9. Hàm addValueRS(value)
  10. Hàm addDataRS()
  11. Hàm numLength(num)
- Bucket Sort
  1. Hàm BucketSort(A)
  2. Hàm insertList(index,x)
  3. Hàm InsertionSort(A)
  4. Hàm Print(arr,k)
  5. Hàm randomValue()
  6. Hàm defValue()
  7. Hàm printit()
  8. Hàm addValueBS(value)
  9. Hàm addDataBS()
  10. Hàm numLength(num)

I. Tổng quát

Tài liệu này hiện có 5 giải thuật sắp xếp, các giải thuật đều được hiện thực trên ngôn ngữ JavaScript:

Heap Sort
Quick Sort
Counting Sort
Radix Sort
Bucket Sort

Mỗi giải thuật đều có các chức năng:

Thêm vào dữ liệu bởi người dùng để thực hiện giải thuật
Hiển thị dữ liệu trước, trong và sau khi thực hiện giải thuật
Khởi tạo giá trị mặc định cho từng giải thuật
Khởi tạo giá trị ngẫu nhiên cho từng giải thuật
Mã nguồn của từng giải thuật
Hướng dẫn chi tiết

Bên cạnh đó, cả 5 giải thuật đều dùng chung file generalFunctions.js cho các vấn đề về giao diện và hiển thị. File này có các biến, hàm với những chức năng và công dụng như sau:

Các biến tổng quát

num : biến lưu trữ ID từng bảng, được dùng để xác định bảng mà người dùng muốn đánh dấu làm nổi bật
k : số phần tử của mảng dùng cho các giải thuật
a : mảng dùng để lưu các giá trị cho việc thực hiện các giải thuật
colorOver : màu của ô chứa giá trị số sẽ thay đổi sang khi người dùng rê chuột vào nó, mã màu dạng Hexa Decimal
colorOut : màu của ô chứa giá trị số sẽ thay đổi sang khi người dùng rê chuột ra khỏi nó
colorClick : màu của ô chứa giá trị số sẽ thay đổi sang khi người dùng click chuột ra vào nó
rowColor : màu của bảng sẽ đổi sang khi người dùng chọn đánh dấu nó
flag : giá trị dùng để nhận biết giá trị chốt ở các giải thuật Quick Sort và Counting Sort
fontSize : cỡ chữ của các giá trị khi hiển thị trong bảng, đơn vị tính là pixel
width : chiều rộng các ô giá trị, đơn vị tính là pixel
space : khoảng cách giữa hai ô giá trị kế nhau, đơn vị tính là pixel

Hàm addData()

Công dụng: hàm được dùng để cho người sử dụng thêm dữ liệu vào theo 2 dạng:
o Dạng 1: thêm dữ liệu vào mảng từ một chuỗi chứa các giá trị số, bằng cách gọi hàm addValue(data)
o Dạng 2: thêm dữ liệu vào mảng bằng lần lượt từng con số
Cách thức hoạt động của hàm:
o Bước 1: đưa vào biến data dữ liệu do người dùng nhập, thông qua dòng lệnh var data = document.data.array.value;o Bước 2: nếu chưa có dữ liệu, data='', thì yêu cầu người dùng phải nhập vào
o Bước 3: ngược lại, nếu đã có dữ liệu, thì kiểm tra xem người dùng muốn thêm dữ liệu vào theo dạng nào:
    + Nếu là dạng 1, thì trong data sẽ có chứa một trong những kí tự phân cách giữa các số, thì gọi hàm addValue(data);
    + Nếu là dạng 2, sẽ không có kí tự phân cách, thì thực hiện kiểm tra xem đó có phải là một giá trị số hay không
        - Nếu là một số hợp lệ thì thêm vào mảng
        - Ngược lại thì thông báo cho người dùng và yêu cầu một con số hợp lệ

Hàm addValue(value)

Công dụng: được dùng để thêm dữ liệu vào mảng a từ một chuỗi chứa các giá trị số do người dùng nhập vào
Cách thức hoạt động của hàm:
o Bước 1: khởi tạo số phần tử của mảng a là k=0, và tạo chuỗi rỗng str
o Bước 2: chạy vòng lặp for, xét duyệt từng kí tự của chuỗi dữ liệu value, thực hiện:
    + Nếu kí tự đang xét không phải là dấu phân cách giữa các số thì chuỗi str=str + kí tự này
    + Ngược lại, nếu là một trong những kí tự phân cách ("," ";" " "), thì kiểm tra xem chuỗi str có đúng là một giá trị số hay không?
    + Nếu str đúng là một giá trị số thì thêm vào mảng a và tăng số phần tử k lên 1, k++
    + Ngược lại, nếu str không phải là một giá trị số thì thông báo với người dùng giá trị này không hợp lệ, sau đó hủy bỏ quá trình thêm dữ liệu (tuy nhiên, ta vẫn có thể tác động để không hủy bỏ, xin xem chi tiết cụ thể trong mã nguồn)
o Bước 3: thông báo cho người dùng biết quá trình thêm dữ liệu hoàn tất. Người dùng phải nhấn nút Print để xử lí dữ liệu tùy theo giải thuật và in kết quả.

Hàm onMouse(obj,color)

Công dụng: dùng để đổi màu ô chứa giá trị khi người dùng rê chuột vào/ra
Cách thức hoạt động:
o Bước 1: kiểm tra xem ô này có được người dùng click vàp để đánh dấu hay chưa
o Bước 2: nếu ô chưa được đánh dấu thì thực hiện việc đổi màu ô này sáng màu mới color khi người dùng rê chuột vào/ra, ngược lại, nếu ô đã được đánh dấu thì không thực đổi màu

Hàm clickMouse(obj,color)

Công dụng: có tác dụng đánh dấu ô số khi người dùng click chuột vào ô
Cách thức hoạt động:
o Bước 1: kiểm tra xem người dùng muốn đánh dấu hay hủy đánh dấu, bằng cách so sánh màu của ô số với màu của biến colorClick
o Bước 2: thực hiện đánh dấu hoặc hủy đánh dấu theo yêu cầu của người dùng

Hàm paintRow(obj)

Công dụng: có tác dụng đánh dấu một hàng/bảng nhằm làm nổi bật nó
Cách thức hoạt động của hàm:
o Bước 1: xác định đối tượng hàng/bảng mà người dùng muốn đánh dấu hoặc hủy đánh dấu qua dòng lệnh rowObj = document.getElementById(obj).style;
o Bước 2: kiểm tra xem người dùng muốn đánh dấu hay hủy đánh dấu, bằng cách so sánh màu của hàng/bảng với màu của biến rowColor
o Bước 3: thực hiện đánh dấu hoặc hủy đánh dấu theo yêu cầu của người dùng

Hàm catchKeyPress()

Công dụng: dùng để kiểm tra xem người dùng có sử dụng phím Enter để nhập dữ liệu vào mảng theo dạng 2 không
Hạn chế:
- Người dùng phải bật bộ quản lí sự kiện người dùng ấn phím trên tài tài liệu của chương trình
- Đồng thời các script giải thuật phải được chạy ở chế độ Preview trong môi trường Microsoft Frontpage
- Hàm này chỉ có tác dụng cho hai giải thuật Quick Sort và Counting Sort
Cách thức hoạt động của hàm:
o Bước 1: bắt lấy mã ASCII của phím mà người dùng vừa gõ vào, thông qua dòng lệnh var key = event.keyCode;
o Bước 2: nếu đây là phím Enter, key=13, thì thực hiện việc thêm dữ liệu mà không cần người dùng nhấn nút Add

Hàm setDIVPos()

Công dụng: dùng để thiết lập trí vị của liên kết "Lên đầu trang" trong mỗi giải thuật

Hàm moveDIVPos()

Công dụng: làm cho liên kết "Lên đầu trang" trong mỗi tài giải thuật luôn di chuyển theo thanh trượt và luôn nằm ở tọa độ xác định

II. Về mã nguồn của giải thuật

Giải thuật được hiện thực bằng ngôn ngữ JavaScript trong môi trường Microsoft Frontpage 2003.

Mã nguồn chỉ chứa các dòng lệnh cho việc giải quyết bài toán được đặt ra mà không giải quyết các vấn đề về giao diện, hiển thị của bài toán trong tài liệu này.

Mã nguồn của các giải thuật được lưu trong các tập tin sau:

Heap Sort: HeapSort/sourceHeapSort.htm
Quick Sort: QuickSort/sourceQuickSort.htm
Counting Sort: CountingSort/sourceCountingSort.htm
Radix Sort: RadixSort/sourceRadixSort.htm
Bucket Sort: BucketSort/sourceBucketSort.htm

Màu dùng trong mã nguồn được qui định như sau:

màu tía : được dùng cho các từ khóa trong ngôn ngữ JavaScript
màu xanh : được dùng cho các toán tử trong ngôn ngữ JavaScript
màu đỏ : được dùng cho các giá trị số trong ngôn ngữ JavaScript
màu đen: được dùng cho các đối tượng còn lại

III. Chi tiết các giải thuật

a. Heap Sort

Mã nguồn của giải thuật Heap Sort nằm trong file HeapSort/HeapSort.htm, có các biến và hàm với công dụng như sau:

Hàm heapSort(A)

Công dụng: thực hiện giải thuật sắp xếp heap Sort trên mảng đầu vào A
Cách thức hoạt động:
o Bước 1: xây dựng một max heap trên mảng A
o Bước 2: chạy vòng lặp for, quét hết tất cả các giá trị của mảng A từ đầu đến cuối, thực hiện
    + Hoán đổi vị trí của phần tử thứ 0 với vị trí thứ i
    + Giảm số phần tử tồn tại trên heap đi 1, heapSize -= 1
    + Thực hiện maxHeapify(A,0) trên mảng A với heapSize mới này, nhằm bảo đảm mảng A tồn tại như là một max heap
    + In ra cột Process mảng A mới vừa thực hiện xong

Hàm buildMaxHeap(A)

Công dụng: xây dựng một max heap trên mảng A

Hàm exchange(pos1,pos2)

Công dụng: dùng để hoán đổi vị trí giữa hai phần tử trong mảng
Cách thức hoạt động:
o Bước 1: cho một giá trị tạm bằng phần tử thứ nhất, temp = a[pos1];
o Bước 2: gán phần tử thứ nhất bằng phần tử thứ hai
o Bước 3: gán phần tử thứ hai bằng giá trị tạm temp

Hàm maxHeapify(A,i)

Công dụng: bảo đảm cho mảng A, bắt đầu từ vị trí i, phải thoả mãn đúng tính chất của một max heap
Cách thức hoạt động:
o Bước 1: tìm con trái và phải của giá trị tại vị trí thứ i
o Bước 2: kiểm tra nếu con trái vẫn thuộc heapSize và giá trị của con trái lớn hơn giá trị tại i thì cho giá trị lớn nhất là giá trị con trái, ngược lại thì giá trị lớn nhất là giá trị tại i
o Bước 3: kiểm tra nếu con phải vẫn thuộc heapSize và giá trị của con phải lớn hơn giá trị lớn nhất thì cho giá trị lớn nhất là giá trị con phải
o Bước 4: kiểm tra nếu giá trị lớn nhất không phải là i thì thực hiện:
+ Hoán đổi vị trí giữa i và lớn nhất largest
+ Thực hiện đệ qui maxHeapify trên A tại vị trí mới largest

Hàm parent(i)

Công dụng: dùng để trả về vị trí cha của vị trí tại i
Cách thức hoạt động:
o Bước 1: kiểm tra tính chẵn lẻ của i
+ Nếu i chẵn, i%2 = 0, thì vị trí cha của giá trị tại vị trí i là i/2 - 1
+ Nếu i lẻ, i%2!=0, thì vị trí cha của giá trị tại vị trí i là (i - i%2)/2
o Bước 2: trả về vị trí cha của giá trị tại vị trí i

Hàm leftChild(i)

Công dụng: trả về vị trí nốt con phía trái của giá trị tại vị trí thứ i

Hàm rightChild(i)

Công dụng: trả về vị trí nốt con phía phải của giá trị tại vị trí thứ i

Bên cạnh đó, giải thuật HeapSort còn sử dụng các hàm hỗ trợ trong việc hiện thực các chức năng và hiển thị giao diện. Các hàm này được lưu trong file HeapSort/HeapSortFunctions.js

Hàm Print(arr)

Công dụng: thiết lập các giá trị trong mảng arr vào một bảng, dùng để in ra

Hàm randomValue()

Công dụng: khởi tạo các giá trị ngẫu nhiên cho mảng và thực hiện giải thuật sắp xếp Heap Sort trên mảng vừa tạo
Cách thức hoạt động:
o Bước 1: xóa tất cả dữ liệu đã in trong các khu vực
o Bước 2: yêu cầu người dùng nhập vào số phần tử sẽ tạo, nếu không nhập, chương trình sẽ tự động thực hiện thuật giải với các giá trị mặc định
o Bước 3: khởi tạo mảng chứa dữ liệu với số phần tử người dùng đã nhập
o Bước 4: chạy vòng lặp while để thêm dữ liệu vào mảng, thêm cho đến khi đủ số phần tử được yêu cầu thì ngưng vòng lặp và thực hiện giải thuật, in ra kết quả

Hàm defValue()

Công dụng: khởi tạo các giá trị như trong slide bài giảng và thực hiện giải thuật

Hàm printit()

Công dụng: sẽ thực thi giải thuật Heap Sort với dữ liệu do người dùng nhập vào và nhấn nút Print trong chương trình

Hàm checkNum(k,num)

Công dụng: so sánh giá trị của số num và giá trị cha của k. Hàm này dùng để kiểm tra trong việc xây dựng một max heap với mảng dữ liệu đã có

b. Quick Sort

Mã nguồn của giải thuật Quick Sort nằm trong file QuickSort/QuickSort.htm, có các biến và hàm với công dụng như sau:

Hàm QuickSort(arr,left,right)

Công dụng: thực hiện đệ qui để sắp xếp các giá trị của mảng arr
Cách thức hoạt động:
o Bước 1: kiểm tra xem còn phần tử để sắp xếp hay không?
o Bước 2: nếu còn thì thực hiện quá trình phân hoạch mảng arr thành các mảng con nhỏ hơn và thực hiện sắp xếp từng mảng con cho đến khi không còn phần tử nào để sắp xếp

Hàm Partition(arr,left,right)

Công dụng: phân hoạch và sắp xếp mảng arr dựa vào vị trí left, right
Cách thức hoạt động:
o Bước 1: chọn giá trị phần tử chốt là x = arr[right];
o Bước 2: chạy vòng lặp for, quét các phần tử của arr từ left đến right, thực hiện
    + Tìm các phần tử arr[j] < phần tử chốt x
    + Nếu tìm thấy thì thực hiện trao đổi vị trí của arr[i] và arr[j]
    + In ra mảng arr với sự thay đổi này
o Bước 3: thực hiện trao đổi giá trị giữa phần tử đếm i với phần tử chốt arr[right]
o Bước 4: trả về giá trị đếm i+1

Bên cạnh đó, giải thuật QuickSort còn sử dụng các hàm hỗ trợ trong việc hiện thực các chức năng và hiển thị giao diện. Các hàm này được lưu trong file QuickSort/QuickSortFunctions.js

Hàm checkArray(i)

Công dụng: kiểm tra giá trị trùnh lặp trong mảng khi thêm dữ liệu
Cách thức hoạt động:
o Bước 1: chạy vòng lặp for, quét hết các giá trị đang tồn tại trong mảng, nếu phần tử cần thêm vào i đã có thì thoát khỏi vòng lặp và trả về false
o Bước 2: nếu quét hết mảng mà không tìm thấy giá trị trùng lắp thì trả về true

Hàm randomValue()

Công dụng: khởi tạo các giá trị ngẫu nhiên cho mảng và thực hiện giải thuật Quick Sort
Cách thức hoạt động:
o Bước 1: xóa tất cả các dữ liệu đã in ra trước đó trong các khu vực
o Bước 2: yêu cầu người dùng nhập vào số phần tử, nếu không nhập, chương trình sẽ tự động thực hiện thuật giải với các giá trị mặc định
o Bước 3: khởi tạo mảng chứa dữ liệu với số phần tử người dùng đã nhập và thêm vào mảng các giá trị không trùng lặp
o Bước 4: khởi tạo phần tử chốt của mảng và bắt đầu thực hiện giải thuật Quick Sort với phần tử chốt này

Hàm defValue()

Công dụng: khởi tạo các giá trị như trong slide bài giảng và thực hiện giải thuật

Hàm printit()

Công dụng: sẽ thực thi giải thuật Quick Sort với dữ liệu do người dùng nhập vào và nhấn nút Print trong chương trình

Hàm Print(stat,x)

Công dụng: thiết lập các giá trị trong mảng arr vào một bảng, dùng để in ra

c. Counting Sort

Mã nguồn của giải thuật Counting Sort nằm trong file CountingSort/CountingSort.htm, có các biến và hàm với công dụng như sau:

Hàm CountingSort(A,B,k)

Công dụng: thực hiện sắp xếp mảng A theo giải thuật Counting Sort, với k là số phần tử của A và mảng kết quả B
Cách thức hoạt động:
o Bước 1: chạy vòng lặp for, gán tất cả giá trị trong mảng trung gian C là 0
o Bước 2: chạy vòng lặp for, đếm số phần tử giống nhau có trong A
o Bước 3: chạy vòng lặp for để đếm số phần tử nhỏ hơn hoặc bằng C[i]
o Bước 4: chạy vòng lặp for, quét hết tất cả các giá trị của mảng A, thực hiện
    + Gán giá trị cho mảng kết quả B, dựa theo số phần tử nhỏ hơn hoặc bằng A[j]
    + In ra kết quả của mỗi lần gán
    + Giảm số phần tử nhỏ hơn hay bằng A[j] đi 1

Hàm findMax(arr)

Công dụng: tìm giá trị lớn nhất trong mảng arr. Hàm này dùng để khởi tạo số phần tử cho mảng trung gian C trong việc đếm số phần tử giống nhau có trong mảng arr

Bên cạnh đó, giải thuật Counting Sort còn sử dụng các hàm hỗ trợ trong việc hiện thực các chức năng và hiển thị giao diện. Các hàm này được lưu trong file CountingSort/CountingFunctions.js

Hàm Print(arr)

Công dụng: thiết lập các giá trị trong mảng arr vào một bảng, dùng để in ra

Hàm randomValue()

Công dụng: khởi tạo các giá trị ngẫu nhiên cho mảng và thực hiện giải thuật Counting Sort
Cách thức hoạt động:
o Bước 1: xóa tất cả dữ liệu đã in ra trước đó ở các khu vực
o Bước 2: yêu cầu người dùng nhập vào số phần tử, nếu không nhập, chương trình sẽ tự động thực hiện thuật giải với các giá trị mặc định
o Bước 3: khởi tạo mảng chứa dữ liệu và mảng kết quả với số phần tử người dùng đã nhập
o Bước 4: chạy vòng lặp for để thêm dữ liệu
o Bước 5: gán số phần tử của mảng trung gian C bằng giá trị cao nhất của a +1 và thực hiện giải thuật

Hàm defValue()

Công dụng: khởi tạo các giá trị như trong slide bài giảng và thực hiện giải thuật

Hàm printit()

Công dụng: sẽ thực thi giải thuật Quick Sort với dữ liệu do người dùng nhập vào và nhấn nút Print trong chương trình

d. Radix Sort

Mã nguồn của giải thuật Radix Sort nằm trong file RadixSort/RadixSort.htm, có các biến và hàm với công dụng như sau:

Hàm RadixSort(A,d)

Công dụng: sắp xếp mảng A theo cơ số d với giải thuật Radix Sort
Cách thức hoạt động:
o Bước 1: tạo một mảng chứa quá trình xử lí dữ liệu
o Bước 2: chạy vòng lặp for, thực hiện
    + Tạo mảng trung gian b có số phần tử bằng số phần tử của mảng A
    + Gọi hàm insertRadix(A,i) để chèn các giá trị của A tại vị trí i vào mảng b
    + Tạo một mảng tạm temp và dùng giải thuật sắp xếp hỗ trợ Counting Sort để sắp xếp temp
    + Sắp xếp lại mảng A với thứ tự của cơ số d đã được sắp xếp trong temp
o Bước 3: in ra quá trình xử lí dữ liệu
o Bước 4: trả về mảng A đã được sắp xếp

Hàm insertRadix(A,i)

Công dụng: chèn các giá trị của mảng A tại vị trí i vào trong mảng trung gian b

Hàm Sort(A,B,d)

Công dụng: sắp xếp lại mảng A theo cơ số d đã được sắp xếp trong mảng B
Cách thức hoạt động:
o Bước 1: tạo biến tạm temp, biến j chứa số phần tử của mảng kết quả B và mảng tạm arr có số phần tử bằng với mảng B
o Bước 2: chạy vòng lặp vô tận for, thực hiện:
    + Kiểm tra nếu đã thêm vào đủ số phần tử cho mảng kết quả arr thì thoát
    + Ngược lại, nếu thêm chưa đủ thì chạy thêm một vòng lặp for, quét tất cả các giá trị của A, nếu giá trị A[i] có cơ số d tại vị trí i và A[i] chưa được xét(khác null) thì thực hiện:
        - Thêm A[i] vào mảng kết quả b
        - Tăng số phần tử của mảng kết quả b lên 1
        - Đánh dấu giá trị A[i] đã được xét rồi, A[i] = null
        - Thực hiện vòng lặp mới để xét các giá trị khác(nếu còn) có cơ số d tại vị trí i
o Bước 3: trả về mảng kết quả arr đã được sắp xếp theo cơ số d

Bên cạnh đó, giải thuật Radix Sort còn sử dụng các hàm hỗ trợ trong việc hiện thực các chức năng và hiển thị giao diện. Các hàm này được lưu trong file RadixSort/RadixSortFunctions.js

Hàm printProcess(tableProcess)

Công dụng: thiết lập các giá trị trong mảng arr vào một bảng, dùng để in ra

Hàm Print(arr,k)

Công dụng: in các bảng dữ liệu trong các khu vực Array of beginning, Processing và Array after using Radix Sort. Hàm này sẽ kiểm tra để in các giá trị với cơ số k được tô màu

Hàm randomValue()

Công dụng: khởi tạo các giá trị ngẫu nhiên cho mảng và thực hiện giải thuật Radix Sort
Cách thức hoạt động:
o Bước 1: xóa tất cả dữ liệu đã in trước đó trong các khu vực
o Bước 2: yêu cầu người dùng nhập vào số phần tử, nếu không nhập, chương trình sẽ tự động thực hiện thuật giải với các giá trị mặc định
o Bước 3: khởi tạo mảng chứa dữ liệu với số phần tử đã nhập
o Bước 4: yêu cầu người dùng nhập vào chiều dài của các số, nếu không nhập, chương trình sẽ tự động thực hiện giải thuật với các giá trị mặc định
o Bước 5: khởi tạo các giá trị mặc định cho mảng dữ liệu với số phần tử và chiều dài người dùng đã nhập
o Bước 6: tạo mảng trung gian b và C cho giải thuật sắp xếp hỗ trợ Counting Sort
o Bước 7: thực hiện giải thuật Radix Sort và in ra kết quả

Hàm defValue()

Công dụng: khởi tạo các giá trị như trong slide bài giảng và thực hiện giải thuật

Hàm printit()

Công dụng: sẽ thực thi giải thuật Radix Sort với dữ liệu do người dùng nhập vào và nhấn nút Print trong chương trình

Hàm addValueRS(value)

Công dụng: được dùng để thêm dữ liệu vào mảng a từ một chuỗi chứa các giá trị số do người dùng nhập vào
Cách thức hoạt động:
o Bước 1: khởi tạo số phần tử k=0 và chuỗi rỗng str
o Bước 2: chạy vòng lặp for, xét duyệt từng kí tự cho đến hết chuỗi dữ liệu value, thực hiện
    + Nếu kí tự đang xét không phải là dấu phân cách giữa các số thì chuỗi str=str + kí tự này
    + Ngược lại, nếu là một trong những kí tự phân cách ("," ";" " "), thì kiểm tra xem chuỗi str có đúng là một giá trị số hay không?
    + Nếu str không phải là một giá trị số thì thông báo cho người dùng và hủy bỏ quá trình thêm dữ liệu
    + Ngược lại, str là một giá trị số, thì kiểm tra xem nó có phải là số đầu tiên được thêm vào hay không(root)?
        - Nếu đúng thì thêm vào gốc và tăng số phần tử của mảng lên thêm 1, k++
        - Nếu không phải là số đầu tiên thì kiểm tra xem nó có cùng chiều dài với số đầu tiên không ? Nếu thỏa thì thêm vào còn ngược lại thì thông báo cho người dùng biết giá trị không hợp lệ và huỷ bỏ quá trình thêm dữ liệu(tuy nhiên, ta có thể tác động để không hủy bỏ)
o Bước 3: thông báo cho người dùng biết quá trình thêm dữ liệu đã hoàn tất

Hàm addDataRS()

Công dụng: thêm dữ liệu do người dùng nhập vào thông qua hai dạng:
o Dạng 1: thêm vào mảng từ một chuỗi chứa các giá trị số
o Dạng 2: thêm vào mảng bằng lần lượt từng con số
Cách thức hoạt động:
o Bước 1: đưa vào biến data dữ liệu do người dùng nhập, thông qua dòng lệnh var data = document.data.array.value;o Bước 2: nếu chưa có dữ liệu, data='', thì yêu cầu người dùng phải nhập vào
o Bước 3: ngược lại, nếu đã có dữ liệu, thì kiểm tra xem người dùng muốn thêm dữ liệu vào theo dạng nào:
    + Nếu là dạng 1, thì trong data sẽ có chứa một trong những kí tự phân cách giữa các số, thì gọi hàm addValue(data);
    + Nếu là dạng 2, thì kiểm tra xem data có phải là một giá trị số hay không?
        - Nếu thỏa thì kiểm tra tiếp xem nó có phải là số đầu tiên được thêm vào hay không? Nếu là số đầu tiên thì thêm vào
        - Ngược lại, nếu chiều dài của nó bằng với số đầu tiên thì thêm vào hoặc thông báo cho người dùng biết giá trị không hợp lệ

Hàm numLength(num)

Công dụng: kiểm tra và trả về chiều dài của một giá trị số

e. Bucket Sort

Mã nguồn của giải thuật Bucket Sort nằm trong file BucketSort/BucketSort.htm, có các biến và hàm với công dụng như sau:

Hàm BucketSort(A)

Công dụng: sắp xếp mảng A theo giải thuật Bucket Sort (chỉ sắp xếp với các giá trị nhỏ hơn 1 và lớn hơn 0)
Cách thức hoạt động:
o Bước 1: tạo một mảng B chứa các liên kết có số phần tử bằng số phần tử của A và số k=0
o Bước 2: chạy vòng lặp for, quét hết tất cả các giá trị trong A và đưa chúng vào các danh sách của B
o Bước 3: gán A là một mảng mới, dùng để chứa giá trị kết quả
o Bước 4: chạy vòng lặp for, quét hết tất cả các danh sách trong mảng B, thực hiện:
+ Nếu tại i tồn tại một danh sách thì dùng giải thuật Insertion Sort để sắp xếp các số trong dnh sách này, bằng cách gọi hàm InsertionSort(B[i])
+ Nối danh sách các số đã được sắp xếp này vào mảng kết quả A, qua dòng lệnh A = A.concat(B[i]);
o Bước 5: in ra quá trình sắp xếp các danh sách
o Bước 6: trả về mảng kết quả A đã được sắp xếp theo giải thuật Bucket Sort

Hàm insertList(index,x)

Công dụng: chèn vào mảng trung gian B danh sách các số của mảng dữ liệu
Cách thức hoạt động:
o Bước 1: kiểm tra tại vị trí index của mảng B nếu chưa tồn tại một danh sách thì tạo một danh sách mới và thêm vào số đầu tiên của danh sách, x
o Bước 2: nếu tại vị trí index đã tồn tại một danh sách thì đưa giá trị x vào cuối danh sách này, qua dòng lệnh B[index].push(x);

Hàm InsertionSort(A)

Công dụng: sắp xếp mảng A theo giải thuật Insertion Sort

Bên cạnh đó, giải thuật Bucket Sort còn sử dụng các hàm hỗ trợ trong việc hiện thực các chức năng và hiển thị giao diện. Các hàm này được lưu trong file BucketSort/BucketFunctions.js

Hàm Print(arr,k)

Công dụng: in các bảng dữ liệu trong các khu vực Array of beginning, Processing và Array after using Radix Sort. Hàm này sẽ kiểm tra để in các giá trị theo đúng dạng .xx. Ví dụ: .12, .20, .102

Hàm randomValue()

Công dụng: khởi tạo các giá trị ngẫu nhiên cho mảng và thực hiện giải thuật Bucket Sort
Cách thức hoạt động:
o Bước 1: xóa tất cả các dữ liệu đã in ra trước đó trong các khu vực
o Bước 2: yêu cầu người dùng nhập vào số phần tử, nếu không nhập, chương trình sẽ tự động thực hiện thuật giải với các giá trị mặc định
o Bước 3: khởi tạo mảng chứa dữ liệu với số phần tử người dùng đã nhập và thêm vào mảng các giá trị thỏa điều kiện để thực hiện Bucke Sort(nhỏ hơn 1)
o Bước 4: thực hiện giải thuật Bucket Sort và in ra kết quả

Hàm defValue()

Công dụng: khởi tạo các giá trị như trong slide bài giảng và thực hiện giải thuật

Hàm printit()

Công dụng: sẽ thực thi giải thuật Heap Sort với dữ liệu do người dùng nhập vào và nhấn nút Print trong chương trình

Hàm addValueBS(value)

Công dụng: được dùng để thêm dữ liệu vào mảng a từ một chuỗi chứa các giá trị số do người dùng nhập vào. Ngoài ra, để đơn giản trong việc nhập liệu, hiệu ứng cho phép(bắt buộc) người dùng chỉ cần nhập vào các giá trị số nguyên mà không cần nhập số dạng 0.xx; sau đó chương trình sẽ tự động chuyển giá trị số nguyên do người dùng nhập vào thành số thập phân nhỏ hơn 1 và lớn hơn 0.
Cách thức hoạt động của hàm:
o Bước 1: khởi tạo số phần tử của mảng a là k=0, và tạo chuỗi rỗng str
o Bước 2: chạy vòng lặp for, xét duyệt từng kí tự của chuỗi dữ liệu value, thực hiện:
    + Nếu kí tự đang xét không phải là dấu phân cách giữa các số thì chuỗi str=str + kí tự này
    + Ngược lại, nếu là một trong những kí tự phân cách ("," ";" " "), thì kiểm tra xem chuỗi str có đúng là một giá trị số hay không?
    + Nếu str đúng là một giá trị số thì thêm vào mảng a theo đúng tính chất của giải thuật Bucket Sort và tăng số phần tử k lên 1, k++
    + Ngược lại, nếu str không phải là một giá trị số thì thông báo với người dùng giá trị này không hợp lệ, sau đó hủy bỏ quá trình thêm dữ liệu (tuy nhiên, ta vẫn có thể tác động để không hủy bỏ, xin xem chi tiết cụ thể trong mã nguồn)
o Bước 3: thông báo cho người dùng biết quá trình thêm dữ liệu hoàn tất. Người dùng phải nhấn nút Print để xử lí dữ liệu tùy theo giải thuật và in kết quả

Hàm addDataBS()

Công dụng: hàm được dùng để cho người sử dụng thêm dữ liệu vào theo 2 dạng. Ngoài ra, để đơn giản trong việc nhập liệu, hiệu ứng cho phép(bắt buộc) người dùng chỉ cần nhập vào các giá trị số nguyên mà không cần nhập số dạng 0.xx; sau đó chương trình sẽ tự động chuyển giá trị số nguyên do người dùng nhập vào thành số thập phân nhỏ hơn 1 và lớn hơn 0.
o Dạng 1: thêm dữ liệu vào mảng từ một chuỗi chứa các giá trị số, bằng cách gọi hàm addValue(data)
o Dạng 2: thêm dữ liệu vào mảng bằng lần lượt từng con số
Cách thức hoạt động của hàm:
o Bước 1: đưa vào biến data dữ liệu do người dùng nhập, thông qua dòng lệnh var data = document.data.array.value;o Bước 2: nếu chưa có dữ liệu, data='', thì yêu cầu người dùng phải nhập vào
o Bước 3: ngược lại, nếu đã có dữ liệu, thì kiểm tra xem người dùng muốn thêm dữ liệu vào theo dạng nào:
    + Nếu là dạng 1, thì trong data sẽ có chứa một trong những kí tự phân cách giữa các số, thì gọi hàm addValue(data);
    + Nếu là dạng 2, sẽ không có kí tự phân cách, thì thực hiện kiểm tra xem đó có phải là một giá trị số hay không
        - Nếu là một số hợp lệ thì thêm vào mảng theo đúng tính chất của giải thuật Bucket Sort
        - Ngược lại thì thông báo cho người dùng và yêu cầu một con số hợp lệ

Hàm numLength(num)

Công dụng: kiểm tra và trả về chiều dài của một giá trị số. Hàm này dùng để kiểm tra và in ra những giá trị số theo đúng định dạng .xx

Tài liệu này được biên soạn bởi Cao Phong All coded by Cao Phong