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

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.

Dưới đây là chương trình C minh họa cho cách thực hiện giải thuật sắp xếp nhanh.

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

#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 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);
}

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.