Rate this post

Thuật toán Selection Sort trong C++ là một giải thuật sắp xếp tăng dần dựa trên việc tìm và chọn phần tử nhỏ nhất trong mảng và sau đó chuyển nó đến vị trí đầu tiên. Giải thuật này lặp qua mảng nhiều lần, mỗi lần tìm phần tử nhỏ nhất và chuyển nó đến vị trí đầu tiên.

Giới thiệu về thuật toán Selection Sort

Thuật toán Selection Sort là một thuật toán sắp xếp đơn giản và hiệu quả trong việc sắp xếp các phần tử trong một mảng. Thuật toán này hoạt động bằng cách tìm kiếm phần tử nhỏ nhất trong mảng và đưa nó về vị trí đầu tiên. Sau đó, tiếp tục tìm kiếm phần tử nhỏ nhất trong các phần tử còn lại và đưa nó về vị trí tiếp theo. Quá trình này được lặp lại cho đến khi tất cả các phần tử trong mảng được sắp xếp theo thứ tự tăng dần.

Cách hoạt động của thuật toán Selection Sort như sau:

  1. Tìm phần tử nhỏ nhất trong mảng chưa được sắp xếp.
  2. Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên trong mảng chưa được sắp xếp.
  3. Tiếp tục tìm phần tử nhỏ nhất trong các phần tử còn lại và hoán đổi với phần tử tiếp theo.
  4. Lặp lại quá trình trên cho đến khi tất cả các phần tử trong mảng được sắp xếp.

Thuật toán Selection Sort có độ phức tạp thời gian là O(n^2), trong đó n là số lượng phần tử trong mảng. Mặc dù có độ phức tạp cao hơn một số thuật toán sắp xếp khác như Quick Sort hay Merge Sort, Selection Sort vẫn được sử dụng trong các trường hợp đơn giản hoặc khi số lượng phần tử nhỏ.

Thuật toán Selection Sort có ưu điểm là dễ hiểu, dễ cài đặt và không đòi hỏi bộ nhớ phụ. Tuy nhiên, điểm yếu của thuật toán này là tốc độ chậm khi xử lý một số lượng lớn phần tử và không thể tối ưu hóa.

Với cách hoạt động đơn giản và dễ cài đặt, thuật toán Selection Sort thường được sử dụng trong các ví dụ giảng dạy và trong các trường hợp cần sắp xếp một số lượng phần tử nhỏ.

Ví dụ về mã code của thuật toán Selection Sort trong C++ như sau:

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
   int i, j, minIndex, temp;
   for (i = 0; i < n-1; i++) {
      minIndex = i;
      for (j = i+1; j < n; j++)
         if (arr[j] < arr[minIndex])
            minIndex = j;
      temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
   }
}

int main() {
   int arr[] = {64, 25, 12, 22, 11};
   int n = sizeof(arr)/sizeof(arr[0]);
   selectionSort(arr, n);
   cout << "Sorted array: \n";
   for (int i=0; i < n; i++)
      cout << arr[i] << " ";
   return 0;
}

Giải thích đoạn code trên

Đoạn code trên là một ví dụ về thuật toán Selection Sort trong ngôn ngữ lập trình C++.

Ở đoạn code này, ta có một mảng arr với n phần tử. Chúng ta sẽ lặp qua mảng này từ đầu đến cuối. Trong mỗi lần lặp, chúng ta sẽ tìm phần tử nhỏ nhất trong mảng và đặt nó vào vị trí đầu tiên. Sau đó, chúng ta sẽ di chuyển con trỏ đến vị trí tiếp theo trong mảng và lặp lại quá trình tìm và hoán vị cho đến khi mảng được sắp xếp hoàn toàn.

Thứ tự của phần tử trong mảng sẽ thay đổi sau mỗi lần lặp, đảm bảo rằng phần tử nhỏ nhất trong mảng luôn được đặt vào vị trí đầu tiên mỗi lần. Khi quá trình lặp hoàn tất, mảng sẽ được sắp xếp từ nhỏ đến lớn.

