[Powered by Google Translate] [Sắp xếp chèn] [Tommy MacWilliam] [Đại học Harvard] [Đây là CS50.TV] Chúng ta hãy xem xét sắp xếp chèn, một thuật toán cho một danh sách các số và phân loại chúng. Một thuật toán, hãy nhớ, chỉ đơn giản là một thủ tục bước từng bước để hoàn thành một nhiệm vụ. Ý tưởng cơ bản đằng sau sắp xếp chèn, là để phân chia danh sách của chúng tôi thành hai phần, một phần được sắp xếp và một phần được phân loại. 

Tại mỗi bước của thuật toán, một số được chuyển từ phần phân loại phần được sắp xếp cho đến khi toàn bộ danh sách được sắp xếp. Dưới đây là danh sách sáu số phân loại 23, 42, 4, 16, 8, và 15. Kể từ khi những con số này không phải tất cả theo thứ tự tăng dần, họ đang được phân loại. Vì chúng tôi đã không bắt đầu sắp xếp chưa, chúng tôi sẽ xem xét tất cả sáu yếu tố phần phân loại của chúng tôi. 

Khi chúng tôi bắt đầu phân loại, chúng tôi sẽ đưa các con số được sắp xếp bên trái trong số này. Vì vậy, hãy bắt đầu với 23 phần tử đầu tiên trong danh sách của chúng tôi. Chúng tôi không có bất kỳ yếu tố trong phần sắp xếp của chúng tôi, vì vậy chúng ta chỉ đơn giản là xem xét 23 là sự khởi đầu và kết thúc phần sắp xếp của chúng tôi. Bây giờ, phần sắp xếp của chúng tôi có một số, 23, và phần phân loại của chúng tôi có năm con số này. Bây giờ chúng ta hãy chèn vào số tiếp theo trong phần phân loại của chúng tôi, 42 tuổi, thành phần được sắp xếp. 

Để làm như vậy, chúng tôi sẽ cần phải so sánh 42 đến số 23 - yếu tố duy nhất trong phần sắp xếp của chúng tôi cho đến nay. Bốn mươi hai là lớn hơn 23, vì vậy chúng tôi chỉ đơn giản là có thể phụ thêm 42 đến cuối cùng của phần sắp xếp danh sách. Great! Bây giờ là phần của chúng tôi được sắp xếp có hai yếu tố, và phần phân loại của chúng tôi có bốn yếu tố. Vì vậy, hãy di chuyển cho 4 phần tử tiếp theo trong phần phân loại. Vì vậy, nơi này nên được đặt trong phần được sắp xếp? 

Hãy nhớ rằng, chúng tôi muốn đặt con số này theo thứ tự sắp xếp do đó, phần của chúng tôi được sắp xếp vẫn được sắp xếp đúng ở tất cả các lần. Nếu chúng ta đặt 4 đến bên phải của số 42, sau đó danh sách của chúng tôi sẽ ra khỏi trật tự. Vì vậy, chúng ta hãy tiếp tục di chuyển từ phải sang trái trong phần loại của chúng tôi. Như chúng ta di chuyển, cho phép chuyển từng số xuống một nơi để nhường chỗ cho số điện thoại mới. Được rồi, 4 cũng là ít hơn 23, vì vậy chúng tôi không thể đặt nó ở đây cả. Hãy di chuyển 23 phải một nơi. 

Điều đó có nghĩa là chúng tôi muốn đặt 4 vào khe đầu tiên trong phần được sắp xếp. Chú ý không gian này trong danh sách đã trống rỗng, bởi vì chúng tôi đã di chuyển các yếu tố được sắp xếp như chúng ta đã gặp phải. Được rồi. Vì vậy, chúng tôi đang nằm ở đó. Hãy tiếp tục thuật toán của chúng tôi bằng cách chèn thêm số 16 vào phần được sắp xếp. Mười sáu là ít hơn 42, vì vậy hãy thay đổi số 42 bên phải. Mười sáu cũng là ít hơn 23, vì vậy chúng ta hãy cũng thay đổi yếu tố đó. 

Bây giờ, 16 là lớn hơn 4. Vì vậy, có vẻ như chúng tôi muốn để chèn 16 giữa 4 và 23. Trong khi di chuyển qua phần sắp xếp danh sách từ phải sang trái, 4 là số đầu tiên chúng ta đã thấy đó là nhỏ hơn so với số lượng chúng tôi đang cố gắng để chèn. Vì vậy, bây giờ chúng ta có thể chèn số 16 vào khe trống này, hãy nhớ rằng, chúng tôi đã tạo ra bởi các yếu tố di chuyển trong phần sắp xếp trên như chúng ta đã gặp phải. 

Được rồi. Bây giờ, chúng tôi có bốn yếu tố được sắp xếp và hai yếu tố được phân loại. Vì vậy, chúng ta hãy di chuyển 8 thành phần được sắp xếp. Tám là ít hơn 42. Tám là dưới 23. Và 8 là ít hơn 16. Nhưng 8 là lớn hơn 4. Vì vậy, chúng tôi muốn để chèn 8 giữa 4 và 16. Và bây giờ chúng tôi chỉ cần có một trong những yếu tố còn lại để sắp xếp trong 15. Mười lăm là ít hơn 42, Mười lăm là ít hơn 23. Và 15 là dưới 16. Nhưng 15 là lớn hơn 8. 

