Tự học C/C++ | Sắp xếp một mảng bằng cách sử dụng sắp xếp lựa chọn

1. Một trường hợp để sắp xếp

Sắp xếp mảng là quá trình sắp xếp tất cả các phần tử trong mảng theo một thứ tự cụ thể. Có nhiều trường hợp khác nhau trong đó việc sắp xếp một mảng có thể hữu ích. Ví dụ: chương trình email của bạn thường hiển thị các email theo thứ tự thời gian nhận được, vì các email gần đây hơn thường được coi là có liên quan hơn. Khi bạn truy cập danh sách liên hệ của mình, các tên thường được xếp theo thứ tự bảng chữ cái, vì theo cách đó, bạn sẽ dễ dàng tìm thấy tên mà bạn đang tìm kiếm hơn. Cả hai bài thuyết trình này đều liên quan đến việc sắp xếp dữ liệu trước khi thuyết trình.

Sắp xếp một mảng có thể giúp tìm kiếm một mảng hiệu quả hơn, không chỉ cho con người mà còn cho cả máy tính. Ví dụ, hãy xem xét trường hợp chúng ta muốn biết liệu một cái tên có xuất hiện trong danh sách tên hay không. Để xem liệu một tên có trong danh sách hay không, chúng ta phải kiểm tra mọi phần tử trong mảng để xem tên đó có xuất hiện hay không. Đối với một mảng có nhiều phần tử, việc tìm kiếm qua tất cả chúng có thể tốn kém.

Tuy nhiên, bây giờ giả sử mảng tên của chúng ta được sắp xếp theo thứ tự bảng chữ cái. Trong trường hợp này, chúng ta chỉ cần tìm kiếm đến điểm mà chúng ta gặp một tên lớn hơn theo thứ tự bảng chữ cái tên mà chúng ta đang tìm kiếm. Tại thời điểm đó, nếu chúng ta chưa tìm thấy tên, chúng tôi biết nó không tồn tại trong phần còn lại của mảng, vì tất cả các tên chúng tôi chưa xem xét trong mảng được đảm bảo sẽ lớn hơn theo thứ tự bảng chữ cái!

Nó chỉ ra rằng có những thuật toán thậm chí còn tốt hơn để tìm kiếm các mảng được sắp xếp. Sử dụng một thuật toán đơn giản, chúng ta có thể tìm kiếm một mảng đã sắp xếp có chứa 1.000.000 phần tử chỉ bằng 20 phép so sánh! Tất nhiên, nhược điểm là việc sắp xếp một mảng tương đối tốn kém và thường không đáng để sắp xếp một mảng để giúp tìm kiếm nhanh chóng trừ khi bạn định tìm kiếm nó nhiều lần.

Trong một số trường hợp, việc sắp xếp một mảng có thể khiến việc tìm kiếm không cần thiết. Hãy xem xét một ví dụ khác mà chúng ta muốn tìm điểm kiểm tra tốt nhất. Nếu mảng không được sắp xếp, chúng ta phải xem xét từng phần tử trong mảng để tìm điểm kiểm tra lớn nhất. Nếu danh sách được sắp xếp, điểm kiểm tra tốt nhất sẽ ở vị trí đầu tiên hoặc cuối cùng (tùy thuộc vào việc chúng ta sắp xếp theo thứ tự tăng dần hay giảm dần), vì vậy chúng ta không cần phải tìm kiếm gì cả!

2. Cách sắp xếp hoạt động

Việc sắp xếp thường được thực hiện bằng cách so sánh nhiều lần các cặp phần tử mảng và hoán đổi chúng nếu chúng đáp ứng một số tiêu chí xác định trước. Thứ tự mà các phần tử này được so sánh khác nhau tùy thuộc vào thuật toán sắp xếp nào được sử dụng. Tiêu chí phụ thuộc vào cách danh sách sẽ được sắp xếp (ví dụ: theo thứ tự tăng dần hoặc giảm dần).

Để hoán đổi hai phần tử, chúng ta có thể sử dụng hàm std :: swap () từ thư viện chuẩn C ++, được định nghĩa trong tiêu đề thuật toán. Vì lý do hiệu quả, std :: swap () đã được chuyển đến tiêu đề tiện ích trong C ++ 11.

