Sắp Xếp Nhanh – Wikipedia Tiếng Việt

Bước tới nội dung

Nội dung

chuyển sang thanh bên ẩn

• Đầu
• 1 Phần tử chốt (pivot)
• 2 Thuật phân chia
• 3 Ví dụ
• 4 Mã giả Hiện/ẩn mục Mã giả
  • 4.1 Thủ tục phân chia
  • 4.2 Quick sort đệ quy
  • 4.3 Quick sort đệ quy có sử dụng cấu trúc dữ liệu C:
  • 4.4 Khử đệ quy
  • 4.5 Quick sort chia ba
• 5 Xem thêm
• 6 Tham khảo

• Bài viết
• Thảo luận

Tiếng Việt

• Đọc
• Sửa đổi
• Sửa mã nguồn
• Xem lịch sử

Công cụ Công cụ chuyển sang thanh bên ẩn Tác vụ

• Đọc
• Sửa đổi
• Sửa mã nguồn
• Xem lịch sử

Chung

• Các liên kết đến đây
• Thay đổi liên quan
• Trang đặc biệt
• Liên kết thường trực
• Thông tin trang
• Trích dẫn trang này
• Lấy URL ngắn gọn
• Tải mã QR

In và xuất

• Tạo một quyển sách
• Tải dưới dạng PDF
• Bản để in ra

Tại dự án khác

• Wikimedia Commons
• Khoản mục Wikidata

Giao diện chuyển sang thanh bên ẩn Bách khoa toàn thư mở Wikipedia Sắp xếp nhanh

Quicksort thực hiện trên danh sách các số. Đường nằm ngang là các giá trị làm phần tử chốt.
Phân loại	Giải thuật sắp xếp
Cấu trúc dữ liệu	Khác nhau
Hiệu suất trường hợp tệ nhất	Trung bình O ( n log ⁡ n ) {\displaystyle O(n\log n)} Xấu nhất O ( n 2 ) {\displaystyle O(n^{2})}
Độ phức tạp không gian trường hợp tệ nhất	Khác nhau tùy vào cách hiện thực
Tối ưu	Thỉnh thoảng

Sắp xếp nhanh (Quicksort), còn được gọi là sắp xếp kiểu phân chia (part sort) là một thuật toán sắp xếp phát triển bởi C.A.R. Hoarec sắp thành hai danh sách con. Khác với sắp xếp trộn, chia danh sách cần sắp xếp a [ 1.. n ] {\displaystyle a[1..n]} thành hai danh sách con có kích thước tương đối bằng nhau nhờ chỉ số đứng giữa danh sách, sắp xếp nhanh chia nó thành hai danh sách bằng cách so sánh từng phần tử của danh sách với một phần tử được chọn được gọi là phần tử chốt. Những phần tử nhỏ hơn hoặc bằng phần tử chốt được đưa về phía trước và nằm trong danh sách con thứ nhất, các phần tử lớn hơn chốt được đưa về phía sau và thuộc danh sách đứng sau. Cứ tiếp tục chia như vậy tới khi các danh sách con đều có độ dài bằng 1.

Phần tử chốt (pivot)

[sửa | sửa mã nguồn]

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 là trung vị của danh sách. Khi đó sau l o g 2 ( n ) {\displaystyle log_{2}(n)} lần phân chia ta sẽ đạt tới kích thước danh sách bằng 1. Tuy nhiên điều đó rất khó. Có các cách chọn phần tử chốt như sau:

• 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 3 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. (Cách này có thể dẫn đến khả năng rơi vào các trường hợp đặc biệt)

Thuật phân chia

[sửa | sửa mã nguồn]

Sau khi phần tử chốt được chọn giải thuật phân chia nên tiến hành như thế nào?

• Một giải pháp đơn giản nhất cho vấn đề này là duyệt từ đầu đến cuối lần lượt so sánh các phần tử của danh sách với phần tử chốt. Theo cách này, ta phải tiến hành n phép so sánh, ngoài ra còn phải dành n đơn vị bộ nhớ để lưu giữ các giá trị trung gian.
• Một giải pháp khác được đề nghị là duyệt theo hai đường. Một đường từ đầu danh sách, một đường từ cuối danh sách. Theo cách này, ta tìm phần tử đầu tiên tính từ trái lớn hơn phần tử chốt và phần tử đầu tiên phía phải nhỏ hơn hoặc bằng phần tử chốt rồi đổi chỗ cho nhau. Tiếp tục như vậy cho đến khi hai đường gặp nhau.
• Để có thể gọi đệ quy ta xét bài toán phân chia một danh sách con của a: a [ k 1 , k 2 ] {\displaystyle a[k_{1},k_{2}]} thành hai danh sách.

