[MUSIC CHƠI] DOUG LLOYD: sắp xếp lựa chọn là một thuật toán đó, như bạn mong đợi, sắp xếp một tập các phần tử. Và thuật toán thu hồi là một tập hợp các bước theo các bước các hướng dẫn để hoàn thành một nhiệm vụ. 

Trong lựa chọn sắp xếp Ý tưởng cơ bản là điều này, tìm các phần tử nhỏ nhất và không được phân loại thêm vào cuối danh sách được sắp xếp. Có hiệu quả những gì điều này là xây dựng một danh sách được sắp xếp, một trong những yếu tố tại một thời điểm. Phá vỡ nó xuống để giả chúng ta có thể nêu thuật toán này như sau, lặp lại cho đến khi không có các yếu tố không được phân loại vẫn còn. Tìm kiếm thông qua các không được phân loại dữ liệu để tìm giá trị nhỏ nhất, sau đó trao đổi các giá trị nhỏ nhất với các Yếu tố đầu tiên của phần được phân loại. 

Nó có thể giúp hình dung này, vì vậy chúng ta hãy nhìn vào điều này. Vì vậy, tôi tranh, là một mảng được phân loại và tôi đã chỉ ra nó bằng cách chỉ ra rằng tất cả của các yếu tố có màu đỏ, họ chưa được sắp xếp. Đây là toàn bộ phần chưa phân loại của mảng. 

Vì vậy, chúng ta hãy đi qua các bước của sắp xếp chọn để sắp xếp mảng này. Vì vậy, một lần nữa, chúng ta sẽ lặp lại đến khi không còn những yếu tố không được phân loại vẫn còn. Chúng tôi đang tìm kiếm sẽ qua dữ liệu để tìm giá trị nhỏ nhất, và sau đó trao đổi giá trị đó với các Yếu tố đầu tiên của phần được phân loại. 

Ngay bây giờ, một lần nữa, toàn bộ mảng là phần được phân loại. Tất cả các yếu tố màu đỏ là không được phân loại. Vì vậy, chúng tôi tìm kiếm thông qua và chúng ta tìm giá trị nhỏ nhất. Chúng tôi bắt đầu từ đầu, chúng tôi đi đến cùng, chúng ta tìm giá trị nhỏ nhất là, một trong. Vì vậy, đó là một phần một. Và sau đó một phần hai này, đổi giá trị đó với các yếu tố đầu tiên của phần không được phân loại, hoặc các yếu tố màu đỏ đầu tiên. 

Trong trường hợp này mà có thể năm, vì vậy chúng tôi trao đổi một đến năm. Khi chúng ta làm điều này, chúng ta có thể trực quan thấy rằng chúng tôi đã di chuyển các phần tử nhỏ nhất có giá trị của mảng, đến sự khởi đầu. Hiệu quả phân loại phần tử đó. 

Và vì vậy chúng tôi thực sự có thể xác nhận và nhà nước mà một, được sắp xếp. Và vì vậy chúng tôi sẽ chỉ ra những phần được sắp xếp các mảng của chúng tôi, bằng cách tô nó màu xanh. 

Bây giờ chúng ta chỉ cần lặp lại quá trình này một lần nữa. Chúng tôi tìm kiếm thông qua các phần chưa phân loại của mảng để tìm các phần tử nhỏ nhất. Trong trường hợp này, đó là hai. 

Chúng tôi trao đổi rằng với sự đầu tiên phần tử của một phần được phân loại. Trong trường hợp này hai cũng sẽ xảy ra là các yếu tố đầu tiên của phần được phân loại. Vì vậy, chúng tôi trao đổi hai với chính nó, mà thực sự chỉ còn hai nó ở đâu, và nó được sắp xếp. Tiếp tục, chúng tôi tìm kiếm thông qua để tìm các phần tử nhỏ nhất. Đó là ba. Chúng tôi trao đổi nó với người đầu tiên yếu tố, mà là năm. Và bây giờ ba được sắp xếp. 

Chúng tôi tìm kiếm thông qua một lần nữa, và chúng tôi tìm các phần tử nhỏ nhất là bốn. Chúng tôi trao đổi nó với phần tử đầu tiên của phần chưa phân loại, và bây giờ bốn được sắp xếp. 

Chúng tôi thấy rằng năm là các phần tử nhỏ nhất. Chúng tôi trao đổi nó với người đầu tiên phần tử của một phần được phân loại. Và bây giờ năm được sắp xếp. 

Và rồi cuối cùng, chúng tôi phần chưa phân loại bao gồm chỉ là một yếu tố duy nhất, vì vậy chúng tôi tìm kiếm thông qua và chúng ta thấy rằng sáu là nhỏ nhất, và trong thực tế, chỉ có yếu tố. Và sau đó chúng ta có thể nói rằng nó được sắp xếp. Và bây giờ chúng tôi đã chuyển sang mảng của chúng tôi từ khi được hoàn toàn không được phân loại màu đỏ, để sắp xếp hoàn toàn trong xanh, sử dụng sắp xếp chọn. 

Vì vậy, trường hợp xấu nhất ở đây là gì? Vâng trong tồi tệ nhất tuyệt đối trường hợp, chúng ta phải nhìn qua tất cả các yếu tố của mảng để tìm các phần tử nhỏ nhất không được phân loại, và chúng ta phải lặp lại Quá trình này n lần. Một lần cho mỗi phần tử của mảng bởi vì chúng ta chỉ, trong thuật toán này, loại một trong những yếu tố tại thời gian. 

Trường hợp kịch bản tốt nhất là gì? Vâng nó chính xác như nhau, phải không? Chúng tôi thực sự phải vẫn bước qua mỗi phần tử của mảng để xác nhận rằng nó là, trong thực tế, các phần tử nhỏ nhất. 

Vì vậy, thời gian chạy trường hợp xấu nhất, chúng tôi phải lặp lại một quá trình n lần, một lần cho mỗi nguyên tố n. Và trong trường hợp tốt nhất, chúng ta phải làm như vậy. 

Vì vậy, suy nghĩ trở lại của chúng tôi tính toán hộp công cụ phức tạp, làm những gì bạn nghĩ là tồi tệ nhất trường hợp thời gian chạy để lựa chọn loại? Những gì bạn nghĩ là tốt nhất trường hợp thời gian chạy để lựa chọn loại? 

Bạn có đoán Big O của n bình phương, và Big Omega của n bình? Bạn muốn được bên phải. Đó là, trong thực tế, trường hợp xấu nhất và trường hợp tốt nhất chạy lần, sắp xếp chọn. 

Tôi Doug Lloyd. Đây là CS50.