/*
Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
@author cafedevn
Contact: cafedevn@gmail.com
Fanpage: https://www.facebook.com/cafedevn
Group: https://www.facebook.com/groups/cafedev.vn/
Instagram: https://instagram.com/cafedevn
Twitter: https://twitter.com/CafedeVn
Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
Pinterest: https://www.pinterest.com/cafedevvn/
YouTube: https://www.youtube.com/channel/UCE7zpY_SlHGEgo67pHxqIoA/
*/

#include <algorithm> // for std::swap, use <utility> instead if C++11
#include <iostream>
 
int main()
{
    int x{ 2 };
    int y{ 4 };
    std::cout << "Before swap: x = " << x << ", y = " << y << '\n';
    std::swap(x, y); // swap the values of x and y
    std::cout << "After swap:  x = " << x << ", y = " << y << '\n';
}

Kết quả

Before swap: x = 2, y = 4
After swap:  x = 4, y = 2

Lưu ý rằng sau khi hoán đổi, giá trị của x và y đã được hoán đổi cho nhau!

3. Sắp xếp lựa chọn(Selection sort)

Có nhiều cách để sắp xếp một mảng. Kiểu lựa chọn có lẽ là kiểu dễ hiểu nhất, khiến nó trở thành một ứng cử viên tốt cho việc giảng dạy mặc dù nó là một trong những kiểu chậm hơn.

Sắp xếp lựa chọn thực hiện các bước sau để sắp xếp một mảng từ nhỏ nhất đến lớn nhất:

1) Bắt đầu từ chỉ số mảng 0, tìm kiếm toàn bộ mảng để tìm giá trị nhỏ nhất

2) Hoán đổi giá trị nhỏ nhất được tìm thấy trong mảng với giá trị ở chỉ số 0

3) Lặp lại bước 1 & 2 bắt đầu từ chỉ mục tiếp theo

Nói cách khác, chúng ta sẽ tìm phần tử nhỏ nhất trong mảng và hoán đổi nó vào vị trí đầu tiên. Sau đó, chúng ta sẽ tìm phần tử nhỏ nhất tiếp theo và hoán đổi nó vào vị trí thứ hai. Quá trình này sẽ được lặp lại cho đến khi chúng tôi sử dụng hết phần tử.

Đây là một ví dụ về thuật toán này hoạt động trên 5 phần tử. Hãy bắt đầu với một mảng mẫu:

{30, 50, 20, 10, 40}

Đầu tiên, chúng tôi tìm phần tử nhỏ nhất, bắt đầu từ chỉ số 0:

{30, 50, 20, 10, 40}

Sau đó, chúng tôi hoán đổi phần tử này với phần tử ở chỉ mục 0:

{10, 50, 20, 30, 40}

Bây giờ phần tử đầu tiên đã được sắp xếp, chúng ta có thể bỏ qua nó. Bây giờ, chúng ta tìm phần tử nhỏ nhất, bắt đầu từ chỉ mục 1:

{10, 50, 20, 30, 40}

Và hoán đổi nó với phần tử trong chỉ mục 1:

{10, 20, 50, 30, 40}

Bây giờ chúng ta có thể bỏ qua hai yếu tố đầu tiên. Tìm phần tử nhỏ nhất bắt đầu từ chỉ số 2:

{10, 20, 50, 30, 40}

Và hoán đổi nó với phần tử trong chỉ mục 2:

{10, 20, 30, 50, 40}

Tìm phần tử nhỏ nhất bắt đầu từ chỉ số 3:

{10, 20, 30, 50, 40}

Và hoán đổi nó với phần tử trong chỉ mục 3:

{10, 20, 30, 40, 50}

Cuối cùng, tìm phần tử nhỏ nhất bắt đầu từ chỉ mục 4:

{10, 20, 30, 40, 50}

Và hoán đổi nó với phần tử trong chỉ mục 4 (không làm gì cả):

{10, 20, 30, 40 50}

Làm xong!

{10, 20, 30, 40, 50}

Lưu ý rằng phép so sánh cuối cùng sẽ luôn ở với chính nó (là thừa), vì vậy chúng ta thực sự có thể dừng 1 phần tử trước khi kết thúc mảng.

4. Sắp xếp lựa chọn trong C ++

Đây là cách thuật toán này được triển khai trong C ++:

/*
Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
@author cafedevn
Contact: cafedevn@gmail.com
Fanpage: https://www.facebook.com/cafedevn
Group: https://www.facebook.com/groups/cafedev.vn/
Instagram: https://instagram.com/cafedevn
Twitter: https://twitter.com/CafedeVn
Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
Pinterest: https://www.pinterest.com/cafedevvn/
YouTube: https://www.youtube.com/channel/UCE7zpY_SlHGEgo67pHxqIoA/
*/

