Sắp xếp thời gian

Tram Ho

Sắp xếp dữ liệu hiệu quả và nhanh chóng là một trong những cuộc nói chuyện nóng bỏng giữa các kỹ sư khoa học máy tính. Một số thuật toán hiệu quả được tạo ra để làm như vậy, nhưng nhiều nghiên cứu đang trải qua để đạt được dấu thời gian tuyến tính. Hôm nay cuộc thảo luận của chúng tôi sẽ là về Timsort, một thuật toán không mấy nổi tiếng, được gọi là thuật toán nhanh nhất trên thế giới mà bạn chưa bao giờ nghe nói tới.

Sắp xếp thời gian

Timsort là một thuật toán sắp xếp hỗn hợp và hiệu quả được tạo ra bằng cách sử dụng khái niệm cả sắp xếp hợp nhất và sắp xếp chèn. Hơn nữa, nó được thiết kế để thực hiện tốt trên nhiều loại dữ liệu trong thế giới thực. Tuy nhiên, đây là một trong số ít các thuật toán sắp xếp không xuất hiện trong phòng học. Nó được Tim Peters triển khai vào năm 2002 để sử dụng trong ngôn ngữ lập trình Python. Thuật toán tìm kiếm hệ quả của dữ liệu đã có theo thứ tự và sử dụng kết quả này để sắp xếp phần còn lại hiệu quả hơn. Sắp xếp này là sắp xếp mặc định trong ngôn ngữ lập trình python. trong phiên bản python> = 2.3, chỉ sort (mảng) sẽ áp dụng sắp xếp thời gian trên dữ liệu. Mặc dù trọng tâm để phát triển điều này chỉ dựa trên ngôn ngữ python, nhưng nó cũng được sử dụng rộng rãi trong các nền tảng khác, chẳng hạn như, JAVA, ANDROID, Google Chrome, v.v.

Tầm quan trọng

Nhìn vào hình ảnh trên, chúng ta có thể phân tích các sự kiện đáng chú ý. Ở mức tốt nhất, Tim Sắp xếp áp đảo Sắp xếp Hợp nhất và Sắp xếp nhanh. Ở mức tồi tệ nhất, nó chạy ở thời điểm song song với Sắp xếp hợp nhất trong khi phân loại nhanh Sắp xếp. Nói chính xác hơn, thời gian thực hiện của nó là chính xác nhanh. Mặt khác, Tim Sort nằm ở đầu đen của quang phổ về không gian. Mặc dù O (n) không quá khắc nghiệt, nhưng đây là trường hợp nhận được điểm trừ hơn quicksort. Thuật ngữ cuối cùng để so sánh các thuật toán là sự ổn định, không được chú ý nhiều hơn tốc độ và không gian. Sự ổn định là một yếu tố rất quan trọng trong việc sắp xếp. Việc duy trì thứ tự các yếu tố bằng nhau có thể mang lại sự phụ thuộc nhiều hơn về độ chính xác của một kết quả lớn. Mặc dù sắp xếp nhanh không ổn định mọi lúc, Tim Sắp xếp ổn định. Sự ổn định là một trong những điểm mà thời gian sắp xếp đạt điểm cao hơn mặc dù nó hơi nặng so với quicksort.

Các bước thuật toán

Điểm chính của việc thực hiện là việc sử dụng chạy. Đầu tiên chúng ta cần đặt một kích thước mà chúng ta sẽ gọi là minrun. Điều chúng tôi cần nhận ra bằng cách này là chúng tôi muốn đảm bảo rằng tất cả các lần chạy của chúng tôi đều có ít nhất một kích thước nhất định. Ban đầu chúng tôi bắt đầu với một lần chạy và chúng tôi giữ nó để sử dụng sau. Khi chúng tôi tìm thấy lần chạy dài nhất trong phạm vi minsl. Bây giờ chúng ta có một mảng nhỏ, được sắp xếp. Nếu nó dài ít nhất là chiều dài, thì chúng tôi đã sẵn sàng để bắt đầu. Nếu không, chúng ta phải có sắp xếp chèn trong hành động. Nếu ít nhất nó không vượt quá độ dài, chúng tôi sẽ tiếp tục và tìm đủ các yếu tố khác để hoàn thành quá trình chạy và do đó sử dụng Sắp xếp chèn để đẩy chúng vào mảng được sắp xếp của chúng tôi một cách đơn giản. Rõ ràng, nếu một lần chạy đến cuối mảng, chúng ta có thể để nó ngắn một chút. Khi chúng tôi đã tạo tất cả các lần chạy, chúng tôi cần sử dụng Sắp xếp hợp nhất để kết hợp chúng lại với nhau. Trong trường hợp tốt nhất, toàn bộ mảng đã được sắp xếp và Tim Sort đủ thông minh để biết nó không cần phải làm gì khác. Những lần khác, nó có xu hướng cực kỳ hiệu quả. Là một lợi ích bổ sung, cả Sắp xếp chèn và Sắp xếp hợp nhất đều ổn định, do đó mảng kết quả là ổn định.

Trong cuộc nói chuyện nhỏ, chúng ta có thể viết các bước:

  • Xây dựng một minsl có kích thước nhỏ hơn 64. Thông thường chúng ta cần lấy một số có sức mạnh bằng 2. Để đơn giản, chúng ta thường lấy 32.
  • Tìm kiếm một lần chạy trong dữ liệu nhỏ đầu tiên.
  • Nếu chúng tôi không thể tìm thấy một lần chạy có độ dài tối thiểu, chúng tôi cần sử dụng Sắp xếp chèn để có được các mục tiếp theo và đẩy chúng vào chạy cho đến khi nó có kích thước chính xác.
  • Chúng ta cần lặp lại cho đến khi toàn bộ mảng được chia thành các phần phụ được sắp xếp.
  • Bây giờ chúng ta cần sử dụng Sắp xếp hợp nhất để tham gia các mảng được đặt hàng.

Thực hiện

Dưới đây là việc thực hiện ruby ​​của sắp xếp thời gian. Trong triển khai này, tôi bỏ qua việc thực hiện sắp xếp hợp nhất và sắp xếp nhanh. Nếu bạn cần thêm một số thông tin về họ, google luôn sẵn sàng phục vụ bạn.

Tim sort là một thuật toán sắp xếp rất mạnh mẽ, nhanh chóng và mạnh mẽ, tập trung chủ yếu vào dữ liệu trong thế giới thực. Nhưng bạn phải hiểu rằng nó không khả thi cho tất cả các trường hợp. Vì vậy, nếu bạn quan tâm nhiều hơn, bạn cần nghiên cứu thêm để hiểu cách sử dụng của nó.

Tham khảo: https://en.wikipedia.org/wiki/Timsort

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo