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

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ổng quan chung

Sắp xếp dữ liệu là một phần tất yếu trong việc phân tích dữ liệu. Việc sắp xếp dữ liệu giúp bạn nhanh chóng trực quan hóa và hiểu rõ hơn về dữ liệu của mình, tổ chức và tìm kiếm dữ liệu mà bạn muốn và cuối cùng là đưa ra quyết định hiệu quả 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 giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử 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 các 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à Ο(n²) với n là số phần tử.

Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các 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ù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.

Có hai phương pháp trong sắp xếp nổi bọt được triển khai:

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

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

Triển khai ý tưởng

Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp 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

Kết quả hiển thị:

 

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

#include <stdio.h>

#include <stdbool.h>

#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 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 danh sách 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 phần tử vào danh sách con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo thứ tự.

Với cấu trúc dữ liệu mảng, chúng ta tưởng tượng là: mảng gồm hai phần: một danh sách con đã được sắp xếp và phần khác là các phần tử không có thứ tự. Giải thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các phần tử không có thứ tự sẽ được di chuyển và được chèn vào vị trí thích hợp trong danh sách con (của cùng mảng đó).

Giải thuật này không thích hợp sử dụng với các 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à Ο(n²) với n là số phần tử.

Một vài phương pháp được sử dụng trong sắp xếp chèn:

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

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

Thuật toán sắp xếp chèn thực hiện sắp xếp dãy số theo cách duyệt từng phần tử và chèn từng phần tử đó vào đúng vị trí trong mảng con(dãy số từ đầu đến phần tử phía trước nó) đã sắp xếp sao cho dãy số trong mảng sắp đã xếp đó vẫn đảm bảo tính chất 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 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.

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

Kết quả hiển thị:

 

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

#include <stdio.h>

#include <stdbool.h>

#define MAX 7

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

void printline(int count){

int i;




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

printf("=");

}




printf("=\n");

}

void display(){

int i;

printf("[");




// duyet qua tat ca phan tu

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

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

}




printf("]\n");

}

void insertionSort(){

int valueToInsert;

int holePosition;

int i;




// lap qua tat ca cac so

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




// chon mot gia tri de chen

valueToInsert = intArray[i];




// lua chon vi tri de chen

holePosition = i;




// kiem tra xem so lien truoc co lon hon gia tri duoc chen khong

while (holePosition > 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 (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à phần tử đó trở thành phần tử của mảng được sắp xếp. Tiến trình này tiếp tục cho tới khi toàn bộ từng phần tử trong mảng chưa được sắp xếp đều được di chuyển sang mảng đã được sắp xếp.

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

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 phần tử 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 phần tử nhỏ nhất đó với phần tử ở đầ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, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển 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

Kết quả hiển thị

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

#include <stdio.h>

#include <stdbool.h>

#define MAX 7

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

void printline(int count){

int i;




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

printf("=");

}




printf("=\n");

}

void display(){

int i;

printf("[");




// duyet qua tat ca phan tu

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

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

}




printf("]\n");

}

void selectionSort(){

int indexMin,i,j;




// lap qua ta ca cac so

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




// thiet lap phan tu hien tai la min

indexMin = i;




// kiem tra phan tu hien tai co phai la nho nhat khong

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

if(intArray[j] < intArray[indexMin]){

indexMin = j;

}

}

if(indexMin != i){

printf("Trao doi phan tu: [ %d, %d ]\n" , intArray[i], intArray[indexMin]);




// Trao doi cac so

int temp = intArray[indexMin];

intArray[indexMin] = intArray[i];

intArray[i] = temp;

}

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

display();

}

}

main(){

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

display();

printline(50);

selectionSort();

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

display();

printline(50);

}

Hiển thị:

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 đó kết 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:

Hình ảnh dưới đây từ wikipedia sẽ hiển thị cho bạn toàn bộ 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, chúng ta có thể thấy mảng ban đầu được lặp lại hành động chia cho tới khi kích thước các mảng sau chia là 1.

Khi kích thước các mảng con là 1, tiến trình gộp sẽ bắt đầu thực hiện gộp lại các mảng này cho tới khi hoàn thành và chỉ còn một mảng đã sắp xếp.

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

Ví dụ minh họa

#include <stdio.h>

#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 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:

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 phần tử trong mảng làm điểm đánh dấu(pivot). Thuật toán sẽ thực hiện chia mảng thành các mảng con dựa vào pivot đã chọn. Việc lựa chọn pivot ảnh hưởng rất nhiều tới tốc độ sắp xếp. Nhưng máy tính lại không thể biết khi nào thì nên chọn theo cách nào. Dưới đây là một số cách để chọn pivot thường được sử dụng:

1. Luôn chọn phần tử đầu tiên của mảng.
2. Luôn chọn phần tử cuối cùng của mảng. (Được sử dụng trong bài viết này)
3. Chọn một phần tử random.
4. Chọn một phần tử có giá trị nằm giữa mảng(median element).