Cách hoạt động của thuật toán Selection Sort

Thuật toán Selection Sort hoạt động theo các bước sau:

  1. Bước 1: Chọn phần tử nhỏ nhất
    • Tìm phần tử nhỏ nhất trong mảng chưa được sắp xếp.
    • Gán phần tử nhỏ nhất này vào vị trí đầu tiên của mảng chưa được sắp xếp.
  2. Bước 2: Hoán đổi và tìm phần tử nhỏ nhất tiếp theo
    • Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của mảng chưa được sắp xếp.
    • Tiếp tục tìm phần tử nhỏ nhất trong các phần tử còn lại của mảng chưa được sắp xếp.
    • Gán phần tử nhỏ nhất này vào vị trí tiếp theo trong mảng chưa được sắp xếp.
  3. Bước 3: Lặp lại cho đến khi mảng được sắp xếp hoàn chỉnh
    • Lặp lại bước 2 cho đến khi tất cả các phần tử trong mảng được sắp xếp.

Quá trình này được lặp lại cho tất cả các phần tử trong mảng. Khi mỗi lần lặp, phần tử nhỏ nhất được tìm ra và đưa vào vị trí chính xác của nó. Điều này dẫn đến việc mảng được sắp xếp theo thứ tự tăng dần từ trái sang phải.

Lưu ý rằng thuật toán Selection Sort có thể hoạt động theo cách ngược lại, tức là tìm phần tử lớn nhất và đưa nó vào vị trí cuối cùng của mảng chưa được sắp xếp. Tuy nhiên, cách hoạt động chung của thuật toán vẫn giữ nguyên.

Độ phức tạp của selection sort

Độ phức tạp của thuật toán Selection Sort là O(n^2), trong đó n là số lượng phần tử trong mảng cần sắp xếp.

Vì thuật toán Selection Sort có hai vòng lặp lồng nhau, nên độ phức tạp của nó là bình phương số lượng phần tử. Tuy nhiên, trong mọi trường hợp, số lần lặp của thuật toán Selection Sort vẫn là một hằng số so với kích thước mảng. Điều này là do thuật toán luôn tìm phần tử nhỏ nhất và hoán đổi nó vào đúng vị trí, bất kể mảng đã được sắp xếp trước đó hay chưa.

Vì vậy, dù độ phức tạp của Selection Sort là O(n^2), thuật toán này thường được sử dụng cho các mảng có kích thước nhỏ hoặc khi hiệu suất không phải là yếu tố quan trọng. Đối với các mảng lớn, thuật toán sắp xếp khác như Quick Sort hoặc Merge Sort có độ phức tạp thấp hơn có thể được sử dụng để tăng hiệu suất.

Xem thêm Gnome Sort là gì ?

Các biến thể của Selection sort

Selection Sort có một số biến thể như:

  • Selection Sort đơn giản: biến thể này sắp xếp mảng bằng cách tìm vị trí của giá trị nhỏ nhất và hoán đổi nó với giá trị đầu tiên.
  • Selection Sort với đánh dấu: biến thể này sắp xếp mảng bằng cách sử dụng một mảng đánh dấu để xác định các phần tử đã được sắp xếp hoặc chưa.

Các biến thể trên cải tiến hoặc giảm thiểu độ phức tạp tối ưu hoặc thời gian chạy của thuật toán, nhưng vẫn giữ nguyên các bước cơ bản của Selection Sort.

Ưu điểm và nhược điểm của thuật toán Selection Sort

Ưu điểm của thuật toán Selection Sort:

  • Đơn giản và dễ hiểu: Thuật toán Selection Sort rất dễ hiểu và cài đặt, không yêu cầu nhiều kiến thức phức tạp.
  • Không sử dụng thêm không gian bộ nhớ: Thuật toán Selection Sort hoạt động trực tiếp trên mảng ban đầu, không cần sử dụng mảng phụ hay không gian bộ nhớ tạm thời khác.

