10 Thuật toán sắp xếp cơ bản

Trong khoa học máy tính và trong toán học, thuật toán sắp xếp được sử dụng để sắp xếp các phần tử của một danh sách (hoặc một mảng) theo thứ tự (tăng hoặc giảm).

Dưới đây là 10 thuật toán sắp xếp cơ bản mà mình muốn giới thiệu đến các bạn.

Sắp xếp chọn – Selection sort

Sắp xếp chọn (selection sort) là phương pháp sắp xếp bằng cách chọn phần tử bé nhất xếp vào vị trí thứ nhất, tương tự với các phần tử nhỏ thứ hai, thứ ba,…

Ví dụ: Sắp xếp dãy 5, 4, -3, 11, 1 theo chiều tăng dần

Thuật toán selection sort
Thuật toán selection sort
#include <stdio.h>
#include <conio.h>

void swap(int* a, int* b);
void SelSort(int arr[], int N);
void disArr(int arr[], int N);

void main()
{
    int A[] = {0, -2, -5, 11, 5, 8, 2, 4, 24, 100, 34};
    int sz = sizeof(A)/sizeof(int);
    SelSort(A, sz);
    disArr(A, sz);
    getch();
}

// Selection sort
void SelSort(int arr[], int N)
{
    int i, j, idx, temp;
    for (i = 0; i < N-1; i++)
    {
        idx = i;
        for (j = i+1; j < N; j++)
        {
            if (arr[i] < arr[j])
            {
                idx = j;
            }
        }
        swap(&arr[i], &arr[idx]);
    }
}

