• Tạo tài khoản
    *
    *
    *
    *
    *
    *

    Thông tin có dấu hoa thị (*) là bắt buộc.

MẠNG SINH VIÊN CNTT VIỆT NAM - ITSTUDENT.net ®

Thuật toán sắp xếp nhanh (quick sort) trong C

  • Share

sorting quicksort animationITStudent.net - Kỹ thuật sắp xếp nhanh xếp danh sách theo chiến lược chia để trị (divide & conquer). Trong thuật toán này, danh sách cần xếp sẽ được xếp thành 2 nhóm, nhóm các phần tử lớn và nhóm các phần tử nhỏ dựa trên 1 phần tử được chọn nào đó. Sau đó tiến hành lặp đệ qui thao tác đó đến khi toàn bộ danh sách được sắp xếp. Nếu so với thuật toán nổi bong bóng đã giới thiệu, thì thuật toán này tỏ ra hiệu quả hơn do số lần thực hiện việc so sánh các phần tử sẽ ít hơn.

 Các bước cơ bản trong thuật toán Quick-Sort bao gồm:

  • Chọn 1 phần tử trong danh sách làm phần tử then chốt (pivot element).
  • Xếp lại danh sách theo qui tắc tất cả các phần tử nhỏ hơn phần tử pivot phải đứng trước nó và tất cả các phần tử lớn hơn phải đứng sau nó.
  • Sau khi tách biệt được 2 phần như thế thì phần tử pivot đã đứng đúng vị trí của nó. Lặp đệ qui cho 2 danh sách con: danh sách các phần tử nhỏ hơn và danh sách các phần tử lớn hơn.
#include <stdio.h>
#include <stdlib.h>
void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
int choose_pivot(int i,int j )
{
   return((i+j) /2);
}
void quicksort(int list[],int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
      k = choose_pivot(m,n);
      swap(&list[m],&list[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] <= key))
                i++;
         while((j >= m) && (list[j] > key))
                j--;
         if( i < j)
                swap(&list[i],&list[j]);
      }
      // hoán 2 phần tử
      swap(&list[m],&list[j]);
      // sắp xếp đệ quy trên danh sách con
      quicksort(list,m,j-1);
      quicksort(list,j+1,n);
   }
}
void printlist(int list[],int n)
{
   int i;
   for(i=0;i<n;i++)
      printf("%d\t",list[i]);
}
void main()
{
   const int MAX_ELEMENTS = 10;
   int list[MAX_ELEMENTS];
   int i = 0;
    
   // phát sinh ngẫu nhiên và điền vào danh sách
   for(i = 0; i < MAX_ELEMENTS; i++ ){
       list[i] = rand();
   }
   printf("Danh sách trước khi sắp xếp là:\n");
   printlist(list,MAX_ELEMENTS);
    
   // sắp xếp danh sách dùng quicksort
   quicksort(list,0,MAX_ELEMENTS-1);
   // In kết quả
   printf("Danh sách sau khi sắp xếp dùng thuật toán quicksort:\n");
   printlist(list,MAX_ELEMENTS);
}

 Đoạn video clip bên dưới minh họa 2 cách sắp xếp đã giới thiệu là bubble sortquick sort. Đoạn video clip cũng so sánh hiệu quả hiện thực của 2 thuật toán này với nhau