• 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 công việc này là: Cho một mảng và một phần tử x là pivot. Đặt x vào đúng vị trí của mảng đã sắp xếp. Di chuyển tất cả các phần tử của mảng mà nhỏ hơn x sang bên trái vị trí của x, và di chuyển tất cả các phần tử 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 công việc 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à phần tử cuối cùng của dãy số arr. Chúng ta bắt đầu từ phần tử trái nhất của dãy số có chỉ số là left, và phần tử phải nhất của dãy số có chỉ số là right -1(bỏ qua phần tử pivot). Chừng nào left < right mà arr[left] > pivot và arr[right] < pivot thì đổi chỗ hai phần tử left và right. Sau cùng, ta đổi chỗ hai phần tử left và pivot cho nhau. Xem hình minh họa phía dưới. Khi đó, phần tử left đã đứng đúng vị trí và chia dãy số làm đôi(bên trái và bên phải)

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

Ví dụ minh họa

#include <stdbool.h>

#define MAX 7

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

void printline(int count){

int i;




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

printf("=");

}




printf("=\n");

}

// ham hien thi cac phan tu

void display(){

int i;

printf("[");




// duyet qua moi phan tu

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

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

}




printf("]\n");

}

// ham de trao doi gia tri

void swap(int num1, int num2){

int temp = intArray[num1];

intArray[num1] = intArray[num2];

intArray[num2] = temp;

}

// ham de chia mang thanh 2 phan, su dung phan tu chot (pivot)

int partition(int left, int right, int pivot){

int leftPointer = left -1;

int rightPointer = right;

while(true){




while(intArray[++leftPointer] < pivot){

//khong lam gi

}




while(rightPointer > 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ị:

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 các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử 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, …, (3^k – 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 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.

Với interval = 9/2 = 4, ta sẽ chia dãy thành các dãy con với các số cách nhau một khoả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).

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

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

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

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

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

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 <stdio.h>

#include <stdbool.h>

#define MAX 7

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

void printline(int count){

int i;




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

printf("=");

}




printf("=\n");

}

//ham hien thi cac phan tu

void display(){

int i;

printf("[");




// duyet qua tat ca phan tu

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

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

}




printf("]\n");

}

//ham sap xep

void shellSort(){

int inner, outer;

int valueToInsert;

int interval = 1;

int elements = MAX;

int i = 0;




while(interval <= elements/3) {

interval = interval*3 +1;

}

while(interval > 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ị:

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 các phần tử mà mỗi phần tử là các số nguyên không âm; Hoặc là một danh sách các ký tự được ánh xạ về dạng số để sort theo bảng chữ cái. Counting sort là một thuật toán sắp xếp các con số nguyên không âm, không dựa vào so sánh.

Trong khi các 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 danh sách không quá nhỏ so với phần tử có giá trị lớn nhất.

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

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

Bước 1:

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

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.

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.

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

Ví dụ minh họa

#include <stdio.h>




// 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; i++)

        count_array[i]=0;




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

        count_array[input[i] - min]++; // Store count of each individual input value




    /* Change count_array so that count_array now contains actual

     position of input values in output array */

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

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




    // Populate output array using count_array and input array

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

    {

        output[count_array[input[i] - min] - 1] = input[i];

        count_array[input[i] - min]--;

    }




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

        input[i] = output[i]; // Copy the output array to input, so that input now contains sorted values




}







// Driver program to test above function

int main()

{

    int n = 9, i;




    int input[] = {1, 5, 2, 7, 3, 4, 4, 1, 5};




    counting_sort(input, n);




    printf("Sorted Array : ");

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

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




    return 0;

}

Kết quả:

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

Ví Dụ 2:

Hiển thị:

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 các phần tử bằng cách nhóm các chữ số riêng lẻ của một giá trị có cùng một vị trí. Sau đó, sắp xếp các phần tử 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ử, chúng ta có một mảng gồm 8 phần tử. Đầu tiên, chúng ta sẽ sắp xếp các phần tử dựa trên giá trị của vị trí đơn vị. Sau đó, chúng ta sẽ sắp xếp các phần tử dựa trên giá trị của vị trí thứ mười. Quá trình này tiếp tục cho đến vị trí cuối cùng.

Giả sử, ta có mảng ban đầ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.

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

• Bước 1: tìm phần tử 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 có thể tính toán được bỏi vì chúng ta phải đi qua tất cả các vị trí quan trọng của tất cả các phần tử. Trong mảng [121,432,564,23,1,45,788], 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: bây giờ, 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 ổn định nào để sắp xếp các 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 các phần tử dựa trên các chữ số hàng đơn vị (X=0)

+ Sử dụng sắp xếp đếm để sắp xếp các phần tử dựa trên vị trí

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

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

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

Ví dụ minh họa

Hiển thị:

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 các phần tử bằng cách chia các phần tử thành một số nhóm được gọi là khối hay Bucket ban đầu. Các phần tử 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 phù hợp 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 các phần tử nhất định. Các phần tử 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, các phần tử 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 có thể được hiểu là một cách tiếp cận phân chia và tập hợp. Đầu tiên các phần tử được phân chia thành các nhóm sau đó các phần tử của các nhóm được sắp xếp. Cuối cùng, các phần tử được tập hợp lại với nhau và được sắp xếp theo một trật tự.

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

Ví dụ minh họa

 

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ổ biến và hiệu quả trong lập trình. Học cách viết thuật toán sắp xếp vun đống đòi hỏi kiến thức về hai loại cấu trúc dữ liệu là mảng và cây.

Tập hợp số ban đầu mà chúng ta muốn sắp xếp được lưu trữ trong một mảng, ví dụ, [12, 5, 78, 36, 25, 34] và sau khi sắp xếp, 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 bằng cách coi các phần tử của mảng như một loại cây nhị phân hoàn chỉnh đặc biệt đượ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 dữ liệu Heap và cây nhị phân hoàn chỉnh.

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

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

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 các 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 các chỉ số của mảng với các vị trí trong cây là rất quan trọng để hiểu được cách thức hoạt động của cấu trúc dữ liệu Heap và cách nó được sử dụng để thực hiện sắp xếp vun đống.

Cấu trúc dữ liệu Heap là gì?

Heap là một cấu trúc dữ liệu đặc biệt 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 dữ liệu đống nếu

Nó là một cây nhị phân hoàn chỉnh.

Tất cả các nút trong cây tuân theo thuộc tính mà chúng lớn hơn phần tử con của chúng, tức là phần tử lớn nhất nằm ở nút gốc và các phần tử 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ất cả các 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 dữ liệu Max Heap và Min Heap.

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 chỉnh, chúng ta có thể sửa đổi nó để trở thành Max Heap bằng cách thực hiện một hàm có tên là Heapify trên tất cả các phần tử không phải là nút lá của Heap. Vì hàm Heapify sử dụng đệ quy nên có thể khó nắm bắt. Vì vậy, trước tiên chúng ta hãy nghĩ về cách ta sẽ tạo Heap cho một cây chỉ với ba phần tử.

heapify(array)

Root = array[0]

Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])

