sapxeptimkiemC

#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);

}