Bài 1:                      Sắp xếp chọn(Selection Sort)

1.Tư tưởng

Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

Các bước tiến hành như sau:

Bước 1: i=1

Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]

Bước 3: Hoán vị a[min] và a[i]

Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2

Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.

Ví dụ: Cho dãy a = (12,2,8,5,1,6,4,15)

12 2 8 5 1 6 4 15

Bước 1: 1 2 8 5 12 6 4 15

Bước 2: 1 2 8 5 12 6 4 15

Bước 3: 1 2 4 5 12 6 8 15

Bước 4: 1 2 4 5 12 6 8 15

Bước 5: 1 2 4 5 6 12 8 15

Bước 6: 1 2 4 5 6 8 12 15

Bước 7: 1 2 4 5 6 8 12 15

2.Giải thuật

Void SelectionSort(int a[], int n)

{

int min;

for(int i=0;i<n-1;i++)

{

min=i;

for(int j=i+1;j<n;j++)

if(a[j]<a[min]) min=j;

HoanVi(a[min],a[i]);

}

}

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

3.1.Lớp SelectionSort

 1  // Fig 16.6: SelectionSort.java
 2  // Class that creates an array filled with random integers.
 3  // Provides a method to sort the array with selection sort.
 4  import java.util.Random;
 5
 6  public class SelectionSort
 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 SelectionSort( 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 SelectionSort constructor
20
21     // sort array using selection sort
22     public void sort()                
23     {
24        int smallest; // index of smallest element
25
26        // loop over data.length - 1 elements        
27        for ( int i = 0 ; i < data.length - 1 ; i++ )
28        {
29           smallest = i; // first index of remaining array
30
31           // loop to find index of smallest element               
32           for ( int index = i + 1 ; index < data.length; index++ )
33              if ( data[ index ] < data[ smallest ] )              
34                 smallest = index;                                 
35
36           swap( i, smallest ); // swap smallest element into position
37           printPass( i + 1, smallest ); // output pass of algorithm  
38        } // end outer for                                            
39     } // end method sort                                             
40
41     // helper method to swap values in two elements
42     public void swap( int first, int second )
43     {
44        int temporary = data[ first ]; // store first in temporary
45        data[ first ] = data[ second ]; // replace first with second
46        data[ second ] = temporary; // put temporary in second
47     } // end method swap
48
49     // print a pass of the algorithm
50     public void printPass( int pass, int index )
51     {
52        System.out.print( String.format( "after pass %2d: ", pass ) );
53
54        // output elements till selected item
55        for ( int i = 0 ; i < index; i++ )
56           System.out.print( data[ i ] + "  " );
57
58        System.out.print( data[ index ] + "* " ); // indicate swap
59
60        // finish outputting array
61        for ( int i = index + 1; i < data.length; i++ )
62           System.out.print( data[ i ] + "  " );
63
64        System.out.print( "\n               " ); // for alignment
65
66        // indicate amount of array that is sorted
67        for ( int j = 0 ; j < pass; j++ )
68           System.out.print( "--   " );
69        System.out.println( "\n" ); // add endline
70     } // end method indicateSelection
71
72     // method to output values in array
73     public String toString()
74     {
75        StringBuffer temporary = new StringBuffer();
76
77        // iterate through array
78        for ( int element : data )
79           temporary.append( element + "  " );
80
81        temporary.append( "\n" ); // add endline character
82        return temporary.toString();
83     } // end method toString
84  } // end class SelectionSort
3.2.Xây dựng lớp SelectionSortTest

1  // Fig 16.7: SelectionSortTest.java

2  // Test the selection sort class.

3

4  public class SelectionSortTest

5  {

6     public static void main( String[] args )

7     {

8         // create object to perform selection sort

9         SelectionSort sortArray = new SelectionSort( 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 SelectionSortTest

Kết quả:

Unsorted array:

61 87 80 58 40 50 20 13 71 45

after pass 1: 13 87 80 58 40 50 20 61* 71 45

after pass 2: 13 20 80 58 40 50 87* 61 71 45

— —

after pass 3: 13 20 40 58 80* 50 87 61 71 45

— — —

after pass 4: 13 20 40 45 80 50 87 61 71 58*

— — — —

after pass 5: 13 20 40 45 50 80* 87 61 71 58

— — — — —

after pass 6: 13 20 40 45 50 58 87 61 71 80*

— — — — — —

after pass 7: 13 20 40 45 50 58 61 87* 71 80

— — — — — — —

after pass 8: 13 20 40 45 50 58 61 71 87* 80

— — — — — — — —

after pass 9: 13 20 40 45 50 58 61 71 80 87*

— — — — — — — — —

Sorted array:

13 20 40 45 50 58 61 71 80 87

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