if(Root != Largest)

Swap(Root, Largest)

Ví dụ trên đưa ra 2 trường hợp, một trong số đó có nút gốc là phần tử lớn nhất và chúng ta không cần phải làm gì cả. Và một phần tử khác trong đó nút gốc có một nút con lớn hơn và chúng ta cần hoán đổi để duy trì thuộc tính Max Heap.

Nếu ta đã làm việc với các thuật toán đệ quy, ta có thể đã xác định 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:

Tuy nhiên, nút trên cùng không phải có cấu trúc Max Heap nhưng tất cả các cây con đều là Max Heap.

Để duy trì thuộc tính Max Heap cho toàn bộ cây, chúng ta sẽ phải tiếp tục đẩy 2 cây xuống dưới cho đến khi nó đến đúng vị trí của nó.

Do đó, để duy trì thuộc tính Max Heap trong một cây mà cả hai cây con đều là Max Heap, chúng ta cần thực hiện quá 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 có thể kết hợp cả hai điều kiện 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 hiệu quả cho trường hợp cơ sở và cho một cây có kích thước bất kỳ. Do đó, chúng ta có thể di chuyển nút gốc đến vị trí chính xác để duy trì trạng thái Max Heap cho bất kỳ kích thước cây nào miễn là các 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 có thể bắt đầu 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 áp dụng cho tất cả các phần tử bao gồm cả phần tử gốc.

Trong trường hợp của một cây hoàn chỉnh, chỉ số đầu tiên của một nút không phải nút lá được cho bởi n/2-1. Tất cả các 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, chúng ta có thể 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);

Như thể hiện trong sơ đồ trên, chúng ta sẽ bắt đầu bằng cách xếp vun đống cho các cây nhỏ nhất thấp nhất và dần dần di chuyển lên cho đến khi chúng ta đạt đến phần tử gốc.

Sắp xếp vun đống hoạt động như nào?

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

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

Xóa: Giảm kích thước của Heap đi 1 đơn vị.

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

Quá trình này được lặp lại cho đến khi tất cả các phần tử của danh sách được sắp xếp.

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 <stdio.h>

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 một số phương pháp thường sử dụng nhất và ứng dụng chúng với ngôn ngữ C. Nên nhớ các thuật toán có thể áp dụng với bất kì ngôn ngữ nào, chỉ là cách triển khai chúng trong mỗi ngôn ngữ sẽ hơi khác nhau mà thôi