Các thuật toán sắp xếp trong C

Posted on by adminChuyên mục:Kiến thức Internet

Thuật toán sắp xếp là một trong những loại thuật toán được sử dụng rất nhiều trong cuộc sống, đơn giản nó là các phương pháp sắp xếp lại dãy kí tự theo mong muốn của người lập trình.
Việc học các thuật toán nhuần nhuyễn sẽ giúp các bạn nâng cao tư duy giải quyết vấn đề bằng lập trình.

Bài này nằm trong serie Học lập trình C từ A tới Z

Tóm Tắt

Tổng quan chung

Sắp xếp tài liệu là một phần tất yếu trong việc nghiên cứu và phân tích tài liệu. Việc sắp xếp tài liệu giúp bạn nhanh gọn trực quan hóa và hiểu rõ hơn về tài liệu của mình, tổ chức triển khai và tìm kiếm tài liệu mà bạn muốn và ở đầu cuối là đưa ra quyết định hành động hiệu suất cao hơn .

Sắp xếp dữ liệu liên quan đến việc sắp xếp mảng theo một thứ tự nào đo chẳng hạn như tăng dần hoặc giảm dần. Các thuật toán sắp xếp cơ bản bao gồm:

  • Sắp xếp nổi bọt ( Bubble Sort )
  • Sắp xếp chèn ( Insertion Sort )
  • Sắp xếp chọn ( Selection Sort )
  • Sắp xếp trộn ( Merge Sort )
  • Sắp xếp nhanh ( Quick Sort )
  • Shell Sort
  • Sắp xếp đếm ( Counting Sort )
  • Sắp xếp theo cơ số ( Radix Sort )
  • Sắp xêp theo khối ( Bucket Sort )
  • Sắp xếp vun đống ( Heap Sort )

Sắp xếp nổi bọt ( Bubble Sort )

Sắp xếp nổi bọt là như thế nào

Sắp xếp nổi bọt là một giải thuật sắp xếp đơn thuần. Giải thuật sắp xếp này được thực thi dựa trên việc so sánh cặp thành phần liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự .
Giải thuật này không thích hợp sử dụng với những tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο ( n2 ) với n là số thành phần .
Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số những giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dầu số lần so sánh bằng nhau, nhưng do đổi chỗ hai thành phần kề nhau nên số lần đổi chỗ nhiều hơn .
Có hai chiêu thức trong sắp xếp nổi bọt được tiến hành :

  • Từ dưới lên trên ( Bottom – up ) : So sánh những giá trị lần lượt từ cuối mảng nếu nhỏ hơn thì từ từ cho lên trên .
  • Từ trên xuống : So sánh mở màn từ thành phần trên cùng, nếu thành phần lớn hơn sẽ bị chìm xuống dưới .

Ý tưởng bài toán :
sap xep noi bot bubble sort

Triển khai ý tưởng

Thuật toán sắp xếp nổi bọt thực thi sắp xếp dãy số bằng cách tái diễn việc làm đổi chỗ 2 số liên tục nhau nếu chúng đứng sai thứ tự ( số sau bé hơn số trước với trường hợp sắp xếp tăng dần ) cho đến khi dãy số được sắp xếp .

