Home > Algorithm > Algorithm Basic – Thuật toán sắp xếp chọn – Selection Sort

Algorithm Basic – Thuật toán sắp xếp chọn – Selection Sort

Sắp xếp chọn là phương pháp sắp xếp đơn giản nhất.

Giả sử có mảng n phần tử từ a[1] đến a[n]

1. Giải thuật :

– Đầu tiên chọn phần tử có khóa nhỏ nhất trong n phần tử từ a[1] đến a[n] và hoán vị nó với a[1]

– Chọn phần tử có khóa nhỏ nhất trong n-1 phần tử từ a[2] đến a[nư và hoán vị nó với a[2]

– Tổng quát ở bước thứ i, chọn phần tử có khóa nhỏ nhất trong n-i+1 phần tử từ a[i] đến a[n] và hoán vị nó với a[i]

– Sau n-1 bước này thì được kết quả là mảng đã sắp xếp

2. Cài đặt :

public static int[] SelectionSort(int[] array)
 {
     int Min;
     int temp;
     for (int i = 0; i < array.Length - 1; i++)
     {
         Min = i;
         for (int j = i + 1; j < array.Length; j++)
         {
             if (array[j]<array[Min])
             {
                 Min = j;
             }
          }
          if (Min!=i)
          {
              temp = array[Min];
              array[Min] = array[i];
              array[i] = temp;
           }
       }
       return array;
   }

3. Đánh giá độ phức tạp thuật toán :

  • Tốt nhất – O(n^2)
  • Trung bình – O(n^2)
  • Xấu nhất – O(n^2)
  • Tính ổn định – phụ thuộc vào việc thực hiện
Advertisements
Categories: Algorithm
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: