Untitled

#include<stdio.h>

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}

void insertionSort(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;

    
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    
    arr[j + 1] = key;
  }
}

void interchangeSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      
      if (arr[j] > arr[j + 1]) {
        
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

void bubbleSort(int arr[], int n) {
  int swapped = 1;
  while (swapped) {
    swapped = 0;
    for (int i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = 1;
      }
    }
  }
}


int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);

  for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;

      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

  int temp = arr[i + 1];
  arr[i + 1] = arr[high];
  arr[high] = temp;

  return (i + 1);
}

void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);

    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}
void merge(int arr[], int left[], int left_size, int right[], int right_size) {
  int i = 0, j = 0, k = 0;

  while (i < left_size && j < right_size) {
    if (left[i] <= right[j]) {
      arr[k++] = left[i++];
    } else {
      arr[k++] = right[j++];
    }
  }

  while (i < left_size) {
    arr[k++] = left[i++];
  }

  while (j < right_size) {
    arr[k++] = right[j++];
  }
}
void mergeSort(int arr[], int size) {
  if (size <= 1) {
    return;
  }

  int mid = size / 2;
  int left[mid];
  int right[size - mid];

  for (int i = 0; i < mid; i++) {
    left[i] = arr[i];
  }

  for (int i = mid; i < size; i++) {
    right[i - mid] = arr[i];
  }

  mergeSort(left, mid);
  mergeSort(right, size - mid);

  merge(arr, left, mid, right, size - mid);
}
void heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest != i) {
    int temp = arr[i];
    arr[i] = arr[largest];
    arr[largest] = temp;

    heapify(arr, n, largest);
  }
}

void heapSort(int arr[], int n) {
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  for (int i = n - 1; i >= 0; i--) {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
heapify(arr, i, 0);
  }
}

void shellSort(int arr[], int n) {
  int gap = n / 2;

  while (gap > 0) {
    for (int i = gap; i < n; i++) {
      int temp = arr[i];
      int j;

      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }

      arr[j] = temp;
    }

    gap /= 2;
  }
}


void printArray(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main() {
	int n; 

  
  printf("Nhap so luong phan tu cua mang: ");
  scanf("%d", &n);

  
  int arr[n];

  
  for (int i = 0; i < n; i++) {
    printf("Nhap phan tu thu %d: ", i + 1);
    scanf("%d", &arr[i]);
  }
  
  
  

  printf("Mang ban dau:\n");
  printArray(arr, n);

  selectionSort(arr, n);
  
  

  printf("selectionSort:\n");
  printArray(arr, n);
  
  insertionSort(arr, n);
  printf("insertionSort : \n");
  printArray(arr, n);
  
  interchangeSort(arr, n);
  printf("interchangeSort : \n");
  printArray(arr, n);
  
  bubbleSort(arr, n);
  printf("bubbleSort : \n");
  printArray(arr, n);
  
  
  quickSort(arr, 0, n - 1);
  printf("quickSort : \n");
  printArray(arr, n);
  
  mergeSort(arr, n);
  printf("mergeSort : \n");
  printArray(arr,n);
  
  heapSort(arr, n);
  printf("heapSort : \n");
  printArray(arr,n);
  
  shellSort(arr, n);
  printf("shellSort : \n");
  printArray(arr,n);
  

  return 0;
}