Giả sử chúng ta cần sắp xếp dãy số [5 1 4 2 8] này tăng dần.
Lần lặp đầu tiên:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Ở đây, thuật toán sẽ so sánh hai phần tử đầu tiên, và đổi chỗ cho nhau do 5 > 1.
( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Đổi chỗ do 5 > 4
( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Đổi chỗ do 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Ở đây, hai phần tử đang xét đã đúng thứ tự (8 > 5), vậy ta không cần đổi chỗ.

Lần lặp thứ 2:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Đổi chỗ do 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )
Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện.

Lần lặp thứ 3:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

  • PHƯƠNG PHÁP CHUNG :

  • Cho một mảng có n phần tử

  • Lặp lại các bước sau n-1 lần:

+ Với a [ i ] và a [ i + 1 ] :
\ Nếu a [ i ] lớn hơn a [ i + 1 ] thì đổi vị trí cho nhau

Cách viết thuật toán sắp xếp nổi bọt với C

Ví dụ 1 : Sắp xếp lại mảng có sẵn theo thứ thự nhỏ tới lớn dùng thuật toán sắp xếp nổi bọt

word image word image 1

Kết quả hiển thị :

word image 2

Ví dụ 2 : Chi tiết quy trình sắp xếp

#include 

#include 

#define MAX 10

int list[MAX] = {1,8,4,6,0,3,5,2,7,9};

void display(){

int i;

printf("[");

// Duyet qua tat ca phan tu

for(i = 0; i < MAX; i++){

printf("%d ",list[i]);

}


printf("]\n");

}

void bubbleSort() {

int temp;

int i,j;

bool swapped = false;

// lap qua tat ca cac so

for(i = 0; i < MAX-1; i++) {

swapped = false;

// vong lap thu hai

for(j = 0; j < MAX-1-i; j++) {

printf(" So sanh cac phan tu: [ %d, %d ] ", list[j],list[j+1]);

// kiem xa xem so ke tiep co nho hon so hien tai hay khong

// trao doi cac so.

// (Muc dich: lam noi bot (bubble) so lon nhat)

if(list[j] > list[j+1]) {

temp = list[j];

list[j] = list[j+1];

list[j+1] = temp;

swapped = true;

printf(" => trao doi [%d, %d]\n",list[j],list[j+1]);

}else {

printf(" => khong can trao doi\n");

}

}

// neu khong can trao doi nua, tuc la

// mang da duoc sap xep va thoat khoi vong lap.

if(!swapped) {

break;

}


printf("Vong lap thu %d#: ",(i+1));

display();

}

}

main(){

printf("Mang du lieu dau vao: ");

display();

printf("\n");


bubbleSort();

printf("\nMang sau khi da sap xep: ");

display();

}

Kết quả

Sắp xếp nổi bọt (Bubble Sort) trong C

Sắp xếp chèn ( Insertion Sort )

Thuật toán sắp xếp chèn là gì?

Sắp xếp chèn là một giải thuật sắp xếp dựa trên so sánh in-place. Ở đây, một list con luôn luôn được duy trì dưới dạng đã qua sắp xếp. Sắp xếp chèn là chèn thêm một thành phần vào list con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp sao cho vẫn bảo vệ rằng list con đó vẫn sắp theo thứ tự .
Với cấu trúc tài liệu mảng, tất cả chúng ta tưởng tượng là : mảng gồm hai phần : một list con đã được sắp xếp và phần khác là những thành phần không có thứ tự. Giải thuật sắp xếp chèn sẽ thực thi việc tìm kiếm liên tục qua mảng đó, và những thành phần không có thứ tự sẽ được vận động và di chuyển và được chèn vào vị trí thích hợp trong list con ( của cùng mảng đó ) .
Giải thuật này không thích hợp sử dụng với những tập dữ liệu lớn khi độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο ( n2 ) với n là số thành phần .
Một vài giải pháp được sử dụng trong sắp xếp chèn :

  • Đối với mỗi thành phần của mảng, đặt nó vào đúng vị trí giữa những thành phần khác được sắp xếp .
  • Khi thành phần sau cuối được đặt vào vị trí, mảng được sắp xếp xong .

Ý tưởng bài toán :
sap xep chen
Thuật toán sắp xếp chèn triển khai sắp xếp dãy số theo cách duyệt từng thành phần và chèn từng thành phần đó vào đúng vị trí trong mảng con ( dãy số từ đầu đến thành phần phía trước nó ) đã sắp xếp sao cho dãy số trong mảng sắp đã xếp đó vẫn bảo vệ đặc thù của một dãy số tăng dần .

  1. Khởi tạo mảng với dãy con đã sắp xếp có k = 1 thành phần ( thành phần tiên phong, thành phần có chỉ số 0 )
  2. Duyệt từng thành phần từ thành phần thứ 2, tại mỗi lần duyệt thành phần ở chỉ số i thì đặt thành phần đó vào một vị trí nào đó trong đoạn từ [ 0 … i ] sao cho dãy số từ [ 0 … i ] vẫn bảo vệ đặc thù dãy số tăng dần. Sau mỗi lần duyệt, số thành phần đã được sắp xếp k trong mảng tăng thêm 1 thành phần .
  3. Lặp cho tới khi duyệt hết toàn bộ những thành phần của mảng .

Sắp xếp chèn với ngôn ngữ C

Ví dụ minh họa : Sắp xếp mảng từ thấp đến cao dùng thuật toán sắp xếp chèn

word image 3 word image 4

Kết quả hiển thị :

word image 5

Ví dụ : Chi tiết quy trình sắp xếp chèn

#include 

#include 

#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count){

int i;




for(i = 0;i  0 && intArray[holePosition-1] > valueToInsert){

intArray[holePosition] = intArray[holePosition-1];

holePosition--;

printf(" Di chuyen phan tu : %d\n", intArray[holePosition]);

}

if(holePosition != i){

printf(" Chen phan tu : %d, tai vi tri : %d\n", valueToInsert,holePosition);

// chen phan tu tai vi tri chen

intArray[holePosition] = valueToInsert;

}

printf("Vong lap thu %d#:",i);

display();




}

}

main(){

printf("Mang du lieu dau vao: ");

display();

printline(50);

insertionSort();

printf("Mang sau khi da sap xep: ");

display();

printline(50);

}
  • Hiển thị :

Sắp xếp chèn (Insertion Sort) trong C

Sắp xếp chọn ( Selection Sort )

Thuật toán sắp xếp chọn là gì?

Giải thuật sắp xếp chọn (Selection Sort) là một giải thuật đơn giản. Giải thuật sắp xếp này là một giải thuật dựa trên việc so sánh in-place, trong đó danh sách được chia thành hai phần, phần được sắp xếp (sorted list) ở bên trái và phần chưa được sắp xếp (unsorted list) ở bên phải. Ban đầu, phần được sắp xếp là trống và phần chưa được sắp xếp là toàn bộ danh sách ban đầu.

