STDIO Developer

20 bundles
2 files3 months ago
1

Merge Sort

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
void Merge(int a[], int left, int mid, int right) { int *temp; // Khoi tao mang tam de sap xep int i = left; // Vi tri phan tu dau tien cua mang con ben trai int j = mid + 1; // Vi tri phan tu dau tien cua mang con ben phai temp = new int[right - left + 1]; // Khoi tao so luong phan tu cua mang tam for (int k = 0; k <= right - left; k++) { // Kiem phan tu cua mang con ben trai va ben phai if (a[i] < a[j]) { // Neu a[i] < a[j] thi copy phan tu ben trai vao mang tam temp[k] = a[i]; i++; // Vi tri phan tu tiep theo cua mang } else // Nguoc lai copy phan tu cua mang con ben phai vao mang tam { temp[k] = a[j]; j++; // Vi tri phan tu tiep theo cua mang } // Kiem tra mang con ben trai con phan tu nao khong if (i == mid + 1) { // Nguoc lai dua cac phan tu con lai cua mang con ben phai vao mang tam while (j <= right) { k++; temp[k] = a[j]; j++; } break; } // Kiem tra mang con ben phai con phan tu nao khong if (j == right + 1) { // Nguoc lai dua cac phan tu con lai cua mang con ben phai vao mang tam while (i <= mid) { k++; temp[k] = a[i]; i++; } break; } } for (int k = 0; k <= right - left; k++) // Chep mang tam vao mang chinh a[left + k] = temp[k]; delete temp; } // left, right la bien trai va bien phai cua mang void MergeSort(int a[], int left, int right) { if (right > left) { int mid; // Phan tu o giua mid = (left + right) / 2; MergeSort(a, left, mid); // Goi de quy mang con ben trai MergeSort(a, mid + 1, right); // Goi de quy mang con ben phai Merge(a, left, mid, right); // Goi ham so sanh hai mang con } } int main() { int a[10], n = 10; for (int i = 0; i < n; i++) { cout << "Nhap so " << i + 1 << ": "; cin >> a[i]; } MergeSort(a, 0, 9); for (int i = 0; i < n; i++) cout << a[i] << " "; return 0; }

Merge Sort - 2

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128
#include <stdio.h> // trả về số nhỏ hơn int min(int a, int b) { if (a < b) return a; return b; } // trộn 2 dãy phụ tạo dãy mới void merge(int arr[], int temp1[], int n1, int temp2[], int n2, int k) { int i1, i2, i; int k1, k2; int j1, j2; i = i1 = i2 = 0; j1 = j2 = 0; while (n2 > 0 && n2 > 0) { // xác định độ dài từng dãy con 2 dãy phụ k1 = min(k, n1); k2 = min(k, n2); // xét và trộn dãy con vào dãy if (temp1[i1 + j1] < temp2[i2 + j2]) { arr[i++] = temp1[i1 + j1]; j1++; // trộn dãy con còn lại vào dãy if (j1 == k1) { for (; j2 < k2; j2++) arr[i++] = temp2[i2 + j2]; i1 += k1; i2 += k2; j1 = j2 = 0; n1 -= k1; n2 -= k2; } } else { arr[i++] = temp2[i2 + j2]; j2++; // trộn dãy con còn lại vào dãy if (j2 == k2) { for (; j1 < k1; j1++) arr[i++] = temp1[i1 + j1]; i1 += k1; i2 += k2; j1 = j2 = 0; n1 -= k1; n2 -= k2; } } } } void mergeSort(int arr[], int n) { int n1, n2; int i; int k; int ik; int *temp1 = new int[n]; int *temp2 = new int[n]; k = 1; do { i = n1 = n2 = 0; // chia mảng ra 2 mảng phụ while (i < n) { ik = 0; while (ik < k && i < n) { temp1[n1++] = arr[i++]; ik++; } ik = 0; while (ik < k && i < n) { temp2[n2++] = arr[i++]; ik++; } } merge(arr, temp1, n1, temp2, n2, k); // tăng độ lớn tối đa dãy con k *= 2; } while (k < n); delete[] temp1; delete[] temp2; } void main() { int i, n; int *Array; printf("How many elements do you want to sort? "); scanf("%d", &n); Array = new int[n]; for (i = 0; i < n; i++) { printf("Array[%d] = ", i); scanf("%d", &Array[i]); } mergeSort(Array, n); for (i = 0; i < n; i++) { printf("%d ", Array[i]); } delete[] Array; }