Đây là bài viết đầu tiên trong series về các thuật toán sắp xếp và tìm kiếm căn bản.
Mình xin giới thiệu các bạn thuật toán sắp xếp Interchange Sort - ĐPT O(n^2).
Mình sẽ cố trình bày mọi thứ theo cách dễ hiểu nhất nhé.
Có một câu nói của Einstein dưới đây, làm mình thực sự tâm đắc:
"Nếu bạn không giúp được một đứa trẻ 6 tuổi hiểu ra vấn đề, thị thật ra... bạn chẳng hiểu gì cả!" - Einstein
Nên nếu bạn không hiểu, thì đó là lỗi của mình nhé. Mình khuyến khích các bạn hỏi tất cả mọi thứ mà bản thân thắc mắc luôn ha.
Ok, bắt đầu nè...
Nếu ai đó cho bạn một dãy số gồm N phần tử lộn xộn, thì bạn sẽ làm như thế nào để sắp xếp nó nhỉ?
Một ý tưởng đơn giản nhất có thể nghĩ ra là:
- Bước 1. Đầu tiên, mình sẽ tìm ra giá trị nhỏ nhất của dãy số từ vị trí 1..N.
- Bước 2. Sau đó, đổi chỗ giá trị nhỏ nhất đó cho vị trí đầu tiên.
- Bước 3. Lặp lại bước 1 và bước 2, nhưng giờ đây là từ vị trí số 2 (vì giờ đây ta đã có giá trị đầu tiên là giá trị nhỏ nhất rồi, nên có thể bỏ qua nó).
Mình để ý rằng, khi đến bước 3, thực sự ta đã thu hẹp được bài toán. Từ dãy số 1..N, giờ đây còn 2..N. Và cứ như thế thì ta cứ thu hẹp dần cho đến N..N thì coi như xong.
Và đây chính là thuật toán interchange sort.
Dưới đây là code mẫu mình đã chuẩn bị:
#include <cstdlib>
#include <iostream> using namespace std; const int sz = 10;
int arr[sz]; void printArray() { for (int i=0; i<sz; i++) { cout<<arr[i]<<" "; } cout<<endl;
} void printArray(int pos) { cout<<"Array after "<<pos<<"-th min position changed: \n"; for (int j=0; j<=pos; j++) { cout<<arr[j]<<" "; } cout<<"|"; for (int j=pos+1; j<sz; j++) { cout<<" "<<arr[j]; } cout<<endl;
} int main(){ for (int i=0; i<sz; i++) { arr[i] = rand() % 100; } cout<<"Original array: \n"; printArray(); for (int i=0; i<sz-1; i++) { int minPosition = i; for (int j=i+1; j<sz; j++) { if (arr[minPosition] > arr[j]) { minPosition = j; } } swap(arr[i], arr[minPosition]); printArray(i); } return 0;
}