Sorting Algorithm Visualisations (Minh họa thuật toán sắp xếp)

Sortvis.ord - Sorting Algorithm VisualisationTrang sortvis.org (sorting algorithm visualisation) giới thiệu một phương pháp minh họa các thuật toán sắp xếp khá độc đáo. Mỗi thuật toán được biểu diễn gần giống dạng đồ thị, không hiệu ứng chuyển động, và người xem có thể dễ dàng nắm bắt được đặc trưng của mỗi thuật toán. Tôi cũng muốn giới thiệu với các bạn phương pháp này thông qua Canvas của HTML5.

Điểm cơ bản của cách minh họa này là sử dụng các đường để đại diện cho một giá trị trong mảng cần sắp xếp với màu sắc đậm/nhạt tùy theo độ lớn. Quá trình sắp xếp đi từ trái qua phải và cuối cùng ta được một dãy các màu được xếp theo mức độ đậm/nhạt của chúng.

Cách minh họa này cũng tương tự như việc bạn liệt kê mảng theo từng bước (trạng thái) sắp xếp. Sau đó nối mỗi phần tử của trạng thái này với vị trí của nó ở trạng thái trước đó, bởi vì ta phân biệt giá trị theo màu sắc nên các con số là không cần thiết.

Trong Canvas, tôi thực hiện một ví dụ nhỏ minh họa lại cách làm này theo hướng dễ hiểu và đơn giản hơn. Ví dụ này khá đơn giản nên tôi bỏ qua phần giải thích.

Xem Demo.

Minh họa hai thuật toán.

Bubble Sort:

Bubble Sort Visualisation

Interchange Sort:

Interchange Sort Visualisation

Source code:

<html>
<head>
  <script>
	function Node(value,preX,preY){
		this.value = value;
		this.preX = preX;
		this.preY = preY;
		var c = 255-value*2;
		this.color = "rgba("+c+","+c+","+c+",255)";
	}

	var ARRAY_SIZE = 10;
	var DISTANCE_X = 40;
	var DISTANCE_Y = 60;
	var _canvas;
	var _context;

	function drawNode(node,cx,cy){

		_context.beginPath();
		_context.fillStyle = node.color;
		_context.arc(cx, cy, 10, 0, Math.PI * 2, true);
		_context.closePath();
		_context.fill();
		_context.fillStyle = "white";
		_context.fillText(node.value,cx-6,cy+4);
	}
	function drawLine(node,x2,y2){

		_context.strokeStyle = node.color;
		_context.beginPath();
		_context.moveTo(node.preX,node.preY);
		_context.lineTo(x2,y2);
		_context.closePath();
		_context.stroke();
	}
	function draw(array,step) {
		var x;
		var y;
		var color;
		for (var i=0; i < ARRAY_SIZE; i++) {
			x = (step+1)*DISTANCE_X+10;
			y = (i+1)*DISTANCE_Y/2;
			if(step>0)
				drawLine(array[i],x,y);
			drawNode(array[i],x,y);
			array[i].preX=x+9;
			array[i].preY=y;
		}
	}
	function interchangeSort(arr){

		draw(arr,0);
		for (var i = 0; i < ARRAY_SIZE-1; i++) {

			for (var j = i+1; j < ARRAY_SIZE; j++) {
				  if (arr[i].value > arr[j].value) {
						var tmp = arr[i];
						arr[i] = arr[j];
						arr[j] = tmp;
				 }
			}
			if(i>0)
				draw(arr,i);
		}

	}
	function bubbleSort(arr) {
		var swapped = true;
		var i = 0;
		draw(arr,0);
		while (swapped) {
				swapped = false;
			for (var j = 0; j < ARRAY_SIZE-i-1; j++) {
				  if (arr[j].value > arr[j + 1].value) {
						var tmp = arr[j];
						arr[j] = arr[j + 1];
						arr[j + 1] = tmp;
						swapped = true;
				 }
			}
			if(i>0)
				draw(arr,i);
			i++;
		}
	}
	function toString(array){
		var s = "[";
		for (var i=0; i < ARRAY_SIZE; i++) {
			s += array[i].value+", ";
		}
		return s+"]";
	}
	function init(){
		var paddleWidth = 100;
		var paddleHeight = 20;
		_canvas = document.getElementById("canvas");
		_context = _canvas.getContext("2d");
		_context.font = "12px Arial";
		_context.lineWidth = 5;

		var output = document.getElementById("output");

		var numbers = new Array(ARRAY_SIZE);
		for (var i=0; i < ARRAY_SIZE; i++) {
			numbers[i] = new Node(Math.floor(Math.random()*90+10),0,0);
		}
		var s ="Before: " + toString(numbers);

		//bubbleSort(numbers);
		interchangeSort(numbers);
		s += "<br/>After:";
		s += toString(numbers);
		output.innerHTML = s;
	}

	window.onload = function(){
		init();
	}
  </script>
</head>
<body>
<h1>Sorting Visualizations:</h1>
<hr/>
<canvas id="canvas" width="450px" height="350px" style="border: 1px solid"></canvas>
<div id="output"></div>
</body>
</html>

YinYang’s Blog

Advertisements

2 thoughts on “Sorting Algorithm Visualisations (Minh họa thuật toán sắp xếp)

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s