Ví dụ

[sửa | sửa mã nguồn]

Trong ví dụ sau đây ta luôn chọn phần tử chốt là phần tử đứng giữa danh sách với chỉ số của phần tử chốt được chọn là k = i n t ( ( k 1 + k 2 ) / 2 ) {\displaystyle k=int((k_{1}+k_{2})/2)}

a = ( 2 , 6 , 3 , 7 , 4 , 5 , 1 ) {\displaystyle a=(2,6,3,7,4,5,1)}

2

6

3

7

4

5

1

Do ngẫu nhiên, phần tử chốt a [ 4 ] = 7 {\displaystyle a[4]=7} là phần tử lớn nhất trong dãy, ta tìm từ trái sang phải không có phần tử nào lớn hơn phần tử chốt, do đó ta đổi phần tử chốt với phần tử cuối cùng, danh sách được chia thành hai danh sách con a [ 1..6 ] {\displaystyle a[1..6]} và a [ 7..7 ] {\displaystyle a[7..7]}

2

6

3

1

4

5

--

7

Việc phân chia tiếp tục với danh sách con a [ 1..6 ] {\displaystyle a[1..6]} . Phần tử chốt được chọn là a[4]=1. Từ trái sang phải tìm được phần tử đầu tiên lớn hơn a [ 4 ] = 1 {\displaystyle a[4]=1} là a [ 1 ] = 2 {\displaystyle a[1]=2} , từ phải sang phần tử đầu tiên <=1 là chính a[4]. Đổi chố hai phần tử này

1

6

3

2

4

5

--

7

Đi tiếp sang phải ta được a [ 2 ] > 1 {\displaystyle a[2]>1} , ở phía ngược lại đi tiếp sang trái tìm được phần tử nhỏ hơn hoặc bằng chốt là chính a [ 1 ] = 1 {\displaystyle a[1]=1} nhưng lúc này hai đường đã chạm nhau nên ta không đổi nữa. Do vậy a [ 1..6 ] {\displaystyle a[1..6]} được phân chia thành hai danh sách con a [ 1..1 ] {\displaystyle a[1..1]} và a [ 2..6 ] {\displaystyle a[2..6]}

1

--

6

3

2

4

5

--

7

Tiếp tục phân chia a [ 2..6 ] {\displaystyle a[2..6]} với phần tử chốt a [ 4 ] = {\displaystyle a[4]=} 2 ta được

1

--

2

--

3

6

4

5

--

7

Tiếp tục phân chia a [ 3..6 ] {\displaystyle a[3..6]} với phần tử chốt a [ 5 ] = 4 {\displaystyle a[5]=4} ta được

1

--

2

--

3

4

--

6

5

--

7

Tiếp tục phân chia a [ 3..4 ] {\displaystyle a[3..4]} với phần tử chốt a [ 4 ] = 4 {\displaystyle a[4]=4} và a [ 5..6 ] {\displaystyle a[5..6]} với phần tử chốt a [ 6 ] = 5 {\displaystyle a[6]=5} ta được

1

--

2

--

3

--

4

--

5

--

6

--

7

Mã giả

[sửa | sửa mã nguồn]

Thủ tục phân chia

[sửa | sửa mã nguồn] // left là chỉ số của phần tử đầu tiên của mảng // right là chỉ số của phần tử cuối cùng của mảng // số phần tử của mảng = right-left+1 function partition(array, 'left', 'right', 'pivotIndex') 1.'pivotValue':= array['pivotIndex'] 2.swap array['pivotIndex'] and array['right'] // Move pivot to end 3.'storeIndex':= 'left' 4.for 'i' from 'left' to 'right'-1 // left ≤ i < right 1.if array['i'] < 'pivotValue' 1.swap array['i'] and array['storeIndex'] 2.'storeIndex':= 'storeIndex' + 1 5.swap array['storeIndex'] and array['right'] // Move pivot to its final place 6.return 'storeIndex'

Quick sort đệ quy

