JAVA - Tập 5: Data Structures và Algorithms

Tiếp tục với chuỗi seri ôn tập cấu trúc dữ liệu và giải thuật. Thuật toán hôm nay chúng ta sẽ tìm hiểu là Selection Sort và Insertion Sort. Đây là 2 thuật toán sắp xếp cuối cùng trong chuỗi seri tự học này của mình. Hi vọng mọi người sẽ đón nhận những chuỗi bài viết về chủ đề khác trong tương lai.

I, Selection Sort

Ý tưởng của nó là giề ?

Ý tưởng của thuật toán này vô cùng thủ công và dễ hiểu. Việc sắp xếp mảng được thực hiện bằng cách đi tìm phần tử có giá trị nhỏ nhất trong đoạn mảng chưa sắp xếp, sau đó đổi chỗ vị trí của phần tử đó cho phần tử đứng đầu đoạn chưa được sắp xếp. Như vậy, theo ta hiểu thì Selection Sort sẽ chia mảng ra 2 phần: Đã sắp xếp và Chưa sắp xếp.

Ví dụ:

Cho mảng như sau: arr[] = 62 24 15 22 1

// Tìm phần tử nhỏ nhất trong trong arr[0...4]
// và đổi chỗ nó với phần tử đầu tiên
[1] 24 15 22 62

// Tìm phần tử nhỏ nhất trong trong arr[1...4]
// và đổi chỗ nó với phần tử đầu tiên của arr[1...4]
1 [15] 24 22 62

// Tìm phần tử nhỏ nhất trong trong arr[2...4]
// và đổi chỗ nó với phần tử đầu tiên của arr[2...4]
1 15 [22] 24 62

// Tìm phần tử nhỏ nhất trong trong arr[3...4]
// và đổi chỗ nó với phần tử đầu tiên của arr[3...4]
11 12 22 [24] 62

Cuối cùng chúng ta có mảng đã được sắp xếp như sau:
11 12 22 24 62

Chương trình:

void sort(int arr[]) 
 { 
 int n = arr.length; 
  
 // One by one move boundary of unsorted subarray 
 for (int i = 0; i < n-1; i++) 
 { 
 // Find the minimum element in unsorted array 
 int min_idx = i; 
 for (int j = i+1; j < n; j++) 
    {
      if (arr[j] < arr[min_idx]) 
          min_idx = j; 
    }

 // Swap the found minimum element with the first 
 // element 
 int temp = arr[min_idx]; 
 arr[min_idx] = arr[i]; 
 arr[i] = temp; 
 } 

 } 

Độ phức tạp của thuật toán:

Do có sự xuất hiện của 2 vòng For lồng nhau nên mình mạnh dạn đoán là O(n2) (Và sự thật cũng như thế nha :3).

Nếu các bạn muốn tìm hiểu thêm về thuật toán Selection Sort thì xem tại đây nha.

II, Insertion Sort

Ý tưởng thuật toán:

Nếu như cái hay của Selection Sort chính là nằm ở chữ " Select ", nghĩa là trong mảng chưa được sắp xếp, thuật toán chỉ Select giá trị nhỏ nhất rồi tiến hành Swap, thì trong thuật toán Insertion Sort thuật toán lại tiến hành Swap mỗi khi trong mảng chưa được sắp xếp có xuất hiện giá trị nhỏ hơn bất kì một giá trị nào trong mảng đã được sắp xếp, để vẫn đảm bảo tính chất tăng dần của mảng. Các bước cụ thể như sau:

1. Khởi tạo mảng với dãy con đã sắp xếp có k = 1 phần tử (phần tử đầu tiên, phần tử có chỉ số 0)

2. Duyệt từng phần tử từ phần tử thứ 2, tại mỗi lần duyệt phần tử ở chỉ số i thì đặt phần tử đó vào một vị trí nào đó trong đoạn từ [0…i] sao cho dãy số từ [0…i] vẫn đảm bảo tính chất dãy số tăng dần. Sau mỗi lần duyệt, số phần tử đã được sắp xếp k trong mảng tăng thêm 1 phần tử.

3. Lặp cho tới khi duyệt hết tất cả các phần tử của mảng.

Ví dụ:

Chương trình:

/*Function to sort array using insertion sort*/
 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ó giá trị lớn hơn giá trị 
       key về sau một vị trí so với vị trí ban đầu
       của nó */
 while (j >= 0 && arr[j] > key) { 
 arr[j + 1] = arr[j]; 
 j = j - 1; 
 } 
 arr[j + 1] = key; 
 } 
 } 

Độ phức tạp của thuật toán:

Do có sự xuất hiện của vòng While lồng trong vòng For nên mình mạnh dạn đoán là O(n2) (Và sự thật cũng như thế nha :3).

Nếu các bạn muốn tìm hiểu thêm về thuật toán Selection Sort thì xem tại đây nha.

III, Tổng kết

Vậy là mình đã kết thúc chuỗi bài viết về cấu trúc dữ liệu và thuật toán dành cho ngôn ngữ Java. Hiện nay mình đang tập trung kiến thức về 1 ngôn ngữ mới khác là C# và hiện đã có nhiều ý tưởng nhưng vẫn chưa có đủ sâu và thời gian để viết. Mong các bạn đón đọc những bài viết hay ho tiếp theo của mình.

PEACE......