Selection Sort Là Gì

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 fundacionfernandovillalon.com 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.

Bạn đang xem: Selection sort là gì

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ó ở đầu11 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 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 C

// C program for implementation of selection sort #include 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 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 > A: min_idx = j # Swap the found minimum element with # the first element A, A = A, A # Driver code to test above print ("Sorted array") for i in range(len(A)): print("%d" %A), 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 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 PHP

$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 : "; for ($i = 0; $i Kết quả:

Sorted array: 11 12 22 25 64

3. Độ phức tạp