>> [MUSIC CHƠI]
>> DOUG LLOYD: Vì vậy, sắp xếp chèn là một thuật toán chúng ta có thể sử dụng để sắp xếp một mảng.
Ý tưởng đằng sau thuật toán này là xây dựng mảng được sắp xếp của bạn
tại chỗ, chuyển các yếu tố ra khỏi cách như bạn đi, để làm cho căn phòng.
Điều này là hơi khác nhau từ lựa chọn loại hoặc bong bóng
sắp xếp, ví dụ, nơi chúng tôi đang điều chỉnh các vị trí,
nơi mà chúng tôi đang thực hiện giao dịch hoán đổi.
>> Trong trường hợp này những gì chúng tôi đang thực sự làm là yếu tố trượt
hơn, ra khỏi con đường.
Làm thế nào thuật toán này làm việc trong giả?
Vâng chúng ta hãy chỉ tùy tiện nói rằng Yếu tố đầu tiên của mảng được sắp xếp.
Chúng tôi đang xây dựng nó tại chỗ.
>> Chúng ta sẽ đi một yếu tố tại một thời gian và xây dựng nó, và do đó, điều đầu tiên chúng ta thấy
là một mảng một phần tử.
Và theo định nghĩa, một mảng phần tử được sắp xếp.
>> Sau đó chúng tôi sẽ lặp lại quá trình này until-- chúng ta sẽ lặp lại các quá trình sau đây
cho đến khi tất cả các yếu tố đều được sắp xếp.
Nhìn vào các yếu tố không được phân loại tiếp theo và chèn nó vào phần được sắp xếp,
bằng cách thay đổi số lượng yêu cầu các yếu tố ra khỏi con đường.
Hy vọng rằng hình này sẽ giúp bạn thấy chính xác những gì
xảy ra với sắp xếp chèn.
>> Vì vậy, một lần nữa, đây là của chúng tôi toàn bộ mảng không được phân loại,
tất cả các yếu tố chỉ màu đỏ.
Và chúng ta hãy thực hiện theo các bước của mã giả của chúng tôi.
Điều đầu tiên chúng tôi làm, là chúng ta gọi là Yếu tố đầu tiên của mảng, sắp xếp.
Vì vậy, chúng tôi sẽ chỉ nói năm, bạn tôi bây giờ được sắp xếp.
>> Sau đó, chúng ta nhìn vào các tiếp theo yếu tố không được phân loại của mảng
và chúng tôi muốn chèn rằng thành phần được sắp xếp,
bằng cách chuyển các yếu tố trên.
Vì vậy, hai là không được phân loại tiếp theo phần tử của mảng.
Rõ ràng nó thuộc về trước năm, vì vậy những gì chúng ta sẽ làm
là loại giữ hai dành cho một thứ hai, chuyển năm qua, và sau đó chèn hai
trước năm, đâu cần đi.
Và bây giờ chúng ta có thể nói rằng hai được sắp xếp.
>> Vì vậy, như bạn có thể thấy, chúng ta chỉ đã cho đến nay nhìn hai yếu tố của mảng.
Chúng tôi đã không xem xét các nghỉ ngơi ở tất cả, nhưng chúng ta
đã hai yếu tố được sắp xếp theo cách của các cơ chế chuyển dịch.
>> Vì vậy, chúng ta lặp lại quá trình này một lần nữa.
Nhìn vào không được phân loại tiếp theo yếu tố, đó là một.
Chúng ta hãy nắm mà dành cho một thứ hai, thay đổi tất cả mọi thứ trên, và đặt một
nơi cần đi.
>> Một lần nữa, vẫn còn, chúng tôi đã chỉ có bao giờ nhìn một, hai, và năm.
Chúng tôi không biết những gì khác đang đến, nhưng chúng tôi đã sắp xếp ba yếu tố.
>> Yếu tố không được phân loại tiếp theo là ba, vì vậy chúng tôi sẽ thiết lập nó sang một bên.
Chúng tôi sẽ thay đổi theo những gì chúng tôi cần đó, thời gian này
không phải là tất cả mọi thứ như trong các trước hai trường hợp, nó chỉ là các năm.
Và sau đó chúng tôi sẽ dính ba, giữa hai và năm.
>> Sáu là tiếp theo không được phân loại yếu tố để các mảng.
Và trên thực tế lớn hơn sáu năm, vì vậy chúng tôi thậm chí không cần phải làm bất cứ trao đổi.
Chúng tôi chỉ có thể tack sáu phải vào sự kết thúc của phần được sắp xếp.
>> Cuối cùng, bốn là yếu tố không được phân loại cuối cùng.
Vì vậy, chúng tôi sẽ thiết lập nó sang một bên, thay đổi theo các yếu tố chúng ta cần phải thay đổi theo,
và sau đó đặt bốn nơi mà nó thuộc về.
Và bây giờ nhìn, chúng tôi đã loại của tất cả các yếu tố.
Chú ý với chèn sắp xếp, chúng tôi không có
để đi qua lại trên mảng.
Chúng tôi chỉ đi qua mảng một thời gian, và chúng tôi chuyển điều
rằng chúng ta đã gặp phải, theo thứ tự để nhường chỗ cho các yếu tố mới.
>> Vì vậy, trường hợp xấu nhất là gì kịch bản với sắp xếp chèn?
Trong trường hợp xấu nhất, mảng là theo thứ tự ngược.
Bạn phải thay đổi mỗi nguyên tố n lên đến vị trí n, mỗi lần chúng ta duy nhất
làm cho một chèn.
Đó là rất nhiều thay đổi.
>> Trong trường hợp tốt nhất, mảng được sắp xếp một cách hoàn hảo.
Và loại giống như những gì đã xảy ra với năm và sáu trong ví dụ,
đó chúng ta chỉ có thể tack nó trên mà không cần phải làm bất cứ chuyển dịch,
chúng tôi chủ yếu muốn làm điều đó.
>> Nếu bạn tưởng tượng rằng chúng tôi mảng là một đến sáu,
chúng tôi muốn bắt đầu bằng tuyên bố một được sắp xếp.
Hai đưa ra sau khi một vì vậy chúng ta có thể chỉ nói, OK, cũng một và hai đều được sắp xếp.
Ba đưa ra sau khi hai như vậy, OK, một và hai và ba đều được sắp xếp.
>> Chúng tôi không thực hiện bất kỳ giao dịch hoán đổi, chúng tôi chỉ cần di chuyển dòng tùy tiện này
giữa sắp xếp và không được phân loại như chúng ta đi.
Hiệu quả như chúng ta đã làm trong ví dụ này, chuyển các yếu tố màu xanh, khi chúng tôi tiến.
Vì vậy, thời gian chạy trường hợp xấu nhất là những gì, sau đó?
Hãy nhớ rằng, nếu chúng ta phải thay đổi mỗi các yếu tố n có thể là vị trí n,
hy vọng cung cấp cho bạn một ý tưởng rằng trường hợp xấu nhất
thời gian chạy là Big O của n bình phương.
>> Nếu mảng là hoàn hảo sắp xếp, tất cả chúng ta phải làm
là nhìn vào từng yếu tố duy nhất một lần, và sau đó chúng tôi đang thực hiện.
Vì vậy, trong trường hợp tốt nhất, đó là omega của n.
>> Tôi Doug Lloyd.
Đây là CS50.