#include <algorithm> // for std::swap, use <utility> instead if C++11
#include <iostream>
#include <iterator>
 
int main()
{
	int array[]{ 30, 50, 20, 10, 40 };
	constexpr int length{ static_cast<int>(std::size(array)) };
 
	// Step through each element of the array
	// (except the last one, which will already be sorted by the time we get there)
	for (int startIndex{ 0 }; startIndex < length - 1; ++startIndex)
	{
		// smallestIndex is the index of the smallest element we’ve encountered this iteration
		// Start by assuming the smallest element is the first element of this iteration
		int smallestIndex{ startIndex };
 
		// Then look for a smaller element in the rest of the array
		for (int currentIndex{ startIndex + 1 }; currentIndex < length; ++currentIndex)
		{
			// If we've found an element that is smaller than our previously found smallest
			if (array[currentIndex] < array[smallestIndex])
				// then keep track of it
				smallestIndex = currentIndex;
		}
 
		// smallestIndex is now the smallest element in the remaining array
                // swap our start element with our smallest element (this sorts it into the correct place)
		std::swap(array[startIndex], array[smallestIndex]);
	}
 
	// Now that the whole array is sorted, print our sorted array as proof it works
	for (int index{ 0 }; index < length; ++index)
		std::cout << array[index] << ' ';
 
	std::cout << '\n';
 
	return 0;
}

i startIndex. Cuối cùng, vòng lặp bên ngoài (startIndex) tiến một phần tử và quá trình này được lặp lại.

Gợi ý: Nếu bạn gặp khó khăn trong việc tìm hiểu cách hoạt động của chương trình ở trên, thì việc thông qua một trường hợp mẫu trên một mảnh giấy có thể hữu ích. Viết các phần tử mảng bắt đầu (chưa được sắp xếp) theo chiều ngang ở đầu tờ giấy. Vẽ các mũi tên cho biết phần tử startIndex, currentIndex và smallIndex đang lập chỉ mục. Theo dõi thủ công qua chương trình và vẽ lại các mũi tên khi các chỉ số thay đổi. Đối với mỗi lần lặp của vòng lặp ngoài, hãy bắt đầu một dòng mới hiển thị trạng thái hiện tại của mảng.

Việc sắp xếp tên hoạt động bằng cách sử dụng cùng một thuật toán. Chỉ cần thay đổi kiểu mảng từ int thành std :: string và khởi tạo với các giá trị thích hợp.

5. std :: sort

Vì việc sắp xếp mảng rất phổ biến, nên thư viện chuẩn C ++ bao gồm một hàm sắp xếp có tên std :: sort. std :: sort sống trong tiêu đề <algorithm> và có thể được gọi trên một mảng như sau:

#include <algorithm> // for std::sort
#include <iostream>
#include <iterator> // for std::size
 
int main()
{
	int array[]{ 30, 50, 20, 10, 40 };
 
	std::sort(std::begin(array), std::end(array));
 
	for (int i{ 0 }; i < static_cast<int>(std::size(array)); ++i)
		std::cout << array[i] << ' ';
 
	std::cout << '\n';
 
	return 0;
}

Theo mặc định, std :: sort sắp xếp theo thứ tự tăng dần bằng cách sử dụng toán tử <để so sánh các cặp phần tử và hoán đổi chúng nếu cần thiết (giống như ví dụ sắp xếp lựa chọn của chúng tôi đã làm ở trên).

Chúng ta sẽ nói thêm về std :: sort trong một chương sau.

Cài ứng dụng cafedev để dễ dàng cập nhật tin và học lập trình mọi lúc mọi nơi tại đây.

Nguồn và Tài liệu tiếng anh tham khảo:

• cplusplus
• w3schools
• Geeksforgeeks
• learncpp

Tài liệu từ cafedev:

• Full series tự học C++ từ cơ bản tới nâng cao tại đây nha.
• Ebook về C++ tại đây.
• Các series tự học lập trình MIỄN PHÍ khác
• Nơi liên hệ hợp tác hoặc quảng cáo cùng Cafedevn tại đây.

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

• Group Facebook
• Fanpage
• Youtube
• Instagram
• Twitter
• Linkedin
• Pinterest
• Trang chủ

Chào thân ái và quyết thắng!