Phần tử nhỏ nhất được lựa chọn từ mảng chưa được sắp xếp và được tráo đổi với phần bên trái nhất và thành phần đó trở thành thành phần của mảng được sắp xếp. Tiến trình này liên tục cho tới khi hàng loạt từng thành phần trong mảng chưa được sắp xếp đều được chuyển dời sang mảng đã được sắp xếp .

  • Ý tưởng bài toán

sap xep chon
Thuật toán sắp xếp chọn sẽ sắp xếp một mảng bằng cách đi tìm thành phần có giá trị nhỏ nhất ( giả sử với sắp xếp mảng tăng dần ) trong đoạn đoạn chưa được sắp xếp và đổi cho thành phần nhỏ nhất đó với thành phần ở đầu đoạn chưa được sắp xếp ( không phải đầu mảng ). Thuật toán sẽ chia mảng làm 2 mảng con

  1. Một mảng con đã được sắp xếp
  2. Một mảng con chưa được sắp xếp

Tại mỗi bước lặp của thuật toán, thành phần nhỏ nhất ở mảng con chưa được sắp xếp sẽ được chuyển dời về đoạn đã sắp xếp .

Sắp xếp chọn với ngôn ngữ C

Ví dụ minh họa : Sắp xếp mảng từ thấp tới cao với thuật toán sắp xếp chọn

word image 6 word image 7 word image 8

Kết quả hiển thị

word image 9

Ví dụ : Chi tiết cách hoạt động giải trí của sắp xếp chọn

#include 

#include 

#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count){

int i;




for(i = 0;i 
Hiển thị :

Sắp xếp chọn (Selection Sort) trong C


Sắp xếp trộn ( Merge Sort )


Thuật toán sắp xếp trộn là gì?


Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Conquer). Với độ phức tạp thời gian trường hợp xấu nhất là Ο(n log n) thì đây là một trong các giải thuật đáng được quan tâm nhất.

Giải thuật sắp xếp trộn chia mảng thành hai nửa liên tục, tới khi còn 1 phẩn tử và sau đó tích hợp chúng lại với nhau thành một mảng đã được sắp xếp .

    

  • Ý tưởng bài toán :
    • 


sap xep tron
Hình ảnh dưới đây từ wikipedia sẽ hiển thị cho bạn hàng loạt sơ đồ tiến trình của thuật toán merge sort cho mảng { 38, 27, 43, 3, 9, 82, 10 }. Nếu nhìn kỹ hơn vào sơ đồ này, tất cả chúng ta hoàn toàn có thể thấy mảng bắt đầu được lặp lại hành vi chia cho tới khi kích cỡ những mảng sau chia là 1 .
Khi size những mảng con là 1, tiến trình gộp sẽ mở màn thực thi gộp lại những mảng này cho tới khi hoàn thành xong và chỉ còn một mảng đã sắp xếp .

word image 10


Thuật toán sắp xếp trộn trong C

Ví dụ minh họa

#include 

#define max 10

int a[10] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };

int b[10];

void merging(int low, int mid, int high) {

int l1, l2, i;

for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {

if(a[l1] <= a[l2])

b[i] = a[l1++];

else

b[i] = a[l2++];

}

while(l1 <= mid)

b[i++] = a[l1++];

while(l2 <= high)

b[i++] = a[l2++];

for(i = low; i <= high; i++)

a[i] = b[i];

}

void sort(int low, int high) {

int mid;




if(low < high) {

mid = (low + high) / 2;

sort(low, mid);

sort(mid+1, high);

merging(low, mid, high);

}else {

return;

}

}

int main() {

int i;

printf("Danh sach truoc khi duoc sap xep\n");




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

printf("%d ", a[i]);

sort(0, max);

printf("\nDanh sach sau khi duoc sap xep\n");




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

printf("%d ", a[i]);

}


Hiện thị :


Sắp xếp trộn (Merge Sort) trong C


Sắp xếp nhanh ( Quick Sort )


Thuật toán sắp xếp nhanh là gì


Giải thuật sắp xếp nhanh (Quick Sort) là một giải thuật hiệu quả cao và dựa trên việc chia mảng dữa liệu thành các mảng nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng phần tử của mảng với một phần tử được chọn gọi là phần tử chốt (Pivot): một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và mảng còn lại bao gồm các phần tử lớn hơn hoặc bằng phần tử chốt.


    

  • Ý tưởng bài toán :
    • 



word image 11

