Đánh giá thuật toán insertion sort năm 2024
|
Giới thiệu và hiện thực thuật toán sắp xếp chèn - Insertion Sort qua code C/C++ sắp xếp tăng dần 1 mảng, đây cũng là 1 trong các thuật toán sắp xếp kinh điển và dễ hiện thực. Show Insertion SortÝ tưởngXét danh sách con gồm Để sắp xếp phần tử Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp. Sau đây là mô phỏng thuật toán Insertion Sort Tạo dãy số ngẫu nhiên để mô phỏng sắp xếp Mã nguồn được thực hiện trên javascript var InsertionSort = function () { $.extend(this, new SortX()); this.onCreateScripts = function (array, scripts) { var $this = this; var addScript = function (a1, a2, action) { scripts.push($this.createScript0(a1, a2)); // Script lấy ra 2 số cần so sánh scripts.push($this.createScript1(a1, a2)); // Script để thực hiện so sánh giữa 2 số return action(); } var j, last; for (var i = 1; i < array.length; i++) { last = array[i]; j = i; while ((j > 0) && addScript(array[j - 1], last, () => array[j - 1].number > last.number)) { var a1 = array[j - 1]; array[j] = a1; scripts.push($this.createScript2(a1, last)); j = j - 1; } array[j] = last; } } } var pageSortX = new PageSortX(); pageSortX.sortX = new InsertionSort(); pageSortX.start(); Sơn 20 Bài viết gốc được đăng tải tại sonpc20.com Có thể bạn quan tâm:
Xem thêm Việc làm Developer hấp dẫn trên TopDev Để sắp xếp một mảng rất ít phần tử hoặc hoàn thiện việc sắp xếp một mảng lớn đã gần hoàn chỉnh người ta thường sử dụng thuật toán Insertin sort. Vậy ... 1. Thuật toán INSERTION SORT là gì?Thuật toán Insertion sort Thuật toán Insertion Sort (Sắp xếp chèn) là một thuật toán sắp xếp đơn giản. Trong cuộc sống thực có thể bạn sẽ sử dụng thuật toán này mà không hề biết mình đang dùng. Bởi vì Insertion Sort là một trong những cách sắp xếp tự nhiên nhất. Hãy lấy một ví dụ:
Bạn sẽ làm gì? Theo cách nghĩ tự nhiên nhất, bạn sẽ duyệt lần lượt các thẻ bài trong cỗ bài, bắt đầu duyệt từ vị trí đầu tiên hoặc duyệt từ cuối lên, so sánh giá trị của thẻ bài mới với giá trị của các thẻ bài trong cỗ bài. Khi bạn tìm đúng vị trí, bạn sẽ chèn (insert) thẻ bài mới vào đó. * Các con nghiện tá lả chắc biết rõ lắm nhỉ :D Tương tự, nếu tiếp tục đưa cho bạn thêm các lá bài mới, bạn sẽ lặp lại quy trình đó, chèn thẻ mới, đồng thời vẫn đảm bảo thứ tự của các thẻ bài. Đây chính là cơ chế hoạt động của Insertion Sort. Nó bắt đầu từ phần tử thứ 2 (tức index = 1). Coi phần tử đầu tiên (tức index = 0) là một cỗ bài đã được sắp xếp. Mỗi phần tử bắt đầu từ vị trí index = 1 sẽ giống như 1 thẻ bài mới. Với cấu trúc dữ liệu mảng, chúng ta tưởng tượng là, mảng gồm hai phần:
Giải thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các phần tử không có thứ tự sẽ được di chuyển và được chèn vào vị trí thích hợp trong danh sách con (của cùng mảng đó). 2. Ý tưởng và Mô tả thuật toán Insertion sortGiải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Trong thuật toán, để sắp xếp một mảng có kích thước 1: Lặp lại từ 2: So sánh phần tử hiện tại (khóa) với phần tử trước của nó. 3: Nếu phần tử chính nhỏ hơn phần tử trước của nó, hãy so sánh nó với các phần tử trước đó. Di chuyển các phần tử lớn hơn lên một vị trí để tạo khoảng trống cho phần tử được hoán đổi. Giả sử một mảng được cho ngẫu nhiên 12, 11, 13, 5, 6 thì việc áp dụng thuật toán Insertion Sort được mô tả như sau:
Đến đây xem như thuật toán đã kết thúc, các phần tử được sắp xếp theo thứ tự mong muốn. 3. Triển khai thuật toán Insertion sort trong JavaTiếp nối ý tưởng của mục 2, liệu khi đã có ý tưởng và giải thuật cơ bản, bạn có thể tự mình triển khai thuật Insertion Sort trong Java không? Để việc học lập trình được tốt nhất, mình khuyên bạn hãy dừng lại và thử tự mình thực hiện trước cho đến khi nào chịu thua thì quay lại đây. Còn nếu bạn có thể thì cũng không cần đọc tiếp nữa :D package insertion.sort.algo; public class InsertionSort { // Phương thức sắp xếp chèn void sort(int arr[]) { int n \= arr.length; for (int i \= 1; i < n; ++i) { int key \= arr[i]; int j \= i - 1; // Di chuyển các phần tử của arr [0 ... i - 1], lớn hơn key // đến một vị trí trước vị trí hiện tại của chúng while (j \>= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j \= j - 1; } arr[j + 1] = key; } } // In các phần tử của mảng static void printArray(int arr[]) { int n \= arr.length; for (int i \= 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6 }; System.out.println("Mảng ban đầu:"); printArray(arr); InsertionSort ob \= new InsertionSort(); ob.sort(arr); System.out.println("Mảng sau khi sắp xếp:"); printArray(arr); } } Khi chạy chương trình, ta nhận được kết quả là: Mảng ban đầu: 12 11 13 5 6 Mảng sau khi sắp xếp: 5 6 11 12 13 Sắp xếp chèn được sử dụng khi số lượng phần tử nhỏ. Nó cũng có thể hữu ích khi mảng đầu vào gần như được sắp xếp, chỉ có một số phần tử bị đặt sai vị trí trong một mảng lớn hoàn chỉnh. Chúng ta có thể sử dụng tìm kiếm nhị phân để giảm số lượng so sánh trong sắp xếp chèn thông thường. Binary Insertion Sort được sử dụng để tìm kiếm nhị phân vị trí thích hợp để chèn mục đã chọn ở mỗi lần lặp. Trong trường hợp chèn thông thường, việc sắp xếp lấy Nói chung, thuật toán vẫn có thời gian chạy trong trường hợp xấu nhất là `n`4 vì chuỗi hoán đổi cần thiết cho mỗi lần chèn. Trong sắp xếp chèn thông thường, nó cần `n`4 so sánh (ở lần lặp thứ n) trong trường hợp xấu nhất. Chúng ta có thể giảm nó thành `n`6 bằng cách sử dụng tìm kiếm nhị phân. package insertion.sort.algo; import java.util.Arrays; public class BinaryInsertionSort { public static void main(String[] args) { final int[] arr \= { 12, 11, 13, 5, 6 }; new BinaryInsertionSort().sort(arr); for (int i \= 0; i < arr.length; i++) System.out.print(arr[i] + " "); } public void sort(int array[]) { for (int i \= 1; i < array.length; i++) { int x \= array[i]; // Tìm vị trí để chèn bằng tìm kiếm nhị phân int j \= Math.abs(Arrays.binarySearch(array, 0, i, x) + 1); // Chuyển mảng sang đúng một vị trí System.arraycopy(array, j, array, j + 1, i - j); // Đặt phần tử vào đúng vị trí của nó array[j] = x; } } } Binary Insertion Sort có thể được xem là Insertion Sort cải tiến, nhưng bạn hãy nhìn xem – code tuy ngắn gọn hơn nhưng mang tính nâng cao hơn khá nhiều. Nhờ vậy, trong đa số trường hợp (không phải là xấu nhất) thì tốc độ ăn đứt Insertion Sort. Thuật toán Insertion sort không phải là thuật toán quá khó khăn, thậm chí rất gần gũi với thực tiễn cuộc sống – nhưng đôi khi bạn không nhận ra mình đang áp dụng thuật toán insertion sort mà thôi. \> Đối với việc HỌC LẬP TRÌNH thì không có sự trùng hợp như vậy được, bạn phải trải qua gian khổ - luyện code mới sớm thành thục được. --- HỌC VIỆN ĐÀO TẠO CNTT NIIT - ICT HÀ NỘI Học Lập trình chất lượng cao (Since 2002). Học làm Lập trình viên. Hành động ngay! Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội SĐT: 02435574074 - 0914939543 Email: [email protected] Fanpage: https://facebook.com/NIIT.ICT/ niitniithanoiniiticthanoihoclaptrinhkhoahoclaptrinhhoclaptrinhjavahoclaptrinhphpjavaphppython |
