Sắp xếp chọn trong Scratch

Sắp xếp là một trong những dạng bài tập thường xuyển được xuất hiện trong các đề thi. Sắp xếp là quá trình xử lý danh sách các đối tượng, phần tử được đặt theo một trình tự nhất định. Có 2 loại sắp xếp là sắp xếp theo chiều tăng dần và sắp xếp theo chiều giảm dần. Giải thuật sắp xếp có khá nhiều giải thuật, tuy nhiên, trong bài học này, thầy sẽ giới thiệu cho các em về giải thuật sắp xếp chọn (Selection Sort) được cài đặt trong Scratch nha. Chúng ta cùng bắt đầu thôi nào!

Nội dung

Ý tưởng giải thuật
Giả mã cho giải thuật
Chương trình minh họa trong Scratch
Xem thêm các video lập trình Scratch

Ý tưởng giải thuật

Xét bài toán sắp xếp sau: Cho dãy khóa là các số nguyên a₁, a₂, …, a_n. Yêu cầu, sắp xếp dãy khóa theo chiều tăng dần các giá trị của phần tử theo giải thuật sắp xếp chọn (selection Sort).

Đầu tiên, ta sẽ chọn khóa có giá trị nhỏ nhất và đổi chỗ vị trí khóa đó với phần tử đầu tiên trong dãy là a[1]. Khi đó, a[i] là khóa có giá trị nhỏ nhất trong n phần tử.
Lần thứ 2, ta chọn khóa có giá trị nhỏ nhất trong (n – 1) khóa còn lại từ a[2], a[3], …, a[n], và đổi chỗ với vị trí của khóa a[2].
…
Ở lần thứ i, ta chọn trong dãy từ a[i] đến a[n] khóa nhỏ nhất và đổi chỗ cho khóa a[i].
Cứ như vậy cho đến khi dãy khó chỉ còn một phần tử.

Giả mã cho giải thuật

Đầu vào: dãy khóa a, số lượng phần tử n.
Đầu ra: không có.

{Hàm này nhận vào dãy khóa a và số lượng phần tử n thông qua đối số, thực hiện sắp xếp tăng dần dãy khóa theo giải thuật sắp xếp chọn}


Procedure SelectionSort(a, n)
	For i:=1 to n-1 do
		Begin
			{1.Tìm phần tử nhỏ nhất ở vị trí k.}
				+) k:=i;
				+) For j:=i+1 to n do
					If a[j] < a[k] then k:=j
			{2. Đổi chỗ phần tử nhỏ nhất ở vị trí k cho vị trí i}
				If k != i then a[k] <=> a[i]
		End
Return