Giống như Merge sort, thuật toán sắp xếp quick sort là một thuật toán chia để trị ( Divide and Conquer algorithm ). Nó chọn một thành phần trong mảng làm điểm ghi lại ( pivot ). Thuật toán sẽ triển khai chia mảng thành những mảng con dựa vào pivot đã chọn. Việc lựa chọn pivot ảnh hưởng tác động rất nhiều tới vận tốc sắp xếp. Nhưng máy tính lại không hề biết khi nào thì nên chọn theo cách nào. Dưới đây là một số ít cách để chọn pivot thường được sử dụng :


    

  1. Luôn chọn thành phần tiên phong của mảng .
    2. 

  2. Luôn chọn thành phần sau cuối của mảng. ( Được sử dụng trong bài viết này )
    3. 

  3. Chọn một thành phần random .
    4. 

  4. Chọn một thành phần có giá trị nằm giữa mảng ( median element ) .
    5. 



    

  • Tầm quan trọng của phân đoạn trong thuật toán Quick Sort
    • 



Mấu chốt chính của thuật toán quick sort là việc phân đoạn dãy số ( Xem hàm partition ( ) ). Mục tiêu của việc làm này là : Cho một mảng và một thành phần x là pivot. Đặt x vào đúng vị trí của mảng đã sắp xếp. Di chuyển tổng thể những thành phần của mảng mà nhỏ hơn x sang bên trái vị trí của x, và chuyển dời tổng thể những thành phần của mảng mà lớn hơn x sang bên phải vị trí của x .

Khi đó ta sẽ có 2 mảng con : mảng bên trai của x và mảng bên phải của x. Tiếp tục việc làm với mỗi mảng con ( chọn pivot, phân đoạn ) cho tới khi mảng được sắp xếp .


    

  • Thuật toán phân đoạn
    • 



Đặt pivot là thành phần sau cuối của dãy số arr. Chúng ta mở màn từ thành phần trái nhất của dãy số có chỉ số là left, và thành phần phải nhất của dãy số có chỉ số là right - 1 ( bỏ lỡ thành phần pivot ). Chừng nào left < right mà arr [ left ] > pivot và arr [ right ] < pivot thì đổi chỗ hai thành phần left và right. Sau cùng, ta đổi chỗ hai thành phần left và pivot cho nhau. Xem hình minh họa phía dưới. Khi đó, thành phần left đã đứng đúng vị trí và chia dãy số làm đôi ( bên trái và bên phải )
Minh họa quá trình phân đoạn trong thuật toán quick sort


Thuật toán sắp xếp nhanh trong C


Ví dụ minh họa


#include 

#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count){

int i;




for(i = 0;i  0 && intArray[--rightPointer] > pivot){

//khong lam gi

}

if(leftPointer >= rightPointer){

break;

}else{

printf(" Phan tu duoc trao doi :%d,%d\n",

intArray[leftPointer],intArray[rightPointer]);

swap(leftPointer,rightPointer);

}




}




printf(" Phan tu chot duoc trao doi :%d,%d\n", intArray[leftPointer],intArray[right]);

swap(leftPointer,right);

printf("Hien thi mang sau moi lan trao doi: ");

display();

return leftPointer;

}

// ham sap xep

void quickSort(int left, int right){

if(right-left <= 0){

return;

}else {

int pivot = intArray[right];

int partitionPoint = partition(left, right, pivot);

quickSort(left,partitionPoint-1);

quickSort(partitionPoint+1,right);

}

}

main(){

printf("Mang du lieu dau vao: ");

display();

printline(50);

quickSort(0,MAX-1);

printf("Mang sau khi da sap xep: ");

display();

printline(50);

}


    

  • Hiển thị :
    • 



Sắp xếp nhanh (Quick Sort) trong C


Shell Sort


Thuật toán sắp xếp Shell Sort là gì?


Shell Sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp xếp chèn (Insertion Sort). Giải thuật này khá hiệu quả với các tập dữ liệu có kích cỡ trung bình khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là O(n), với n là số phần tử. 


Giải thuật này tránh những trường hợp phải tráo đổi vị trí của hai thành phần xa nhau trong giải thuật sắp xếp chọn ( nếu như thành phần nhỏ hơn ở vị trí bên phải khá xa so với thành phần lớn hơn bên trái ) .


Đầu tiên, giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. Khoảng cách này còn được gọi là khoảng (interval) – là số vị trí từ phần tử này tới phần tử khác. Khoảng này được tính dựa vào các loại công thức sau


    

  • Shell’s original sequence: N/2, N/4, …, 1
    • 

  • Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2
    • 

  • Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1
    • 

  • Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
    • 

  • Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,...
    • 

  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....
    • 



Cách Shell Sort hoạt động giải trí với công thức Shell’s original sequence


Ví dụ sắp xết dãy a = [ 9, 1, 3, 7, 8, 4, 2, 6, 5 ] thành dãy không giảm .


word image 12


Với interval = 9/2 = 4, ta sẽ chia dãy thành những dãy con với những số cách nhau một khoảng chừng là interval : [ 9, 8, 5 ], [ 1, 4 ], [ 3, 2 ] và [ 7, 6 ] .


Sắp xếp những dãy con này theo cách sắp xếp chèn (Insertion Sort).


word image 13


