Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Selection Sort, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Selection Sort thông qua các phần sau.
Nội dung chính
1. Giới thiệu
Thuật toán sắp xếp lựa chọn(Selection Sort) sắp xếp một mảng bằng cách liên tục tìm phần tử tối thiểu (xét theo thứ tự tăng dần) từ phần không được sắp xếp và đặt nó ở đầu. Thuật toán duy trì hai mảng con trong một mảng nhất định.
1) Mảng con đã được sắp xếp.
2) Mảng con còn lại chưa được sắp xếp.
Trong mỗi lần lặp lại sắp xếp lựa chọn, phần tử tối thiểu (xét theo thứ tự tăng dần) từ mảng con chưa được sắp xếp được chọn và chuyển đến mảng con đã sắp xếp.
Ví dụ sau giải thích các bước trên:
arr [] = 64 25 12 22 11
// Tìm phần tử nhỏ nhất trong arr [0 ... 4]
// và đặt nó ở đầu
11 25 12 22 64
// Tìm phần tử nhỏ nhất trong arr [1 ... 4]
// và đặt nó ở đầu arr [1 ... 4]
11 12 25 22 64
// Tìm phần tử nhỏ nhất trong arr [2 ... 4]
// và đặt nó ở đầu arr [2 ... 4]
11 12 22 25 64
// Tìm phần tử nhỏ nhất trong arr [3 ... 4]
// và đặt nó ở đầu arr [3 ... 4]
11 12 22 25 64Hình ảnh luồng xử lý của Selection sort:
2. Code ví dụ trên nhiều ngôn ngữ lập trình
C++
// C++ program for implementation of selection sort
#include <bits/stdc++.h>
using namespace std;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
} C
// C program for implementation of selection sort
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Python
# Python program for implementation of Selection
# Sort
import sys
A = [64, 25, 12, 22, 11]
# Traverse through all array elements
for i in range(len(A)):
# Find the minimum element in remaining
# unsorted array
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
# Swap the found minimum element with
# the first element
A[i], A[min_idx] = A[min_idx], A[i]
# Driver code to test above
print ("Sorted array")
for i in range(len(A)):
print("%d" %A[i]),
Java
// Java program for implementation of Selection Sort
class SelectionSort
{
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;
}
}
// Prints the array
void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver code to test above
public static void main(String args[])
{
SelectionSort ob = new SelectionSort();
int arr[] = {64,25,12,22,11};
ob.sort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
} C#
// C# program for implementation
// of Selection Sort
using System;
class GFG
{
static 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;
}
}
// Prints the array
static void printArray(int []arr)
{
int n = arr.Length;
for (int i=0; i<n; ++i)
Console.Write(arr[i]+" ");
Console.WriteLine();
}
// Driver code
public static void Main()
{
int []arr = {64,25,12,22,11};
sort(arr);
Console.WriteLine("Sorted array");
printArray(arr);
}
} PHP
<?php
// PHP program for implementation
// of selection sort
function selection_sort(&$arr, $n)
{
for($i = 0; $i < $n ; $i++)
{
$low = $i;
for($j = $i + 1; $j < $n ; $j++)
{
if ($arr[$j] < $arr[$low])
{
$low = $j;
}
}
// swap the minimum value to $ith node
if ($arr[$i] > $arr[$low])
{
$tmp = $arr[$i];
$arr[$i] = $arr[$low];
$arr[$low] = $tmp;
}
}
}
// Driver Code
$arr = array(64, 25, 12, 22, 11);
$len = count($arr);
selection_sort($arr, $len);
echo "Sorted array : \n";
for ($i = 0; $i < $len; $i++)
echo $arr[$i] . " ";
// This code is contributed
// by Deepika Gupta.
?>
Kết quả:
Sorted array:
11 12 22 25 643. Độ phức tạp
Độ phức tạp thời gian: O (n2) vì có hai vòng lặp lồng nhau.
Không gian phụ trợ: O (1)
Điều tốt về sắp xếp lựa chọn là nó không bao giờ tạo ra nhiều hơn O (n) hoán đổi và có thể hữu ích khi ghi bộ nhớ là một hoạt động tốn kém.
4. Bài tập
Sắp xếp một mảng chuỗi bằng cách dùng Selection Sort
Bài giải
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