Nhược điểm của thuật toán Selection Sort:

  • Độ phức tạp thời gian lớn: Thuật toán Selection Sort có độ phức tạp thời gian là O(n^2), tức là tăng theo bình phương số lượng phần tử của mảng. Điều này khiến thuật toán trở nên không hiệu quả cho các mảng lớn.
  • Không ổn định: Thuật toán Selection Sort không đảm bảo tính ổn định. Điều này có nghĩa là nếu có hai phần tử bằng nhau, thì thứ tự của chúng có thể bị đảo ngược sau khi sắp xếp.
  • Không phù hợp với dữ liệu gần như đã sắp xếp: Thuật toán Selection Sort sẽ thực hiện nhiều phép hoán đổi dữ liệu ngay cả khi dữ liệu gần như đã sắp xếp. Điều này làm cho thuật toán không hiệu quả trong trường hợp này.

Tóm lại, thuật toán Selection Sort là một thuật toán đơn giản và dễ hiểu, nhưng có độ phức tạp thời gian lớn và không ổn định. Do đó, nó thường được sử dụng trong các trường hợp dữ liệu nhỏ hoặc khi không có yêu cầu về hiệu suất cao. Trong các trường hợp khác, các thuật toán sắp xếp khác như Quick Sort hoặc Merge Sort thường được ưu tiên.

Xem thêm bubble sort trong c++

So sánh thuật toán Selection Sort với các thuật toán sắp xếp khác

So sánh thuật toán Selection Sort với các thuật toán sắp xếp khác có thể dựa trên các yếu tố như độ phức tạp thời gian, tính ổn định, sử dụng bộ nhớ và hiệu suất trong các trường hợp dữ liệu khác nhau. Dưới đây là một số so sánh phổ biến:

  1. Selection Sort vs Bubble Sort:
  • Độ phức tạp thời gian: Cả hai thuật toán đều có độ phức tạp O(n^2), nhưng Selection Sort thường hiệu quả hơn do ít phép so sánh hơn.
  • Tính ổn định: Bubble Sort là thuật toán ổn định, trong khi Selection Sort không ổn định.
  • Hiệu suất: Selection Sort thường hiệu quả hơn Bubble Sort do ít phép so sánh và hoán đổi hơn.
  1. Selection Sort vs Insertion Sort:
  • Độ phức tạp thời gian: Cả hai thuật toán đều có độ phức tạp O(n^2), nhưng Insertion Sort có thể hiệu quả hơn trong các trường hợp dữ liệu gần như đã sắp xếp.
  • Tính ổn định: Cả hai thuật toán đều không ổn định.
  • Hiệu suất: Insertion Sort thường hiệu quả hơn Selection Sort trong các trường hợp dữ liệu gần như đã sắp xếp.
  1. Selection Sort vs Quick Sort:
  • Độ phức tạp thời gian: Selection Sort có độ phức tạp O(n^2), trong khi Quick Sort có độ phức tạp trung bình O(nlogn). Quick Sort thường nhanh hơn nhiều cho các mảng lớn.
  • Tính ổn định: Selection Sort không ổn định, trong khi Quick Sort có thể được cài đặt để làm việc ổn định.
  • Sử dụng bộ nhớ: Selection Sort không cần bộ nhớ phụ, trong khi Quick Sort sử dụng bộ nhớ phụ trong quá trình phân hoạch.
  • Hiệu suất: Quick Sort thường hiệu quả hơn Selection Sort trong hầu hết các trường hợp.

Tuy nhiên, việc chọn thuật toán sắp xếp phù hợp còn phụ thuộc vào các yêu cầu cụ thể của bài toán và loại dữ liệu đầu vào. Một thuật toán có thể tốt hơn trong một trường hợp cụ thể nhưng không hiệu quả trong trường hợp khác. Do đó, việc lựa chọn thuật toán sắp xếp phụ thuộc vào các yếu tố khác nhau và nghiên cứu kỹ về từng thuật toán là cần thiết.

Xem thêm Thuật toán Shell Sort là gì ?

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now