Sau khi sắp xếp những dãy con dãy sẽ thành .


word image 14


Với interval = 9/4 = 2, ta sẽ chia dãy thành những dãy con với những số cách nhau một khoảng chừng là interval : [ 9, 8, 5 ], [ 1, 4 ], [ 3, 2 ] và [ 7, 6 ] .


word image 15


Sau khi sắp xếp những dãy con dãy sẽ thành .


word image 16


Với interval = 9/8 = 1, lúc này interval = 1 ta vận dụng sắp xếp chèn với cả dãy a :


word image 17


Dãy sau khi sắp xếp là :


word image 18


Sắp xếp Shell trong lập trình C


Ví dụ minh họa, bài tập vận dụng :


#include 

#include 

#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count){

int i;




for(i = 0;i  0) {

printf("Vong lap thu %d#:",i);

display();




for(outer = interval; outer < elements; outer++) {

valueToInsert = intArray[outer];

inner = outer;




while(inner > interval -1 && intArray[inner - interval]

>= valueToInsert) {

intArray[inner] = intArray[inner - interval];

inner -=interval;

printf(" Di chuyen phan tu :%d\n",intArray[inner]);

}




intArray[inner] = valueToInsert;

printf(" Chen phan tu :%d, tai vi tri :%d\n",valueToInsert,inner);

}




interval = (interval -1) /3;

i++;

}

}

int main() {

printf("Mang du lieu dau vao: ");

display();

printline(50);

shellSort();

printf("Mang ket qua: ");

display();

printline(50);

return 1;

}


    

  • Hiển thị :
    • 



Shell Sort trong C


Thuật toán sắp xếp đếm ( Counting Sort )


Thuật toán sắp xếp đếm là gì?


Counting sort là một thuật toán sắp xếp cực nhanh một mảng những thành phần mà mỗi thành phần là những số nguyên không âm ; Hoặc là một list những ký tự được ánh xạ về dạng số để sort theo bảng vần âm. Counting sort là một thuật toán sắp xếp những con số nguyên không âm, không dựa vào so sánh .

Trong khi những thuật toán sắp xếp tối ưu sử dụng so sánh có độ phức tạp O ( nlogn ) thì Counting sort chỉ cần O ( n ) nếu độ dài của list không quá nhỏ so với thành phần có giá trị lớn nhất .


    

  • Ý tưởng bài toán
    • 



Hình ảnh dưới đây cho tất cả chúng ta thấy cách hoạt động giải trí của thuật toán sắp xếp này .


Bước 1:


Trong bước tiên phong, chúng tôi đếm số lần Open của từng thành phần trong mảng cần sắp xếp A. Kết quả được lưu vào mảng C .


Diagram, application Description automatically generated


Bước 2: Ở bước này, chúng ta cần xem xét sửa đổi giá trị của C. C[i] thể hiện giới hạn trên của chỉ số của phần tử i sau khi sắp xếp.


Diagram Description automatically generated with medium confidence


Bước 3: Duyệt qua từng phần tử của A và đặt nó vào đúng chỉ số của mảng chứa các giá trị đã sắp xếp B dựa vào C.


Diagram Description automatically generated


Thuật toán sắp xếp đếm trong C


Ví dụ minh họa


#include 




// Function that sort the given input

void counting_sort(int input[], int n)

