Các thuật toán sắp xếp phổ biến nhất hiện nay 2020

Các thuật toán sắp xếp là một trong những từ khóa được tìm kiếm nhiều nhất trên google về chủ đề Các thuật toán sắp xếp. Trong bài viết này, chatfuel.vn sẽ viết bài Các thuật toán sắp xếp phổ biến nhất hiện nay 2020

Merge sort

Giống như Quick sort, Merge sort là thuật toán chia để trị. Chia mảng thành những mảng nhỏ, sau đó gộp các mảng nhỏ đã sắp xếp lại với nhau.

Chẳng hạn như với mảng 3, 2., 4, 3. 9 8., 10, trình tự của merge sort sẽ như sau:

Khai triển thuật toán: Vì merge sort là một thuật toán sử dụng cực kì nhiều bộ nhớ nên sẽ vượt trội hơn khi dùng linked list, với linked list thì việc tách mảng và lưu trữ sẽ đơn giản hơn rất nhiều so với sử dụng mảng thường thường (Bạn cần có kiến thức căn bản về con trỏ trước khi coi đoạn code dưới). làm sao để bố trí một dự án React & Redux ?

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

// C++ code for linked list merged sort

#include

using namespacestd;

/* đường link list node */

classNode

public:

intdata;

Node*next;

;

/* function prototypes */

Node* SortedMerge(Node* avàNode*b);

void FrontBackSplit(Node* source, Node** frontRefvàNode**backRef);

voidMergeSort(Node**headRef)

(head->next==NULL))

return;

/* phân thành 2 linked list nhỏ dại a, b*/

FrontBackSplit(head, &a,&b);

/* Đệ quy để phân thành những linked list bé dại nhất */

MergeSort(&a);

MergeSort(&b);

/* answer = merge the two sorted lists together */

*headRef = SortedMerge(a,b);

/* Trộn 2 mảng đã được bố trí */

Node* SortedMerge(Node* a,Node*b)

Node*result=NULL;

if(a==NULL)

return(b);

elseif(b==NULL)

return(a);

if(a->data<=b->data)

result=a;

result->next = SortedMerge(a->next,b);

else

result=b;

result->next = SortedMerge(avàb->next);

return(result);

/* Chia đôi linked list source thành frontRef và backRef */

void FrontBackSplit(Node* sourcevà

Node** frontRef,Node**backRef)

Node*fast;

Node*slow;

slow=source;

fast=source->next;

/* Node fast di chuyển 2. bước thì Node slow di chuyể n được 1 bước */

while(fast!=NULL)

fast=fast->next;

if(fast!=NULL)

slow=slow->next;

fast=fast->next;

/* sau cuối Note slow sẽ là Node ở giữa */

*frontRef=source;

*backRef=slow->next;

slow->next=NULL;

voidprintList(Node*node)

while(node!=NULL)

cout<<node->data<<” “;

node=node->next;

/* Hàm thêm 1 node vào đầu mỗi linked list */

void push(Node** head_refvàintnew_data)

Node*new_node=newNode();

new_node->data=new_data;

new_node->next=(*head_ref);

(*head_ref)=new_node;

intmain()

Node*a=NULL;

/* tạo linked list: 2->3->20->5->10->15 */

push(&a,15);

push(&a,10);

push(&a, 5.);

push(&avà 2.);

push(&avà 3);

push(&a, 2);

/* sử dụng merge sort */

MergeSort(&a);

cout<<“Sorted Linked List is: \n”;

printList(a);

return0;

// This is code is contributed by rathbhupendra

Counting sort

Nâng cao, phát triển sự nghiệp của bạn trong kiểm thử ứng dụng

Counting sort là một kỹ thuật sắp xếp các đối tượng mục tiêu trong một phạm vị cụ thể. Nó hoạt động bằng việc đếm số lượng các đôi tượng có giá trị giống nhau. Sau đấy dùng một chút toán học để tính toán địa điểm cuối cùng của đối tượng mục tiêu đó.

Độ khó khăn của thuật toán này là O(n+k) với n là số lượng đối lượng, k là phạm vị giá trị của n đối tượng mục tiêu.

Hãy nghiên cứu thông qua 1 ví dụ:

Phạm vị giá trị k 10, giá trị của n nằm tại đoạn từ [0và 9].

Input: 1và 4và 1và 2, 7.và 5, 2.

1) Đếm số lượng các đối tượng có giá trị giống nhau.

Index: 0 1 2 3. 4 5. 6. 7 8. 9.

Count: 0 2 2 0 1 1 0 1 0 0

2.)Sửalạigiátrịcủamảng Count sao cho giátrịtạimỗivịtríisẽbằngtổng giátrịtạivịtríi+giátrịtạivịtríi-1.

Index: 0 1 2 3. 4 5. 6. 7 8. 9.

Count: 0 2. 4 4 5. 6 6. 7. 7. 7

Giá trị của mảng Count sẽ chỉ ra vị trí cuối cùng của các đối tượng.

3.) Sắp xếp lại các phần tử vào mảng Output.

Với Input là: 1, 4., 1, 2và 7, 5.và 2 Vị trí của 1 là 2 trong mảng Output.

Giảmgiátrịtạivịtrí1củamảng Count xuống1đơnvị

