Bài toán nhập vào mảng rồi sắp xếp c++ năm 2024
Trong bài viết này, codehow sẽ giới thiệu đến các bạn thuật toán sắp xếp chèn (Insertion Sort) trong C / C++. Về cơ bản thì thuật toán này sắp xếp nhanh hơn và tối ưu hơn thuật toán sắp xếp nổi bọt (Bubble Sort). Mình sẽ giải thích khái niệm sắp xếp chèn là gì? Cách nó hoạt động ra sao? Sau đó sẽ đưa ra giải thuật kèm theo ví dụ cụ thể để các bạn tham khảo nhé. Sắp xếp chèn là gì? Hoạt động như thế nàoThuật toán sắp xếp chèn (Insertion Sort) hoạt động dựa trên thuật toán sắp xếp nổi bọt (Bubble Sort). Nó thực hiện sắp xếp bằng cách duyệt từng phần tử trong mảng và chèn phần tử đó vào đúng trong mảng con. Nói một cách dễ hiểu, thuật toán sẽ duyệt từng phần tử trong mảng, sau đó so sánh và chèn vào mảng còn sao cho đúng thứ tự. Như các bạn thấy ở hình trên, đầu tiên nó so sánh cặp 4 và 3, bởi vì 3 nhỏ hơn 4 nên nó chèn vào trước số 4. Tiếp tục cặp 4 và 2, vì 2 nhỏ hơn 4 và 3 nên nó chèn vào trước 3, cứ như vậy cho đến khi hết mảng. Về cơ bản thì nó sẽ nhanh hơn thuật toán sắp xếp nổi bọt, tuy nhiên vẫn chưa được tối ưu vì phải duyệt hết tất cả các phần tử trong mảng. Nếu các bạn mới bắt đầu học lập trình thì nên tìm hiểu qua thuật toán này, bởi nó cơ bản và độ phức tạp không cao. Các bạn có thể tìm hiểu thêm các thuật toán sắp xếp khác tối ưu hơn ở các bài viết sau của mình nhé. Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++Đối với thuật toán sắp xếp chèn (Insertion Sort) trong C / C++, chúng ta không cần sử dụng hàm void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { }
}Giải thích thuật toán:
Bây giờ mình sẽ thực hiện một ví dụ sử dụng thuật toán sắp xếp chèn (Insertion Sort) trong C / C++. Đề bài: Viết chương trình sắp xếp các phần tử trong mảng được nhập bởi người dùng. Số lương phần tử trong mảng không được nhỏ hơn 0, nếu nhỏ hơn thì yêu cầu nhập lại. Sử dụng thuật toán sắp xếp chèn để sắp xếp các phần tử. Gợi ý:
Dưới đây là hai chương trình mình đã viết bằng ngôn ngữ C và C++, các bạn có thể tham khảo nhé. Chương trình C: include
include void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { }
}
void printArr(int arr[], int N)
{
int i;
for (i = 0; i < N; i++)
{ }
}
int main(void) {
int n; }Kết quả: Chương trình C++: include using namespace std; void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { }
}
void printArr(int arr[], int N)
{
int i;
for (i = 0; i < N; i++)
{ }
}
int main(void) {
int n; }Kết quả: Như vậy là chúng ta đã cùng nhau tìm hiểu về thuật toán sắp xếp chèn (Insertion Sort) trong C / C++. Ở bài tiếp theo mình sẽ giới thiệu đến các bạn thuật toán sắp xếp chọn (Selection Sort) trong C / C++, các bạn chú ý theo dõi nhé !!! |