{

    int output[n]; // The output will have sorted input array

    int max = input[0];

    int min = input[0];




    int i;

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

    {

        if(input[i] > max)

            max = input[i]; // Maximum value in array

        else if(input[i] < min)

            min = input[i]; // Minimum value in array

    }




    int k = max - min + 1; // Size of count array




    int count_array[k]; // Create a count_array to store count of each individual input value

    for(i=0; i
Kết quả :

Sorted Array : 1  1  2  3  4  4  5  5  7

Ví Dụ 2 :

word image 19 word image 20 word image 21

Hiển thị :

word image 22


Thuật toán sắp xếp theo cơ số ( Radix Sort )


Thuật toán sắp xếp cơ số là gì?

Sắp xếp dựa trên cơ số là một kỹ thuật sắp xếp những thành phần bằng cách nhóm những chữ số riêng không liên quan gì đến nhau của một giá trị có cùng một vị trí. Sau đó, sắp xếp những thành phần theo thứ tự tăng hoặc giảm .
Sắp xếp cơ số thường được dùng để sắp xếp số có nhiều chữ số ( số lớn )
Giả sử, tất cả chúng ta có một mảng gồm 8 thành phần. Đầu tiên, tất cả chúng ta sẽ sắp xếp những thành phần dựa trên giá trị của vị trí đơn vị chức năng. Sau đó, tất cả chúng ta sẽ sắp xếp những thành phần dựa trên giá trị của vị trí thứ mười. Quá trình này liên tục cho đến vị trí ở đầu cuối .
Giả sử, ta có mảng khởi đầu là [ 121,432,564,23,1,45,788 ]. Nó được sắp xếp theo cơ số như trong hình bên dưới .

thuat-toan-sap-xep-theo-co-so

Cách thức hoạt động giải trí của thuật toán sắp xếp theo cơ số .

    

  • Bước 1 : tìm thành phần lớn nhất trong mảng, được gọi là biến max. Gọi X là số chữ số trong biến max. X hoàn toàn có thể đo lường và thống kê được bỏi vì tất cả chúng ta phải đi qua toàn bộ những vị trí quan trọng của toàn bộ những thành phần. Trong mảng [ 121,432,564,23,1,45,788 ], tất cả chúng ta có số lớn nhất là 788. Nó có 3 chữ số. Do đó, vòng lặp sẽ lên đến chữ số hàng trăm .
    • 

  • Bước 2 : giờ đây, ta lần lượt đi qua từng vị trí quan trọng .
    • 


Sử dụng bất kể kỹ thuật sắp xếp không thay đổi nào để sắp xếp những chữ số tại mỗi vị trí quan trọng. Chúng ta sử dụng sắp xếp đếm cho việc này .
Sắp xếp những thành phần dựa trên những chữ số hàng đơn vị chức năng ( X = 0 )

thuat-toan-sap-xep-theo-co-so-2

+ Sử dụng sắp xếp đếm để sắp xếp những thành phần dựa trên vị trí

    

  • Bước 3 : Bây giờ, ta sẽ sắp xếp những thành phần dựa trên những chữ số ở hàng chục .
    • 



thuat-toan-sap-xep-theo-co-so-3


    

  • Bước 4 : Cuối cùng, sắp xếp những thành phần dựa trên những chữ số ở vị trí hàng trăm .
    • 



thuat-toan-sap-xep-theo-co-so-4


Sắp xếp cơ số trong C


Ví dụ minh họaword image 23 word image 24 word image 25

Hiển thị :

word image 26


Thuật toán sắp xếp theo khối ( Bucket Sort )


Thuật toán sắp xếp theo khối là gì?

Thuật toán sắp xếp dựa trên khối hay Bucket Sort là một kỹ thuật sắp xếp những thành phần bằng cách chia những thành phần thành một số ít nhóm được gọi là khối hay Bucket khởi đầu. Các thành phần bên trong mỗi nhóm được sắp xếp bằng cách sử dụng bất kể thuật toán sắp xếp tương thích nào hoặc gọi đệ quy cho cùng một thuật toán .
Một số nhóm được tạo ra. Mỗi nhóm chứa đầy một loạt những thành phần nhất định. Các thành phần bên trong nhóm được sắp xếp bằng cách sử dụng bất kể thuật toán nào khác. Cuối cùng, những thành phần trong khối được tập hợp lại để có được mảng sắp xếp theo thứ tự nhất định .
Quá trình sắp xếp theo khối hoàn toàn có thể được hiểu là một cách tiếp cận phân loại và tập hợp. Đầu tiên những thành phần được phân loại thành những nhóm sau đó những thành phần của những nhóm được sắp xếp. Cuối cùng, những thành phần được tập hợp lại với nhau và được sắp xếp theo một trật tự .

thuat-toan-sap-xep-theo-khoi


thuat-toan-sap-xep-theo-khoi-2


thuat-toan-sap-xep-theo-khoi-3


Sắp xếp theo khối với C

Ví dụ minh họa

word image 28 word image 29 word image 30


    

  • 

  • 






word image 31


Thuật toán sắp xếp vun đống ( Heap Sort )


Thuật toán sắp xếp vun đống là gì?

Sắp xếp vun đống hay Heap Sort là một thuật toán sắp xếp phổ cập và hiệu suất cao trong lập trình. Học cách viết thuật toán sắp xếp vun đống yên cầu kiến thức và kỹ năng về hai loại cấu trúc tài liệu là mảng và cây .
Tập hợp số bắt đầu mà tất cả chúng ta muốn sắp xếp được tàng trữ trong một mảng, ví dụ, [ 12, 5, 78, 36, 25, 34 ] và sau khi sắp xếp, tất cả chúng ta nhận được một mảng đã sắp xếp là [ 5, 12, 25, 34, 36, 78 ]
Sắp xếp vun đống hoạt động giải trí bằng cách coi những thành phần của mảng như một loại cây nhị phân hoàn hảo đặc biệt quan trọng được gọi là Heap. Điều kiện tiên quyết là bạn phải biết về cấu trúc tài liệu Heap và cây nhị phân hoàn hảo .

Mối quan hệ giữa chỉ số của mảng và thành phần của cây

Một cây nhị phân hoàn hảo có một đặc tính mà tất cả chúng ta hoàn toàn có thể sử dụng để tìm nút con và nút cha của bất kể nút nào .
Nếu chỉ số của bất kể thành phần nào trong mảng là i, thành phần trong chỉ số 2 i + 1 sẽ trở thành nút con bên trái và thành phần trong chỉ số 2 i + 2 sẽ trở thành nút con bên phải. Ngoài ra, nút cha của bất kể thành phần nào tại chỉ số i được cho bởi số lượng giới hạn dưới là ( i-1 ) / 2 .

thuat-toan-sap-xep-vun-dong

Nút con bên trái của 3 ( Chỉ số là 0 )
= Phần tử tại chỉ số ( 2 * 0 + 1 )
= Phần tử trong chỉ số 1 = 12
Nút con bên phải của 3
= Phần tử tại chỉ số ( 2 * 0 + 2 )
= Phần tử trong chỉ số 2 = 9
Tương tự ,
Nút con bên trái của 14 ( Chỉ số 1 )
= Phần tử tại chỉ số ( 2 * 1 + 1 )
= Phần tử tại chỉ số 3 = 5
Nút con bên phải của 14
= Phần tử tại chỉ số ( 2 * 1 + 2 )
= Phần tử tại chỉ số 4 = 6
Ta sẽ xác nhận rằng những quy tắc sẽ luôn đúng cho việc tìm kiếm nút cha của bất kể nút nào
Nút cha của 11 ( Vị trí 2 )
= ( 2-1 ) / 2 = 1/2 = 0.5 ~ chỉ số 0
= 3
Nút cha của 14 ( Vị trí 1 )
= ( 1-1 ) / 2 = chỉ số 0
= 3
Hiểu được việc ánh xạ của những chỉ số của mảng với những vị trí trong cây là rất quan trọng để hiểu được phương pháp hoạt động giải trí của cấu trúc tài liệu Heap và cách nó được sử dụng để thực thi sắp xếp vun đống .

Cấu trúc tài liệu Heap là gì ?

Heap là một cấu trúc tài liệu đặc biệt quan trọng dựa trên cấu trúc cây. Cây nhị phân được cho là tuân theo cấu trúc tài liệu đống nếu
Nó là một cây nhị phân hoàn hảo .
Tất cả những nút trong cây tuân theo thuộc tính mà chúng lớn hơn thành phần con của chúng, tức là thành phần lớn nhất nằm ở nút gốc và những thành phần con của nó nhỏ hơn nút gốc, …. Một Heap như vậy được gọi là Max heap. Nếu thay vào đó, tổng thể những nút đều nhỏ hơn nút con của chúng, nó được gọi là Min Heap .
Hình bên dưới đây sẽ minh họa về cấu trúc tài liệu Max Heap và Min Heap .

thuat-toan-sap-xep-vun-dong-2


Làm thế nào để để tạo một cấu trúc Heap cho một cây ?

Bắt đầu từ một cây nhị phân hoàn hảo, tất cả chúng ta hoàn toàn có thể sửa đổi nó để trở thành Max Heap bằng cách triển khai một hàm có tên là Heapify trên tổng thể những thành phần không phải là nút lá của Heap. Vì hàm Heapify sử dụng đệ quy nên hoàn toàn có thể khó chớp lấy. Vì vậy, thứ nhất tất cả chúng ta hãy nghĩ về cách ta sẽ tạo Heap cho một cây chỉ với ba thành phần .
heapify ( array )
Root = array [ 0 ]
Largest = largest ( array [ 0 ], array [ 2 * 0 + 1 ]. array [ 2 * 0 + 2 ] )
if ( Root ! = Largest )
Swap ( Root, Largest )

thuat-toan-sap-xep-vun-dong-3


thuat-toan-sap-xep-vun-dong-4

Ví dụ trên đưa ra 2 trường hợp, một trong số đó có nút gốc là thành phần lớn nhất và tất cả chúng ta không cần phải làm gì cả. Và một thành phần khác trong đó nút gốc có một nút con lớn hơn và tất cả chúng ta cần hoán đổi để duy trì thuộc tính Max Heap .
Nếu ta đã thao tác với những thuật toán đệ quy, ta hoàn toàn có thể đã xác lập rằng đây phải là trường hợp cơ sở ( trường hợp để kết thúc lời gọi đệ quy ) .
Ví dụ 2 :

thuat-toan-sap-xep-vun-dong-5

Tuy nhiên, nút trên cùng không phải có cấu trúc Max Heap nhưng tổng thể những cây con đều là Max Heap .
Để duy trì thuộc tính Max Heap cho hàng loạt cây, tất cả chúng ta sẽ phải liên tục đẩy 2 cây xuống dưới cho đến khi nó đến đúng vị trí của nó .

thuat-toan-sap-xep-vun-dong-6


thuat-toan-sap-xep-vun-dong-7

Do đó, để duy trì thuộc tính Max Heap trong một cây mà cả hai cây con đều là Max Heap, tất cả chúng ta cần triển khai quy trình Heapify trên nút gốc nhiều lần cho đến khi nó lớn hơn cây con của nó hoặc nó trở thành một nút lá .
Chúng ta hoàn toàn có thể tích hợp cả hai điều kiện kèm theo này trong một hàm Heapify như sau :

void heapify(int arr[], int n, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {

swap(&arr[i], &arr[largest]);

heapify(arr, n, largest);

}

}


Hàm này hoạt động giải trí hiệu suất cao cho trường hợp cơ sở và cho một cây có kích cỡ bất kể. Do đó, tất cả chúng ta hoàn toàn có thể vận động và di chuyển nút gốc đến vị trí đúng chuẩn để duy trì trạng thái Max Heap cho bất kể size cây nào miễn là những cây con có cấu trúc Max Heap .


Xây dựng cấu trúc Max heap


Để tạo Max Heap từ bất kể cây nào, ta hoàn toàn có thể mở màn xếp từng cây con từ dưới lên và có được cấu trúc Max Heap sau khi hàm được vận dụng cho tổng thể những thành phần gồm có cả thành phần gốc .

Trong trường hợp của một cây hoàn hảo, chỉ số tiên phong của một nút không phải nút lá được cho bởi n / 2-1. Tất cả những nút khác sau đó là nút lá và do đó không cần phải tạo cấu trúc heap cho nó nữa .

Vì vậy, tất cả chúng ta hoàn toàn có thể thiết kế xây dựng một cấu trúc Max heap như sau :


for (int i = n / 2 - 1; i >= 0; i--)


 heapify(arr, n, i);


thuat-toan-sap-xep-vun-dong-8


thuat-toan-sap-xep-vun-dong-9


thuat-toan-sap-xep-vun-dong-10


thuat-toan-sap-xep-vun-dong-11


thuat-toan-sap-xep-vun-dong-12


Như bộc lộ trong sơ đồ trên, tất cả chúng ta sẽ mở màn bằng cách xếp vun đống cho những cây nhỏ nhất thấp nhất và từ từ vận động và di chuyển lên cho đến khi tất cả chúng ta đạt đến thành phần gốc .


Sắp xếp vun đống hoạt động giải trí như nào ?


Vì cây thỏa mãn nhu cầu thuộc tính Max Heap, nên thành phần lớn nhất được tàng trữ tại nút gốc .

Hoán đổi : Loại bỏ thành phần gốc và đặt ở cuối mảng ( vị trí thứ n ). Đặt thành phần sau cuối của cây ( đống ) vào chỗ trống .

Xóa : Giảm kích cỡ của Heap đi 1 đơn vị chức năng .

Heapify : Tạo cấu trúc Heap cho thành phần gốc để tất cả chúng ta có thành phần cao nhất ở nút gốc .

Quá trình này được lặp lại cho đến khi toàn bộ những thành phần của list được sắp xếp .


thuat-toan-sap-xep-vun-dong-13


thuat-toan-sap-xep-vun-dong-14


thuat-toan-sap-xep-vun-dong-15


thuat-toan-sap-xep-vun-dong-16


thuat-toan-sap-xep-vun-dong-17


thuat-toan-sap-xep-vun-dong-18


thuat-toan-sap-xep-vun-dong-19


thuat-toan-sap-xep-vun-dong-20


thuat-toan-sap-xep-vun-dong-21


thuat-toan-sap-xep-vun-dong-22


thuat-toan-sap-xep-vun-dong-23


thuat-toan-sap-xep-vun-dong-24


thuat-toan-sap-xep-vun-dong-25


thuat-toan-sap-xep-vun-dong-26


Sắp xếp vun đống với C


Ví dụ minh họa


for (int i = n - 1; i >= 0; i--) {

swap(&arr[0], &arr[i]);

//Tạo cấu trúc heap cho phần tử gốc để lấy ra phần tử lớn nhất

heapify(arr, i, 0);

}

#include 

void swap(int *a, int *b) {

int c = *a;

*a = *b;

*b = c;

}




void heapify(int arr[], int n, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {

swap(&arr[i], &arr[largest]);

heapify(arr, n, largest);

}

}

void sort_heap(int arr[], int n) {

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

for (int i = n - 1; i >= 0; i--) {

swap(&arr[0], &arr[i]);

heapify(arr, i, 0);

}

}




void print(int arr[], int n) {

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

printf("%d ", arr[i]);

printf("\n");

}

int main() {

int arr[] = {3, 14, 11, 7, 8, 12};

int n = sizeof(arr) / sizeof(arr[0]);

sort_heap(arr, n);

printf("Mảng sau khi sắp xếp là: \n");

print(arr, n);

}


Kết quả :


Mảng sau khi sắp xếp là:


3 7 8 11 12 14


Lời kết


Có rất nhiều loại thuật toán sắp xếp, trong bài này mình chỉ nêu ra 1 số ít chiêu thức thường sử dụng nhất và ứng dụng chúng với ngôn từ C. Nên nhớ những thuật toán hoàn toàn có thể vận dụng với bất kể ngôn từ nào, chỉ là cách tiến hành chúng trong mỗi ngôn từ sẽ hơi khác nhau mà thôi

Nếu bạn thấy bài viết này có ích hãy để lại phản hồi và đừng quên ra nhập Hội Anh Em Nghiện Lập trình nhé .






5/5 - ( 1 bầu chọn )

admin