Giá tiếp theo là 4., vị trí tại mảng Output là 5. Giảm giá trị tại vị trí 4 của mảng Count xuống 1 đơn vị

Cứ như vậy và ta sẽ thu được kết quả của mảng Output là : 1, 1và 2, 2.và 4, 5., 7.

Triển khai thuật toán:

// C++ Program for counting sort

#include

using namespacestd;

k = 256

#define RANGE 255

voidcountSort(chararr[])

// Mảng Output

charoutput[strlen(arr)];

// Mảng count với 256 phần tử từ 0-255 với giá trị là 0 trong mỗi địa điểm

int count[RANGE + 1],i;

memset(count, 0vàsizeof(count));

// Đếm số lượng đối tượng có cùng giá trị và lưu kết quả vào mảng count

for(i=0;arr[i];++i)

++count[arr[i]];

// điều chỉnh giá trị của mảng count

for(i=1;i<=RANGE;++i)

count[i]+=count[i-1];

// tạo mảng Output

for(i=0;arr[i];++i)

output[count[arr[i]]-1]=arr[i];

–count[arr[i]];

for(i=0;arr[i];++i)

arr[i]=output[i];

// Driver code

intmain()

chararr[]=”geeksforgeeks”;

countSort(arr);

cout<<“Sorted character array is “<<arr;

return0;

Đây chính là một đoạn code sắp đặt mảng các ký tự, thuật toán cũng có thể được sử dụng để sắp đặt mảng những số nguyên. Với mảng các số nguyên gồm có cả số âm , dương thì cần phải thay đổi thuật toán 1 chút. Lí do là vì tại c++ bạn không thể truy xuất giá trị trong ví trí âm tại mảng. Để giải quyết lỗi lo này bạn cần tính lại khoảng k , xây dựng lại mảng count sao cho phần tử bé dại nhất ở trị trí 0.

Xem thêm: Hướng dẫn cách lập trình trí tuệ nhân tạo Python cơ bản mới nhất 2020

Radix sort

Các thuật toán quen thuộc như quick sort, merge sort, heap sort,… là những thuật toán bố trí dựa vào giá trị của những phép so sánh, độ phức tạo của những thuật toán này không thể tốt hơn O(nLogn). Còn với thuật toán counting sort ở trên, là một thuật toán tuyến tính với độ khó khăn là O(n+k). trong trường hợp k bằng n*n thì counting sort là một lựa chọn tồi. Radix sort là một xác định tốt trong TH này.

Tư tưởng của thuật toán này là bố trí các số theo giá trị của hàng chục, hàng trăm, hàng nghìn, …

Có thể bạn quan tâm: Augmented Reality là gì? Xu hướng tương tác thực tế thời đại số 2020Ví dụ:

với một mảng các số 170và 4.và 7, 9và 802, 2., 2, 6

Đầu tiên sắp xếp theo hàng đơn vị

170, 9, 802, 2, 2.và 4và 7, 6.

0 0 2. 2. 4 5. 5 6

Tiếp theo đến hàng chục

802, 2và 2., 4và 6.và 170, 7., 9

0 0 2. 4 6. 7 7 9

Cứ như vậy sẽ thu được kết quả cuối cùng

2.và 2., 4., 6, 7., 9., 170và 802

Triển khai thuật toán:

// C++ implementation of Radix Sort

#include

using namespacestd;

// Tìm giá trị lớn nhất trong mảng

int getMax(int arr[]vàintn)

intmx=arr[0];

for(inti=1;i<n;i++)

if(arr[i]>mx)

mx=arr[i];

returnmx;

// dùng thuật toán counting sort để bố trí lại vị trí của các đôi tượng theo giá trị hàng đơn vị, hàng chục,…

void countSort(int arr[]và int nvàintexp)

intoutput[n];

int ivàcount[10]=0;

for(i=0;i<n;i++)

count[(arr[i]/exp)%10]++;

for(i=1;i<10;i++)

count[i]+=count[i-1];

for(i=n-1;i>=0;i–)

output[count[(arr[i]/exp)%10]-1]=arr[i];

count[(arr[i]/exp)%10]–;

for(i=0;i<n;i++)

arr[i]=output[i];

// Radix Sort

void radixsort(int arr[],intn)

int m = getMax(arr,n);

// sử dụng couting sort để sắp đặt lại địa điểm những đôi tượng

for(intexp=1;m/exp>0;exp *=10)

countSort(arr, n,exp);

void print(int arr[]vàintn)

for(inti=0;i<n;i++)

cout<<arr[i]<<” “;

intmain()

int arr[] = 170và 4và 7và 9, 802và 2.và 2, 6.;

intn=sizeof(arr)/sizeof(arr[0]);

radixsort(arr,n);

print(arrvàn);

return0;

Nguồn:https://techtalk.vn/

Trending Tags

Trending Tags

Các thuật toán sắp xếp phổ biến nhất hiện nay 2020

Merge sort

Counting sort

Radix sort

Hướng dẫn tự lập trình Android cơ bản từ A đến Z

Native App là gì? Ưu và nhược điểm khi dùng Native App hiện nay 2020

CODER

Chuyên mục

Phần mềm - Công cụ

Liên kết