sapxeptimkiemC
anhhackta
c_cpp
a year ago
5.5 kB
14
Indexable
#include <stdio.h> #include <stdbool.h> //heap void maxHeapify(int arr[], int n, int i) { int largest = i; int left = i + 1; int right = i + 2 ; if (left < n && arr[largest] > arr[left]) largest = left; if (right < n && arr[largest] > arr[right]) largest = right; if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; maxHeapify(arr, n, largest); } } void heapsort(int arr[],int n) { //chon phan tu tai vi tri i for (int i = n / 2 - 1; i >= 0; i--) maxHeapify(arr, n, i); } //quick void swap(int* x, int* y) { int temp = *x; *x = *y; *y = temp; } // Ham chia mang va dat phan tu chot vao dung vi tri int partition(int arr[],int low, int high) { int pivot = arr[high]; // Chon phan tu chot int i = (low - 1); // Chi muc cua phan tu nho hon pivot for (int j = low; j <= high - 1; j++) { // Neu phan tu hien tai nho hon hoac bang pivot if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); // tra ve phan tu cuoi cung cua mang do doc tu 0 } // Ham sap xep mang bang thuat toan Quick Sort void quickSort( int arr[],int low, int high) { if (low < high) { // Tim vi tri dung cua phan tu chot int pi = partition(arr,low, high); // Sap xep cac phan tu nam ben trai va ben phai cua phan tu chot quickSort(arr,low, pi - 1); quickSort(arr, pi + 1, high); } } //bubble void bubble_sort(int arr[], int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n - i; j++) { if (arr[j] > arr[j+1]) { int swap = arr[j]; arr[j] = arr[j+1]; arr[j+1] = swap; } } } } void linearsearch(int arr[],int n,int tim) { if(tim >= 0) { for(int i=0; i<n; ++i) { if(tim == arr[i]) { printf("tim thay so: %d tai vi tri thu : %d\n",tim,i+1); return; } } } printf("Nhap sai gia tri hay khong co gia tri trong mang\n"); } void binarysearch(int arr[], int n, int x) { quickSort(arr, 0, n - 1); int inkq = -1; int l = 0, r = n - 1; while (l <= r) { int m = l + (r - l) / 2; if (arr[m] == x) { inkq = m; break; } else if (arr[m] < x) { l = m + 1; } else { r = m - 1; } } printf("\nMang da xep\n"); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } if (inkq == -1) { printf("\nKhong tim thay %d trong mang\n", x); } else { printf("\nTim thay %d tai vi tri %d\n", x, inkq + 1); } } void menu(int arr[],int mang[],int n) { int tim; printf("\nChon thao tac :\n1.Sap xep \n2.Tim kiem \n3.IN\n"); int chon; scanf("%d",&chon); switch(chon) { case 1 :printf("\nChon kieu sap xep :"); printf("\n1.BubbleSort \n2.QuickSort \n3.HeapSort\n"); scanf("%d",&chon); switch(chon) { case 1 :bubble_sort(arr, n-1); printf("Mang sau khi sap xep kieu bubblesort :\n"); for(int i=0; i<n; ++i) printf("%d ", arr[i]);menu(arr,mang,n);break; case 2 :quickSort(arr,0, n - 1); printf("Mang sau khi sap xep kieu quicksort :\n"); for(int i=0; i<n; ++i) printf("%d ", arr[i]);menu(arr,mang,n);break; case 3 :heapsort(arr,n); printf("Mang sau khi sap xep kieu heapsort :\n"); for(int i=0; i<n; ++i) printf("%d ", arr[i]);menu(arr,mang,n);break; default :printf("chon sai !\n");break; } case 2 :printf("\nChon kieu tim kiem :"); printf("\n1.Linear Search \n2.Binary Search\n"); scanf("%d",&chon); switch(chon) { case 1 :printf("Nhap so can tim ver 1 : \n"); scanf("%d",&tim); linearsearch(arr,n,tim); menu(arr,mang,n);break; case 2 :printf("Nhap so can tim ver 2: \n"); scanf("%d",&tim); quickSort(arr,0, n - 1); binarysearch(arr,n,tim); menu(arr,mang,n);break; default :printf("chon sai !\n");break; } case 3 : printf("Mang luc dau\n"); for(int i=0; i<n; ++i){ printf("%d ", mang[i]); } printf("\nMang da xep\n"); for(int i=0; i<n; ++i){ printf("%d ", arr[i]); } menu(arr,mang,n);break; default :printf("chon sai !\n");break; } } int main(void) { int mang[] = {2, 6, 24, 39, 12, 19, 1, 5, 3}; int n = sizeof(mang)/sizeof(mang[0]); int arr[n]; printf("Mang luc dau\n"); for(int i=0; i<n; ++i){ printf("%d ", mang[i]); arr[i] = mang[i]; } menu(arr,mang,n); }
Editor is loading...
Leave a Comment