- đầu tiên tại sao chúng ta cần sắp xếp?
+ việc chúng ta sắp xếp sẽ khiến các bài toán khác trở nên đơn giản hơn rất nhiều
-đầu tiên chúng ta sẽ đến với thuật toán sắp xếp đơn giản nhất
-nổi bọt(bubble sort)
so sánh 2 phần tử kề nhau nếu chúng chưa đứng đúng vị trí thì đổi chỗ
-chèn(insertion sort) giống như xếp quân bài
+thì để giải quyết vấn đề này chúng ta giải quyết các vấn đề sau trước
+phần tử nghịch thế đi tìm nó
+phân biệt giữa dời và đổi chỗ và giải quyết vấn đề dời
+giải quyết vấn đề chèn
-vậy chúng ta đã chia nhỏ bài toán sắp xếp chèn thành 3 việc cần phải giải quyết
-bài toán giả sử: sắp xếp mảng có 5 phần tử{1,4,5,2,9}
+vấn đề nghịch thế: chúng ta thấy số 2 là nghịch thế làm sao máy tính biết được nó: chúng ta xét: for(int i=0;i+dời khác đổi chỗ là khi dời chúng ta dời các 1 hay nhiều phần tử ra trước hoặc ra sau còn đổi chỗ chỉ đổi chỗ 1 phần tử:
bây giờ làm sao chúng ta biết cần phải dời những phần tử nào, chúng ta đã biết phần tử nghịch thế là số 2, nên các số lơn hơn nó sẽ dời ra sau nó chả lẽ bây giờ chúng ta cứ dời từng phần tử rồi xét lại mảng tìm phần tử nghịch thế rồi dời tiếp sao chắc chắn là không rồi vậy thử nghĩ làm sao chúng ta có thể dời mà không cần xét lại mảng => chúng ta không sử dụng vòng if được rồi vì nó thực hiện được có 1 lần nên chúng ta có thể chọn vòng while vì chúng ta chưa biết được chúng ta phải dời bao nhiêu lần
+bây giờ chúng ta xét cách dời phần tử: xét mảng trên chúng ta so sánh số 2 với số 5, 2 nhỏ hơn nên chúng ta dời số 5 về sau 1 bước chúng ta lại xét tiếp 2 với 4, 2<4 nên dời số 4 về sau 1 bước chúng ta so sánh số 2 và số 1 số 2 lớn hơn số 1 nên chúng ta nhét nó vào trước số 1 bây giờ chuyển ý tưởng chúng ta thành mã code bằng những kiến thức chúng ta có về mã code
+tiếp tục chúng phải xác định có bao nhiêu phần tử cần dời và dời nó đi đâu cho chính xác
-void insertionSort(int a[],int n)
{
for (int i = 1; i < n; i++)
{
int x = a[i];
int j = i;
// nhưng khi i mà giảm bất thường sẽ dẫn đến sai mảng mà chúng ta đang xét nên chúng ta phải mượn tạm thằng j làm trung gian
//chúng ta vẫn thực hiện được đổi chỗ mà không làm thay đổi i đang xét
while (j>0&&x < a[j - 1])
{
a[j] = a[j - 1];
j--;
}
a[j] = x;
}
}
- chúng ta phải hiểu tại sao như thế tai sao chúng ta sử dụng vòng while lại tốt hơn vòng for, sao chúng ta phải dùng biến j, tại sao chúng ta bắt đầu i từ 1 mà không phải i từ 0,
=> kết luận:lập trình không khó nhưng cái khó nhất khi chúng ta code là thậm chí chúng ta code mà chúng ta không biết đang làm gì
các bước trước khi code, code cũng như đánh cờ vậy muốn đánh cờ tốt chúng ta phải phân tích những nước đi chúng ta đang muốn làm cái gì và nước đi nào là tối ưu và tại sao chúng ta đi nước đó
-tìm ý tưởng giải bài toán:chia nó thành các bước cần thực hiện chúng ta phải biết chúng ta đang làm gì và đang đi đâu
- chuyển nó thành mã code mà chúng ta có kiến thức về lập trình đó là cấu trúc dữ liệu và những thứ liên quan
-hiệu chỉnh dần cho đến khi chính xác không ai có thể code 1 bài toán chính xác ngay lúc đầu đó là lời nói của thầy chúng tôi