Bài 2:                      Sắp Xếp Chèn(Inserion Sort)

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.

1.Tư tưởng

Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu a1,…,ak. Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu a1,…,ak − 1 đã được sắp. Để sắp xếp phần tử ak = x ta tìm vị trí thích hợp của nó trong dãy a1,…,ak − 1. Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

Các phần tử ≤x Vị trí thích hợp Các phần tử>x Các phần tử chưa sắp
a1 ai − 1 x ai + 1 ak − 1 ak + 1 an

Ví dụ

Cho danh sách

1 3 7 6 4 2 5

Danh sách con gồm 3 phần tử bên trái 1,3,7 đã được sắp. Để tiếp tục sắp xếp phần tử thứ tư a4 = 6 vào danh sách con đó, ta tìm vị trí thích hợp của nó là sau 3 và trước 7.

1 3 6 7 4 2 5

Làm tiếp theo với a5 = 4 ta được

1 3 4 6 7 2 5

Làm tiếp theo với a6 = 2 ta được

1 2 3 4 6 7 5

Cuối cùng chèn a7 = 5

1 2 3 4 5 6 7

2.Giải thuật

  • Danh sách a bắt đầu từ chỉ số 1 tới length
 Procedure Insert (array a, int k, Value) {
      int i := k-1;
     while (i > 0 and a[i] > value) {
         a[i+1] := a[i];
         i := i - 1;
     }
     a[i+1] := value;
 }
 Procedure InsertSort (array a, int length) {
     int k := 2;
     while (k <= length) {
         insert(a, k, a[k]);
         k := k + 1;
     }
 }

3.Cài đặt bằng Java

3.1.Lớp InsertionSort

1  // Fig 16.8: InsertionSort.java
 2  // Class that creates an array filled with random integers.
 3  // Provides a method to sort the array with insertion sort.
 4  import java.util.Random;
 5
 6  public class InsertionSort
 7  {
 8     private int[] data; // array of values
 9     private static Random generator = new Random();
10
11     // create array of given size and fill with random integers
12     public InsertionSort( int size )
13     {
14        data = new int [ size ]; // create space for array
15
16        // fill array with random ints in range 10-99
17        for ( int i = 0; i < size; i++ )
18           data[ i ] = 10 + generator.nextInt( 90 );
19     } // end InsertionSort constructor
20
21     // sort array using insertion sort
22     public void sort()                
23     {
24        int insert; // temporary variable to hold element to insert
25
26        // loop over data.length - 1 elements           
27        for ( int next = 1; next < data.length; next++ )
28        {
29           // store value in current element
30           insert = data[ next ];           
31
32           // initialize location to place element
33           int moveItem = next;                   
34
35           // search for place to put current element             
36           while ( moveItem > 0 && data[ moveItem - 1 ] > insert )
37           {
38              // shift element right one slot         
39              data[ moveItem ] = data[ moveItem - 1 ];
40              moveItem--;                             
41           } // end while                             
42
43           data[ moveItem ] = insert; // place inserted element    
44           printPass( next, moveItem ); // output pass of algorithm
45        } // end for                                               
46     } // end method sort                                          
47
48     // print a pass of the algorithm
49     public void printPass( int pass, int index )
50     {
51        System.out.print( String.format( "after pass %2d: ", pass ) );
52
53        // output elements till swapped item
54        for ( int i = 0 ; i < index; i++ )
55           System.out.print( data[ i ] + "  " );
56
57        System.out.print( data[ index ] + "* " ); // indicate swap
58
59        // finish outputting array
60        for ( int i = index + 1; i < data.length; i++ )
61           System.out.print( data[ i ] + "  " );
62
63        System.out.print( "\n               " ); // for alignment
64
65        // indicate amount of array that is sorted
66        for( int i = 0; i <= pass; i++ )
67           System.out.print( "--  " );
68        System.out.println( "\n" ); // add endline
69     } // end method printPass
70
71     // method to output values in array
72     public String toString()
73     {
74        StringBuffer temporary = new StringBuffer();
75
76        // iterate through array
77        for ( int element : data )
78           temporary.append( element + "  " );
79
80        temporary.append( "\n" ); // add endline character
81        return temporary.toString();
82     } // end method toString
83  } // end class InsertionSort

3.2.Lớp InsertionSortTest

1  // Fig 16.9: InsertionSortTest.java

2  // Test the insertion sort class.

3

4  public class InsertionSortTest

5  {

6     public static void main( String[] args )

7     {

8        // create object to perform selection sort

9        InsertionSort sortArray = new InsertionSort( 10 );

10

11        System.out.println( “Unsorted array:” );

12        System.out.println( sortArray ); // print unsorted array

13

14        sortArray.sort(); // sort array

15

16        System.out.println( “Sorted array:” );

17        System.out.println( sortArray ); // print sorted array

18     } // end main

19  } // end class InsertionSortTest

Kết quả

Unsorted array:

40 17 45 82 62 32 30 44 93 10

after pass 1: 17* 40 45 82 62 32 30 44 93 10

— —

after pass 2: 17 40 45* 82 62 32 30 44 93 10

— — —

after pass 3: 17 40 45 82* 62 32 30 44 93 10

— — — —

after pass 4: 17 40 45 62* 82 32 30 44 93 10

— — — — —

after pass 5: 17 32* 40 45 62 82 30 44 93 10

— — — — — —

after pass 6: 17 30* 32 40 45 62 82 44 93 10

— — — — — — —

after pass 7: 17 30 32 40 44* 45 62 82 93 10

— — — — — — — —

after pass 8: 17 30 32 40 44 45 62 82 93* 10

— — — — — — — — —

after pass 9: 10* 17 30 32 40 44 45 62 82 93

— — — — — — — — — —

Sorted array:

10 17 30 32 40 44 45 62 82 93

Các bài viết liên quan:
Thuật toán sắp xếp – Phần 2