void swap(int* a, int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void disArr(int arr[], int N)
{
    int i;
    for (i = 0; i < N; i++)
    {
        printf("%d\t", arr[i]);
    }
}

Kết quả:

Sắp xếp dãy bằng thuật toán selection sort
Sắp xếp dãy bằng thuật toán selection sort

Sắp xếp chèn – Insertion sort

Sắp xếp chèn (insertion sort) là thuật toán sắp xếp cho một dãy đã có thứ tự. Chèn thêm một phần tử vào vị trí thích hợp của dãy số đã sắp xếp sao cho dãy số vẫn là dãy sắp xếp có thứ tự.

Ví dụ: Sắp xếp dãy  theo chiều tăng dần

Sắp xếp chèn Insertion sort
Sắp xếp chèn Insertion sort
#include <stdio.h>
#include <conio.h>

void InsertSort(int arr[], int N);
void disArr(int arr[], int N);

void main()
{
    int A[] = {0, -2, -5, 11, 5, 8, 2, 4, 24, 100, 34};
    int sz = sizeof(A)/sizeof(int);
    InsertSort(A, sz);
    disArr(A, sz);
    getch();
}

// Insertion sort
void InsertSort(int arr[], int N)
{
    int i, j, temp;
    for (i = 1; i < N; i++)
    {
        j = i - 1;
        temp = arr[i];
        while(arr[j] > temp && j >= 0)
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }
}

void disArr(int arr[], int N)
{
    int i;
    for (i = 0; i < N; i++)
    {
        printf("%d\t", arr[i]);
    }
}

Kết quả:

Sắp xếp dãy bằng thuật toán Insertion sort
Sắp xếp dãy bằng thuật toán Insertion sort

Sắp xếp nổi bọt – Bubble sort

Sắp xếp nổi bọt (bubble sort) là phương pháp sắp xếp đơn giản, dễ hiểu thường được dạy trong khoa học máy tính. Nó so sánh hai phần tử cuối, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử tiếp theo cho đến cuối đầu dãy số. Sau đó nó quay lại với hai phần tử cuối cho đến khi không còn cần phải đổi chỗ nữa.

Bước 1: tại bước này, khi duyệt từ cuối dãy lên, các cặp cần phải đổi chỗ (98, 6), (49, 6), (17, 6), (32, 6). Phần tử 6 nổi lên vị trí đầu tiên

Bước 1: Sắp xếp Bublesort
Bước 1: Sắp xếp Bubble sort

Bước 2: tại bước này, khi duyệt từ cuối dãy lên, các cặp cần phải đổi chỗ (98, 25), (49, 25), (17, 32). Phần tử 17 nổi lên vị trí thứ 2

Bước 2: Sắp xếp Bubblesort
Bước 2: Sắp xếp Bubblesort

Bước 3: tại bước này, khi duyệt từ cuối dãy lên, các cặp cần phải đổi chỗ (98, 53), (32, 25). Phần tử 25 nổi lên vị trí thứ 3

Bước 3: Sắp xếp Bubble sort
Bước 3: Sắp xếp Bubble sort

Bước 4: tại bước này, khi duyệt từ cuối dãy lên, cặp cần phải đổi chỗ (98, 61).

Bước 4: Sắp xếp Bubble sort
Bước 4: Sắp xếp Bubble sort

#include <stdio.h>
#include <conio.h>

void swap(int *a, int* b);
void BubbleSort(int arr[], int N);
void disArr(int arr[], int N);

void main()
{
    int A[] = {0, -2, -5, 11, 5, 8, 2, 4, 24, 100, 34};
    int sz = sizeof(A)/sizeof(int);
    BubbleSort(A, sz);
    disArr(A, sz);
    getch();
}

// Bubble sort
void BubbleSort(int arr[], int N)
{
    int i, j;
    for (i = 0; i < N; i++)
    {
        for (j = N-1; j > i; j--)
        {
            if(arr[j] < arr[j-1])
                swap(&arr[j], &arr[j-1]);
        }
    }
}

void swap(int *a, int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void disArr(int arr[], int N)
{
    int i;
    for (i = 0; i < N; i++)
    {
        printf("%d\t", arr[i]);
    }
}

Kết quả:

Thuật toán Bubble sort
Thuật toán Bubble sort

Sắp xếp trộn – Merge sort

Sắp xếp trộn (merge sort) cùng với sắp xếp nhanh là hai thuật toán sắp xếp dựa vào tư tưởng “chia để trị” (divide and conquer). Thủ tục cơ bản là việc trộn hai danh sách đã được sắp xếp vào một danh sách mới theo thứ tự. Nó có thể bắt đầu trộn bằng cách so sánh hai phần tử một (chẳng hạn phần tử thứ nhất với phần tử thứ hai, sau đó thứ ba với thứ tư…) và sau khi kết thúc bước 1 nó chuyển sang bước 2. Ở bước 2 nó trộn các danh sách hai phần tử thành các danh sách bốn phần tử. Cứ như vậy cho đến khi hai danh sách cuối cùng được trộn thành một.

#include <stdio.h>
#include "conio.h"
#include <stdlib.h>
#define MAX_SIZE 100

void Merge(int A[],int first,int mid,int last); // Merge() function
void MergeSort(int A[], int first, int last); // MergeSort() function
void disArr(int arr[], int N);

void main()
{
    int A[] = {0, -2, -5, 11, 5, 8, 2, 4, 24, 100, 34};
    int sz = sizeof(A)/sizeof(int);
    MergeSort(A, 0, sz - 1); 
    disArr(A, sz);
    getch();
}


void disArr(int arr[], int N)
{
    int i;
    for (i = 0; i < N; i++)
    {
        printf("%d\t", arr[i]);
    }
}

void Merge(int A[], int first, int mid, int last)
{
    int tempA[MAX_SIZE];
    int first1 = first, last1 = mid;
    int first2 = mid+1, last2 = last;
    int index = first1;
    for( ; (first1 <= last1) && (first2 <= last2); ++index)
    { 
        if(A[first1] < A[first2])
        {
            tempA[index] = A[first1];
            first1++;
        }
        else
        {
            tempA[index] = A[first2];
            first2++;
        }
    }
    for( ; first1 <= last1; ++index, ++first1)
    {
        tempA[index] = A[first1]; // copy the rest element of Array1
    }
    for( ; first2 <= last2; ++index, ++first2)
    {
        tempA[index] = A[first2]; // copy the rest element of Array2
    }
    for(index = first; index <= last; ++index)
    {
        A[index] = tempA[index];
    }
}

void MergeSort(int A[], int first, int last)
{
    int mid;
    if(first < last)
    {
        mid = (first + last) / 2;
        // Sort left sub-array A[fist...mid]
        MergeSort(A, first, mid);
        // Sort right sub-array A[mid+1...last]
        MergeSort(A, mid+1, last);
        // Combination sub-array A[fist...mid] & sub-array A[mid+1...last]
        Merge(A, first, mid, last);
    }
}

Kết quả:

Thuật toán Merge sort
Thuật toán Merge sort

Sắp xếp vun đống – Heap sort

Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).

Sắp xếp nhanh – Quick Sort

Sắp xếp nhanh (quicksort) là một thuật toán theo tư tưởng chia để trị, nó dựa trên thủ tục phân chia như sau: để chia một dãy ta chọn một phần tử được gọi là “chốt” (pivot), chuyển tất cả các phần tử nhỏ hơn chốt về trước chốt, chuyển tất cả các phần tử lớn hơn chốt về sau nó(nếu sắp xếp theo dãy theo thứ tự tăng dần), nếu sắp xếp dãy theo thứ tự giảm dần ta chuyển tất cả các phần tử nhỏ hơn chốt về bên phải chốt và lớn hơn chốt về bên trái chốt. Thủ tục này có thể thực hiện trong thời gian tuyến tính. Tiếp tục phân chia các dãy con đó như trên cho đến khi các dãy con chỉ còn một phần tử.

Điểm khác biệt giữa sắp xếp nhanh và sắp xếp trộn là trong sắp xếp trộn việc xác định thứ tự được xác định khi “trộn”, tức là trong khâu tổng hợp lời giải sau khi các bài toán con đã được giải, còn sắp xếp nhanh đã quan tâm đến thứ tự các phần tử khi phân chia một danh sách thành hai danh sách con.

Ngoài ra còn nhiều giải thuật sắp xếp khác, trong đó nhiều giải thuật sắp xếp được cải tiến từ các giải thuật trên. Trong sau giải thuật liệt kê trên, ta thường coi các giải thuật chèn, chọn, nổi bọt là các giải thuật cơ bản, độ phức tạp trong trường hợp trung bình của chúng là O(n^2). Ba giải thuật còn lại thường được coi là giải thuật cao cấp, độ phức tạp tính toán trung bình của chúng là n.\log n.

Sắp xếp theo cơ số – Radix sort

Sắp xếp theo cơ số (radix sort) dựa trên tính chất “số” của các khóa. Trong giải thuật sắp xếp theo cơ số, ta không chỉ so sánh giá trị của các khóa, mà so sánh các thành phần của khóa. Giả sử các khóa là các số biểu diễn theo hệ ghi số cơ số M. Khi đó sắp xếp theo cơ số sẽ so sánh từng k

Chúng ta mô tả cách sắp này khi cơ số M=10. Giả sử phải sắp các hồ sơ đánh số bởi 3 chữ số thập phân. Đầu tiên ta chia các hồ sơ vào các đống có cùng chữ số hàng trăm (đồng thới xếp các đống theo thứ tự của chữ số hàng trăm), trong mỗi đống con lại phân chia theo chữ số hàng chục, cuối cùng trong mỗi đống có cùng chữ số hàng trăm và hàng chục, sắp xếp theo thứ tự của chữ số hàng đơn vị.

Trong máy tính, đương nhiên việc sắp xếp theo cơ số nhị phân (cơ số 2) hoặc cơ số là lũy thừa của 2 là thuận lợi nhất. Trong trường hợp cơ số 2, việc phân hoạch tương tự như phân hoạch trong Quick Sort, chỉ khác ở chỗ cách chọn phần tử chốt.

1 Comment on 10 Thuật toán sắp xếp cơ bản

Leave a Reply