Sắp xếp là quá trình sắp xếp các phần tử theo thứ tự tăng dần (hoặc) giảm dần.
Các kiểu sắp xếp
Ngôn ngữ C cung cấp năm kỹ thuật sắp xếp như sau -
- Sắp xếp bong bóng (hoặc) Sắp xếp trao đổi
- Sắp xếp lựa chọn
- Sắp xếp chèn (hoặc) Sắp xếp tuyến tính
- Sắp xếp nhanh (hoặc) Sắp xếp trao đổi phân vùng
- Sắp xếp Hợp nhất (hoặc) Sắp xếp bên ngoài
Hợp nhất sắp xếp
Merge sort là một phương pháp chia để trị. Nó chia một mảng thành hai nửa, chinh phục đệ quy và hợp nhất (kết hợp).
Hãy xem xét một ví dụ được đưa ra bên dưới -
Lấy một mảng chưa được sắp xếp và áp dụng kỹ thuật sắp xếp hợp nhất để sắp xếp mảng.
38, 27, 43, 3, 9, 82, 10
Bây giờ, hãy kết hợp một mảng bằng cách sắp xếp như hình dưới đây -
Ví dụ
Sau đây là chương trình C để sắp xếp các phần tử bằng cách sử dụng kỹ thuật sắp xếp hợp nhất -
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i <= high; i++)
a[i] = b[i];
}
void sort(int low, int high) {
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main() {
int i;
printf("List before sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
sort(0, max);
printf("\nList after sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
} Đầu ra
Khi chương trình trên được thực thi, nó tạo ra kết quả sau -
List before sorting 10 14 19 26 27 31 33 35 42 44 0 List after sorting 0 10 14 19 26 27 31 33 35 42 44