Sắp Xếp Chèn – Wikipedia Tiếng Việt

Sắp xếp chèn

Phân loại	Sắp xếp chèn
Cấu trúc dữ liệu	Cấu trúc dữ liệu mảng
Hiệu suất trường hợp tệ nhất	О(n2)
Hiệu suất trường hợp tốt nhất	O(n)
Hiệu suất trung bình	О(n2)
Độ phức tạp không gian trường hợp tệ nhất	О(n) tổng, O(1) phụ
Tối ưu	Không có

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.

Thuật toán

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

Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu a 1 , . . . , a k {\displaystyle a_{1},...,a_{k}} . Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu a 1 , . . . , a k − 1 {\displaystyle a_{1},...,a_{k-1}} đã được sắp. Để sắp xếp phần tử a k = x {\displaystyle a_{k}=x} ta tìm vị trí thích hợp của nó trong dãy a 1 , . . . , a k − 1 {\displaystyle a_{1},...,a_{k-1}} . Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

Các phần tử ≤x			Vị trí thích hợp	Các phần tử>x			Các phần tử chưa sắp
a 1 {\displaystyle a_{1}}	...	a i − 1 {\displaystyle a_{i-1}}	x	a i + 1 {\displaystyle a_{i+1}}	...	a k − 1 {\displaystyle a_{k-1}}	a k + 1 {\displaystyle a_{k+1}}	...	a n {\displaystyle a_{n}}

Ví dụ

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

Cho danh sách

1

3

7

-

6

4

2

5

Danh sách con gồm 3 phần tử bên trái 1,3,7 đã được sắp. Để tiếp tục sắp xếp phần tử thứ tư a 4 = 6 {\displaystyle a_{4}=6} vào danh sách con đó, ta tìm vị trí thích hợp của nó là sau 3 và trước 7.

1

3

6

7

-

4

2

5

Làm tiếp theo với a 5 = 4 {\displaystyle a_{5}=4} ta được

1

3

4

6

7

-

2

5

Làm tiếp theo với a 6 = 2 {\displaystyle a_{6}=2} ta được

1

2

3

4

6

7

-

5

Cuối cùng chèn a 7 = 5 {\displaystyle a_{7}=5}

1

2

3

4

5

6

7

-

Giải thuật

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

• Danh sách a bắt đầu từ chỉ số 1 tới length

Procedure insert (array a, int k, value) { int i:= k-1; while (i > 0 and a[i] > value) { a[i+1]:= a[i]; i:= i - 1; } a[i+1]:= value; } Procedure InsertSort (array a, int length) { int k:= 2; while (k < length) { insert(a, k, a[k]); k:= k + 1; } }

// Mã giả viết bằng ngôn ngữ C++

void InsertSort (int a[],int n) { int t,j; for(int i=1;i<n;i++) { j=i-1; t=a[i]; while(j >= 0 && t < a[j]) { a[j+1]=a[j]; j--; } a[j+1]=t; // Chèn } }

Đánh giá

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

• Thuật toán sử dụng trung bình n2/4 phép so sánh và n2/4 lần hoán vị, n2/2 phép so sánh và n2/2 lần hoán vị trong trường hợp xấu nhất, n-1 phép so sánh và 0 lần hoán vị trong trường hợp tốt nhất.
• Thuật toán thích hợp đối với mảng đã được sắp xếp một phần hoặc mảng có kích thước nhỏ.

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 vun đống
• Sắp xếp nhanh
• Sắp xếp trộn

Tham khảo

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

• Bender, Michael A.; Farach-Colton, Martín; Mosteiro, Miguel, Insertion Sort is O(n log n) (PDF); also http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.3758; republished? in Theory of Computing Systems Volume 39 Issue 3, June 2006 http://dl.acm.org/citation.cfm?id=1132705
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 2.1: Insertion sort, pp. 15–21.
• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.2.1: Sorting by Insertion, pp. 80–105.
• Sedgewick, Robert (1983), Algorithms, Addison-Wesley, ISBN 978-0-201-06672-2, Chapter 8, pp. 95–??

Liên kết

[sửa | sửa mã nguồn] Wikibook Algorithm implementation có một trang Insertion sort Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Sắp xếp chèn.

• Binary Insertion Sort - Scoreboard Lưu trữ 2012-02-24 tại Wayback Machine – Complete Investigation and C Implementation – By JohnPaul Adamovsky
• Insertion Sort in C with demo Lưu trữ 2013-07-19 tại Wayback Machine - Insertion Sort in C with demo
• Insertion Sort - a comparison with other O(n^2) sorting algorithms
• Animated Sorting Algorithms: Insertion Sort – graphical demonstration and discussion of insertion sort
• Category:Insertion Sort - LiteratePrograms – implementations of insertion sort in various programming languages
• InsertionSort – colored, graphical Java applet that allows experimentation with the initial input and provides statistics
• Sorting Algorithms Demo Lưu trữ 2007-10-24 tại Wayback Machine – visual demonstrations of sorting algorithms (implemented in Java)
• Insertion sort illustrated explanation. Java and C++ implementations.

x t s Thuật toán sắp xếp
Lý thuyết	Độ phức tạp thuật toán | Ký hiệu O lớn | Thứ tự toàn phần | Danh sách | Sắp xếp so sánh
Sắp xếp đổi chỗ	Sắp xếp nổi bọt | Sắp xếp cốc tai | Sắp xếp chẵn lẻ | Sắp xếp răng lược | Sắp xếp gnome | Sắp xếp nhanh
Sắp xếp chọn	Sắp xếp chọn | Sắp xếp vun đống
Sắp xếp chèn	Sắp xếp chèn | Sắp xếp Shell | Sắp xếp bằng cây | Sắp xếp thư viện | Patience sorting
Sắp xếp trộn	Sắp xếp trộn | Strand sort
Sắp xếp không so sánh	Sắp xếp theo cơ số | Sắp xếp thùng | Sắp xếp đếm | Sắp xếp chuồng bồ câu | Burstsort | Bead sort
Các loại khác	Sắp xếp topo | Mạng sắp xếp | Bitonic sorter | Pancake sorting | Bogosort | Stooge sort