Vì vậy, đây là nơi chúng ta muốn làm cho chèn cuối cùng của chúng tôi. Và chúng tôi đang làm. Chúng tôi không có yếu tố hơn trong phần phân loại, và một phần của chúng tôi được sắp xếp theo thứ tự đúng. Các con số được sắp xếp từ nhỏ đến lớn. Vì vậy, chúng ta hãy có một cái nhìn tại một số mã giả mô tả các bước chúng tôi chỉ cần thực hiện. 

On line 1, chúng ta có thể thấy rằng chúng tôi sẽ cần để lặp qua mỗi phần tử trong danh sách ngoại trừ lần đầu tiên, kể từ khi các yếu tố đầu tiên trong phần phân loại chỉ đơn giản là sẽ trở thành phần tử đầu tiên trong phần được sắp xếp. Trên dòng 2 và 3, chúng tôi đang theo dõi vị trí hiện tại của chúng tôi trong phần phân loại. Yếu tố đại diện cho số chúng tôi đang di chuyển vào phần được sắp xếp, và j đại diện cho chỉ mục của chúng tôi vào phần phân loại. 

On line 4, chúng ta đang lặp lại thông qua phần được sắp xếp từ phải sang trái. Chúng tôi muốn dừng lại lặp lại một lần một phần tử bên trái của vị trí hiện tại của chúng tôi ít hơn so với các yếu tố mà chúng tôi đang cố gắng để chèn. Trên dong 5, chúng ta đang chuyển mỗi yếu tố chúng ta bắt gặp một không gian bên phải. Bằng cách đó, chúng tôi sẽ có một không gian rõ ràng để chèn vào khi chúng ta tìm thấy những yếu tố đầu tiên ít hơn so với các yếu tố mà chúng tôi đang di chuyển. On line 6, chúng tôi cập nhật truy cập của chúng tôi để tiếp tục di chuyển trái qua phần được sắp xếp. Cuối cùng, trên dòng 7, chúng tôi đang chèn các phần tử vào phần sắp xếp danh sách. 

Chúng tôi biết rằng nó được chèn vào vị trí j, bởi vì chúng tôi đã chuyển các yếu tố đó được sử dụng để có được một không gian bên phải. Hãy nhớ rằng, chúng tôi đang di chuyển qua phần sắp xếp từ phải sang trái, nhưng chúng tôi đang di chuyển qua phần được phân loại từ trái sang phải. Được rồi. Bây giờ chúng ta hãy có một cái nhìn bao lâu chạy rằng thuật toán mất. Đầu tiên chúng ta sẽ đặt câu hỏi như thế nào lâu cho thuật toán này để chạy trong trường hợp xấu nhất. Nhớ lại rằng chúng tôi đại diện cho thời gian chạy này với ký hiệu O Big. Để sắp xếp danh sách của chúng tôi, chúng tôi đã để lặp lại trên các yếu tố trong phần phân loại, và cho mỗi người trong số những yếu tố đó, có khả năng trên tất cả các yếu tố trong phần được sắp xếp. Trực giác, điều này nghe giống như một hoạt động O (n ^ 2). 

Nhìn giả của chúng tôi, chúng tôi có một vòng lặp lồng nhau bên trong vòng lặp khác, , quả thật vậy, âm thanh như một hoạt động O (n ^ 2). Tuy nhiên, phần sắp xếp danh sách không chứa toàn bộ danh sách cho đến phút cuối. Tuy nhiên, chúng tôi có thể có khả năng chèn một phần tử mới vào đầu của phần được sắp xếp trên mỗi lần lặp của thuật toán, điều này có nghĩa là chúng ta phải nhìn vào mỗi phần tử hiện đang trong phần được sắp xếp. Vì vậy, điều đó có nghĩa là chúng tôi có thể có khả năng làm cho một so sánh các yếu tố thứ hai, hai so sánh các yếu tố thứ ba, và như vậy. Vì vậy, tổng số của bước là tổng của các số nguyên từ 1 đến chiều dài của danh sách trừ đi 1. Chúng tôi có thể đại diện cho điều này với một tổng kết. 

Chúng tôi sẽ không đi vào summations ở đây, nhưng nó quay ra rằng tổng kết này là bằng n (n - 1) trên 2, tương đương với n ^ 2/2 - n / 2. Khi nói về thời gian chạy tiệm cận, này n ^ 2 hạn sẽ chi phối hạn n. Vì vậy, chèn sắp xếp là Big O (n ^ 2). Điều gì sẽ xảy ra nếu chúng ta chạy sắp xếp chèn vào một danh sách đã được sắp xếp. Trong trường hợp đó, chúng tôi chỉ đơn giản là muốn xây dựng phần được sắp xếp từ trái sang phải. Vì vậy, chúng tôi chỉ cần về trình tự các bước n. 

Điều đó có nghĩa là chèn loại có hiệu suất tốt nhất của n, mà chúng tôi đại diện với Ω (n). Và đó là nó sắp xếp chèn, chỉ là một trong rất nhiều các thuật toán chúng ta có thể sử dụng để sắp xếp một danh sách. Tên tôi là Tommy, và điều này là CS50. [CS50.TV] Oh, bạn không thể dừng lại một khi nó bắt đầu. Ồ, chúng tôi đã làm điều đó - >> Boom!