VietTuts

Tự Học Lập Trình Online

  • Home
  • Java
  • Servlet
  • JSP
  • Struts2
  • Hibernate
  • Spring
  • MyBatis
  • Java WS
  • C
  • C++
  • C#
  • Python
  • PHP
  • Excel
  • VBA
  • Web
    • JavaScript
    • JQUERY
    • JSON
    • AJAX
    • CSS
    • HTML
    • HTML5
    • Node.js
    • Angular 7
  • SQL
    • MySQL
    • SQL Server
  • Misc
    • Eclipse
    • Phần mềm tiện ích
    • Cấu trúc DL&GT
    • Selenium Test

Cấu Trúc Dữ Liệu & Giải Thuật

Tổng quan về cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu là gì? Giải thuật là gì? Cài đặt môi trường

Giải Thuật

Giải thuật tiệm cận Giải thuật tham lam Giải thuật chia để trị Giải thuật qui hoạch động

Cấu Trúc Dữ Liệu Mảng

Cấu trúc dữ liệu mảng

Danh sách liên kết - Linked list

Cấu trúc dữ liệu Linked List Cấu trúc dữ Doubly Linked List Cấu trúc dữ Circular Linked List

Ngăn Xếp & Hàng Đợi

Cấu trúc dữ liệu ngăn xếp - Stack Cấu trúc dữ hàng dợi - Queue

Một Số Giải Thuật Tìm Kiếm

Tìm kiếm tuyến tính - Linear Search Tìm kiếm nhị phân - Binary Search Tìm kiếm nội suy - Interpolation Search Cấu trúc dữ liệu Hash Table

Một Số Giải Thuật Sắp Xếp

Giải thuật sắp xếp 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 Giải thuật Shell Sort Giải thuật quay lui - Back Tracking

Cấu Trúc Dữ Liệu Đồ Thị (Graph)

Cấu trúc dữ liệu đồ thị Tìm kiếm theo chiều sâu - Depth First Search Tìm kiếm theo chiều sâu - Breadth First Search
1 / 3
❮ ❯

Giải thuật sắp xếp nhanh (Quick Sort)


Giải thuật sắp xếp trộn (Merge Sort)
Giải thuật sắp xếp Shell Sort

Nội dung chính

  • Sắp xếp nhanh (Quick Sort) là gì?
  • Kỹ thuật chọn phần tử chốt trong giải thuật sắp xếp nhanh (Quick Sort)
  • Minh họa cách chia trong giải thuật sắp xếp nhanh (Quick Sort)
  • Giải thuật phần tử chốt trong sắp xếp nhanh (Quick Sort)
  • Giải thuật phần tử chốt mẫu trong sắp xếp nhanh (Quick Sort)
  • Giải thuật sắp xếp nhanh (Quick Sort)
  • Giải thuật mẫu cho Sắp xếp nhanh (Quick Sort)

Sắp xếp nhanh (Quick Sort) 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.

Tiến trình chia này diễn ra tiếp tục cho tới khi độ dài của các mảng con đều bằng 1. Giải thuật sắp xếp nhanh tỏ ra khá hiệu quả với các tập dữ liệu lớn khi mà độ phức tạp trường hợp trung bình và trường hợp xấu nhất là O(nlogn) với n là số phần tử.



Kỹ thuật chọn phần tử chốt trong giải thuật sắp xếp nhanh (Quick Sort)

Kỹ thuật chọn phần tử chốt ảnh hưởng khá nhiều đến khả năng rơi vào các vòng lặp vô hạn đối với các trường hợp đặc biệt. Tốt nhất là chọn phần tử chốt (pivot) nằm ở trung vị của danh sách. Khi đó, sau log2(n) lần chia chúng ta sẽ đạt tới kích thước các mảng con bằng 1.

Dưới đây là các cách chọn phần tử chốt:

  • Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.

  • Chọn phần tử đứng giữa danh sách làm phần tử chốt.

  • Chọn phần tử trung vị trong ba phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt.

  • Chọn phần tử ngẫu nhiên làm phần tử chốt. Tuy nhiên cách này rất dễ dẫn đến khả năng rơi vào các trường hợp đặc biệt.


Minh họa cách chia trong giải thuật sắp xếp nhanh (Quick Sort)

Hình minh họa dưới đây minh họa cách tìm phần tử chốt trong mảng. Ở đây, chúng ta chọn phần tử chốt đứng ở cuối danh sách.

Giải thuật sắp xếp nhanh (Quick Sort)

Phần tử chốt chia danh sách thành hai phần. Và sử dụng đệ qui, chúng ta tìm phần tử chốt cho các mảng con cho tới khi danh sách chỉ còn một phần tử.



