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à 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 chưa 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 sắp xếp và hoán đổi 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 được 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 bởi một yếu tố sang 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 ² ), trong đó n là số lượng mục.

Lựa chọn sắp xếp hoạt động như thế nào?

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

Đối với vị trí đầu tiên trong danh sách được sắp xếp, toàn bộ danh sách được quét liên tục. Vị trí đầu tiên nơi 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 10, giá trị tối thiểu trong danh sách, xuất hiện ở vị trí đầu tiên của danh sách được sắp xếp.

Đối với vị trí thứ hai, nơi 33 đang cư trú, 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 trao đổi những 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.

Quá 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à mô tả bằng hình ảnh của 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 sắp xếp 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

Được cập nhật: hôm qua lúc 3:11:28 | Lượt xem: 510