Sắp xếp là một hoạt động cơ bản trong đó các yếu tố của một mảng được sắp xếp theo một số thứ tự cụ thể để tăng cường khả năng tìm kiếm của nó. Nói một cách đơn giản, dữ liệu được sắp xếp sao cho có thể dễ dàng tìm kiếm.
Biểu đồ so sánh
| Cơ sở để so sánh | Sắp xếp chèn | Sắp xếp lựa chọn |
|---|---|---|
| Căn bản | Dữ liệu được sắp xếp bằng cách chèn dữ liệu vào một tệp được sắp xếp hiện có. | Dữ liệu được sắp xếp bằng cách chọn và đặt các phần tử liên tiếp vào vị trí được sắp xếp. |
| Thiên nhiên | Ổn định | Không ổn định |
| Quy trình cần tuân thủ | Các yếu tố được biết trước trong khi vị trí để đặt chúng được tìm kiếm. | Vị trí được biết trước trong khi các yếu tố được tìm kiếm. |
| Dữ liệu ngay lập tức | Sắp xếp chèn là kỹ thuật sắp xếp trực tiếp có thể xử lý dữ liệu ngay lập tức. | Nó không thể đối phó với dữ liệu ngay lập tức, nó cần phải có mặt ngay từ đầu. |
| Trường hợp phức tạp nhất | Trên) | O (n 2 ) |
Định nghĩa sắp xếp chèn
Sắp xếp chèn hoạt động bằng cách chèn tập hợp các giá trị trong tệp được sắp xếp hiện có. Nó xây dựng mảng được sắp xếp bằng cách chèn một phần tử tại một thời điểm. Quá trình này tiếp tục cho đến khi toàn bộ mảng được sắp xếp theo thứ tự. Khái niệm chính đằng sau sắp xếp chèn là chèn từng mục vào vị trí thích hợp của nó trong danh sách cuối cùng. Phương pháp sắp xếp chèn giúp tiết kiệm một lượng bộ nhớ hiệu quả.
Làm việc của loại chèn
- Nó sử dụng hai bộ mảng trong đó một bộ lưu trữ dữ liệu được sắp xếp và bộ khác trên dữ liệu chưa được sắp xếp.
- Thuật toán sắp xếp hoạt động cho đến khi có các phần tử trong tập hợp chưa sắp xếp.
- Giả sử có các phần tử số 'n' trong mảng. Ban đầu, phần tử có chỉ số 0 (LB = 0) tồn tại trong tập đã sắp xếp. Các yếu tố còn lại nằm trong phân vùng chưa sắp xếp của danh sách.
- Phần tử đầu tiên của phần chưa sắp xếp có chỉ số mảng 1 (Nếu LB = 0).
- Sau mỗi lần lặp, nó chọn phần tử đầu tiên của phân vùng chưa được sắp xếp và chèn nó vào vị trí thích hợp trong tập đã sắp xếp.
Ưu điểm của sắp xếp chèn
- Dễ dàng thực hiện và rất hiệu quả khi được sử dụng với các bộ dữ liệu nhỏ.
- Yêu cầu không gian bộ nhớ bổ sung của sắp xếp chèn là ít hơn (tức là O (1)).
- Nó được coi là kỹ thuật sắp xếp trực tiếp vì danh sách có thể được sắp xếp khi các yếu tố mới được nhận.
- Nó nhanh hơn các thuật toán sắp xếp khác.
Thí dụ :
Định nghĩa sắp xếp lựa chọn
Sắp xếp lựa chọn thực hiện sắp xếp bằng cách tìm kiếm số giá trị tối thiểu và đặt nó vào vị trí đầu tiên hoặc cuối cùng theo thứ tự (tăng dần hoặc giảm dần). Quá trình tìm kiếm khóa tối thiểu và đặt nó vào vị trí thích hợp được tiếp tục cho đến khi tất cả các yếu tố được đặt ở vị trí phù hợp.
Làm việc của Sắp xếp lựa chọn
- Giả sử một mảng ARR với N phần tử trong bộ nhớ.
- Trong lần đầu tiên, khóa nhỏ nhất được tìm kiếm cùng với vị trí của nó sau đó ARR [POS] được hoán đổi với ARR [0]. Do đó, ARR [0] được sắp xếp.
- Trong lần chuyển thứ hai, một lần nữa vị trí của giá trị nhỏ nhất được xác định trong phân đoạn của các phần tử N-1. Trao đổi ARR [POS] với ARR [1].
- Trong pass N-1, quy trình tương tự được thực hiện để sắp xếp số lượng phần tử N.
Thí dụ :
Sự khác biệt chính giữa Sắp xếp chèn và Sắp xếp lựa chọn
- Các loại chèn thường thực hiện các hoạt động chèn. Ngược lại, sắp xếp lựa chọn thực hiện việc lựa chọn và định vị các yếu tố cần thiết.
- Sắp xếp chèn được cho là ổn định trong khi sắp xếp lựa chọn không phải là thuật toán ổn định.
- Trong thuật toán sắp xếp chèn, các phần tử được biết trước đó. Ngược lại, sắp xếp lựa chọn chứa vị trí trước.
- Sắp xếp chèn là một kỹ thuật sắp xếp trực tiếp trong đó các phần tử đến được sắp xếp ngay lập tức trong danh sách trong khi sắp xếp lựa chọn không thể hoạt động tốt với dữ liệu ngay lập tức.
- Sắp xếp chèn có thời gian chạy O (n) trong trường hợp tốt nhất. Ngược lại, độ phức tạp thời gian chạy trường hợp tốt nhất của sắp xếp lựa chọn là O (n2).
Độ phức tạp của sắp xếp chèn
Độ phức tạp trường hợp tốt nhất của sắp xếp chèn là O (n) lần, tức là khi mảng được sắp xếp trước đó. Theo cách tương tự, khi mảng được sắp xếp theo thứ tự ngược lại, phần tử đầu tiên của mảng chưa được sắp xếp sẽ được so sánh với từng phần tử trong tập đã sắp xếp. Vì vậy, trong trường hợp xấu nhất, thời gian chạy của sắp xếp Chèn là bậc hai, tức là O (n2) . Trong trường hợp trung bình, nó cũng phải thực hiện các phép so sánh tối thiểu (k-1) / 2. Do đó, trường hợp trung bình cũng có thời gian chạy bậc hai O (n2).
Độ phức tạp của Sắp xếp lựa chọn
Vì công việc của lựa chọn, sắp xếp không phụ thuộc vào thứ tự ban đầu của các phần tử trong mảng, do đó không có nhiều khác biệt giữa trường hợp tốt nhất và độ phức tạp của trường hợp xấu nhất của sắp xếp lựa chọn.
Sắp xếp lựa chọn chọn phần tử giá trị tối thiểu, trong quá trình lựa chọn, tất cả số phần tử 'n' được quét; do đó, so sánh n-1 được thực hiện trong lần đầu tiên. Sau đó, các yếu tố được hoán đổi cho nhau. Tương tự trong lần chuyển thứ hai cũng để tìm phần tử nhỏ thứ hai, chúng tôi yêu cầu quét các phần tử n-1 còn lại và quá trình được tiếp tục cho đến khi toàn bộ mảng được sắp xếp.
Do đó, độ phức tạp thời gian chạy của sắp xếp lựa chọn là O (n2) .
= (n-1) + (n-2) + Cách giết .. + 2 + 1
= n (n-1) / 2 = O (n2)
Phần kết luận
Trong số cả hai thuật toán sắp xếp, sắp xếp chèn là nhanh, hiệu quả, ổn định trong khi sắp xếp lựa chọn chỉ hoạt động hiệu quả khi tập hợp các phần tử nhỏ hoặc danh sách được sắp xếp một phần trước đó. Số lượng so sánh được thực hiện theo cách sắp xếp lựa chọn lớn hơn các chuyển động được thực hiện trong khi trong sắp xếp chèn, số lần một phần tử được di chuyển hoặc hoán đổi lớn hơn so với các so sánh được thực hiện.
