Cấu trúc dữ liệu và lựa chọn thuật toán Sắp xếp lựa chọn

Sắp xếp lựa chọn là một thuật toán sắp xếp đơn giản. Thuật toán sắp xếp này là một thuật toán dựa trên so sánh tại chỗ trong đó danh sách được chia thành hai phần, phần được sắp xếp ở đầu bên trái và phần chưa được sắp xếp ở đầu bên phải. Ban đầu, phần được sắp xếp trống và phần không được sắp xếp là toàn bộ danh sách.

Phần tử nhỏ nhất được chọn từ mảng chưa được sắp xếp và đổi chỗ với phần tử ngoài cùng bên trái và phần tử đó trở thành một phần của mảng đã sắp xếp. Quá trình này tiếp tục di chuyển ranh giới mảng chưa được sắp xếp theo một phần tử sang bên phải.

Thuật toán này không phù hợp với các tập dữ liệu lớn vì độ phức tạp trung bình và trường hợp xấu nhất của nó là Ο (n 2 ), trong đón là số lượng mặt hàng.

Cách phân loại lựa chọn hoạt động?

Hãy xem xét mảng được mô tả sau đây làm ví dụ.

Đối với vị trí đầu tiên trong danh sách đã sắp xếp, toàn bộ danh sách được quét tuần tự. Vị trí đầu tiên mà 14 được lưu trữ hiện tại, chúng tôi tìm kiếm toàn bộ danh sách và thấy rằng 10 là giá trị thấp nhất.

Vì vậy, chúng tôi thay thế 14 bằng 10. Sau một lần lặp lại 10, giá trị này xảy ra là giá trị nhỏ nhất trong danh sách, xuất hiện ở vị trí đầu tiên của danh sách đã sắp xếp.

Đối với vị trí thứ hai, nơi có 33, chúng tôi bắt đầu quét phần còn lại của danh sách theo cách tuyến tính.

Chúng tôi thấy rằng 14 là giá trị thấp thứ hai trong danh sách và nó sẽ xuất hiện ở vị trí thứ hai. Chúng tôi hoán đổi các giá trị này.

Sau hai lần lặp, hai giá trị nhỏ nhất được định vị ở đầu theo cách được sắp xếp.

Quy trình tương tự được áp dụng cho phần còn lại của các mục trong mảng.

Sau đây là hình ảnh mô tả toàn bộ quá trình phân loại -

Bây giờ, chúng ta hãy tìm hiểu một số khía cạnh lập trình của phân loại lựa chọn.

Thuật toán

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

Mã giả

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

Để biết về triển khai sắp xếp lựa chọn trong ngôn ngữ lập trình C, vui lòng nhấp vào đây .