[sửa | sửa mã nguồn] function quicksort(array, 'left', 'right') // If the list has 2 or more items if 'left' < 'right' // See "Choice of pivot" section below for possible choices choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right' // Get lists of bigger and smaller items and final position of pivot 'pivotNewIndex':= partition(array, 'left', 'right', 'pivotIndex') // Recursively sort elements smaller than the pivot quicksort(array, 'left', 'pivotNewIndex' - 1) // Recursively sort elements at least as big as the pivot quicksort(array, 'pivotNewIndex' + 1, 'right')

Quick sort đệ quy có sử dụng cấu trúc dữ liệu C:

[sửa | sửa mã nguồn] #include<stdio.h> #include<conio.h> typedefintkeytype; typedefstruct{ keytypekey; }recordtype; voidSwap(recordtype*x,recordtype*y){ recordtypetemp; temp=*x; *x=*y; *y=temp; } intFindPivot(recordtypea[],inti,intj){ keytypefirstkey; intk; k=i+1; firstkey=a[i].key; while((k<=j)&&(a[k].key==firstkey)) k++; if(k>j) return-1; else if((a[k].key>firstkey)) returnk; else returni; } intPartition(recordtypea[],inti,intj,keytypepivot){ intL,R; L=i; R=j; while(L<=R){ while(a[L].key<pivot)L++; while(a[R].key>pivot)R--; if(L<R)Swap(&a[L],&a[R]); } returnL; } voidQuickSort(recordtypea[],inti,intj){ keytypepivot; intpivotindex,k; pivotindex=FindPivot(a,i,j); if(pivotindex!=-1){ pivot=a[pivotindex].key; k=Partition(a,i,j,pivot); QuickSort(a,i,k-1); QuickSort(a,k,j); } } intmain(){ intn,i; recordtypea[50]; printf("nhap n: "); scanf("%d",&n); for(i=0;i<n;i++){ printf("nhap phan tu: "); scanf("%d",&a[i].key); } QuickSort(a,0,n-1); for(i=0;i<n;i++){ printf(" --- %d",a[i].key); } return0; }

Khử đệ quy

[sửa | sửa mã nguồn]

Nhiều người cho rằng việc khử đệ quy của sắp xếp nhanh thực ra không cần thiết, nó chỉ có tác dụng cho những người mới tiếp cận khoa học máy tính hiểu sâu sắc hơn về khái niệm đệ quy. Bản chất của các giải thuật đệ quy là lưu trữ các tham biến đệ quy vào một ngăn xếp (stack) để lần lượt lấy ra xử lý.

Khi khử đệ quy của giải thuật đệ quy, mỗi lần phân chia danh sách thành 2 danh sách con ta lưu trữ các tham số của danh sách đứng sau vào một ngăn xếp, rồi phân chia tiếp danh sách đứng trước.

Giải thuật đơn giản nhất để khử đệ quy của sắp xếp nhanh như sau:

Procedure QuickSort(a[1..n]) { Var list S, E; Int m:=1 S(m):=1; E(m):= n; While m>0 { k=S(m); l=E(m) m:=m-1; if l<k then { i=Part(k,l); m=m+1; S(m):=i+1 E(m):=l } } }

Ưu điểm của sắp xếp nhanh không đệ quy nằm ở những cải tiến của giải thuật trên đây. Có thể cải tiến theo những hướng sau: Cất vào ngăn xếp danh sách con ít phần tử hơn trong hai danh sách con và đối với các danh sách con có độ dài đủ nhỏ thì dùng một phương pháp sắp xếp sơ cấp (chẳng hạn sắp xếp chèn).

Quick sort chia ba

[sửa | sửa mã nguồn]

Một phương pháp chia khác là chia danh sách thành 3 danh sách con, lần lượt nhỏ hơn, bằng và lớn hơn phần tử chốt.

function quicksort(a) Var list less, equal, greater if length(a) ≤ 1 return a else select a pivot value pivot from a for each x in a if x < pivot then add x to less if x = pivot then add x to equal if x > pivot then add x to greater return concatenate(quicksort(less), equal, quicksort(greater))

Xem thêm

[sửa | sửa mã nguồn]

• Sắp xếp nổi bọt
• Sắp xếp chọn
• Sắp xếp chèn
• Sắp xếp trộn
• Sắp xếp vun đống

Tham khảo

[sửa | sửa mã nguồn] Lấy từ “https://vi.wikipedia.org/w/index.php?title=Sắp_xếp_nhanh&oldid=69052358” Thể loại:

• Thuật toán sắp xếp
• Khoa học năm 1961

Thể loại ẩn:

• Pages using deprecated image syntax