Giải thuật phần tử chốt trong sắp xếp nhanh (Quick Sort)

Dựa vào cách chia danh sách trong giải thuật sắp xếp nhanh ở trên, chúng ta có thể viết một giải thuật như dưới đây.

Output:

Bước 1: Chọn phần tử chốt là phần tử có chỉ mục cao nhất (phần tử ở cuối danh sách)
Bước 2: Khai báo hai biến để trỏ tới bên trái và bên phải của danh sách, ngoại trừ phần tử chốt
Bước 3: Biến bên trái trỏ tới mảng con bên trái
Bước 4: Biến bên phải trỏ tới mảng con bên phải 
Bước 5: Khi giá trị tại biến bên trái là nhỏ hơn phần tử chốt thì di chuyển sang phải
Bước 6: Khi giá trị tại biến bên phải là lớn hơn phần tử chốt thì di chuyển sang trái 
Bước 7: Nếu không trong trường hợp cả bước 5 và bước 6 thì tráo đổi giá trị biến trái và phải
Bước 8: Nếu left ≥ right, thì đây chính là giá trị chốt mới

Giải thuật phần tử chốt mẫu trong sắp xếp nhanh (Quick Sort)

Từ các bước trên, chúng ta có thể suy ra code mẫu cho giải thuật sắp xếp nhanh (Quick Sort) như sau:


Bắt đầu hàm partitionFunc(left, right, pivot)
   leftPointer = left -1
   rightPointer = right
   while True thực hiện
      while A[++leftPointer] < pivot thực hiện
         //không làm điều gì            
      kết thúc while
  
      while rightPointer > 0 && A[--rightPointer] > pivot thực hiện
         //không làm điều gì     
      kết thúc while
  
      if leftPointer >= rightPointer
         break
      else                
         Tráo đổi leftPointer,rightPointer
      kết thúc if
  
   kết thúc while 
 
   Tráo đổi leftPointer,right
   return leftPointer
 
Kết thúc hàm


Giải thuật sắp xếp nhanh (Quick Sort)

Sử dụng giải thuật phần tử chốt một cách đệ qui, chúng ta có thể kết thúc với các mảng con nhỏ hơn. Sau đó mỗi mảng con này có thể được xử lý với sắp xếp nhanh. Dưới đây, mình sử dụng giải thuật đệ qui cho sắp xếp nhanh:

Output:

Bước 1: Lấy phần tử chốt là phần tử ở cuối danh sách
Bước 2: Chia mảng bởi sử dụng phần tử chốt
Bước 3: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên trái 
Bước 4: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên phải

Giải thuật mẫu cho Sắp xếp nhanh (Quick Sort)

Từ phần giải thuật trên, chúng ta có thể suy ra code mẫu cho giải thuật sử dụng đệ qui cho sắp xếp nhanh như sau:


Bắt đầu hàm quickSort(left, right)
   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   kết thúc if  
   
Kết thúc hàm

Giải thuật sắp xếp trộn (Merge Sort)
Giải thuật sắp xếp Shell Sort

Recent Updates

Sắp Tết 2024 Rồi! - Còn bao nhiêu ngày nữa là đến tết 2024?Java Swing - Bài tập quản lý sinh viên trong javaLinkedList trong javaArrayList trong javaBài tập java có lời giảiXác thực dữ liệu (Data Validation) trong ExcelSắp xếp dữ liệu trong ExcelLọc dữ liệu (Data Filter) trong ExcelHeader và Footer trong ExcelMàu văn bản và màu nền (background) trong ExcelCăn chỉnh văn bản trong ExcelĐịnh hướng văn bản trong ExcelTrang trí văn bản trong Excel

VietTuts on facebook

Học Lập Trình Online Miễn Phí - VietTuts.Vn
Danh Sách Bài Học

Học Java | Hibernate | Spring
Học Excel | Excel VBA
Học Servlet | JSP | Struts2
Học C | C++ | C#
Học Python
Học SQL

Bài Tập Có Lời Giải

Bài tập Java
Bài tập C
Bài tập C++
Bài tập C#
Bài tập Python
Ví dụ Excel VBA

Câu Hỏi Phỏng Vấn

201 câu hỏi phỏng vấn java
25 câu hỏi phỏng vấn servlet
75 câu hỏi phỏng vấn jsp
52 câu hỏi phỏng vấn Hibernate
70 câu hỏi phỏng vấn Spring
57 câu hỏi phỏng vấn SQL

Scroll back to top

Copyright © 2016 VietTuts.Vn all rights reserved. | Liên hệ | Chính sách - riêng tư | sitemap.html | sitemap_index.xml