fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MAX 100
  3. /*
  4. con thieu may cai sort nua nhung khong biet thay co day khong
  5. bo sung sau
  6. */
  7. void print(int *a, int array_size);
  8. void print(int *a, int left, int right);
  9.  
  10. void shuffle(int *array, size_t n)
  11. {
  12.     srand(time(0));
  13.     if (n > 1)
  14.     {
  15.         size_t i;
  16.         for (i = 1; i < n - 1; i++)
  17.         {
  18.           size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
  19.           int t = array[j];
  20.           array[j] = array[i];
  21.           array[i] = t;
  22.         }
  23.     }
  24. }
  25. // quicksort
  26. void swap_(int *a, int *b) {
  27.     int tmp = *a;
  28.     *a = *b;
  29.     *b = tmp;
  30. }
  31.  
  32. int partition_(int *a, int left, int right) {
  33.     int pivot = a[right];
  34.     int i = left - 1;
  35.  
  36.     for(int j = left; j <= right - 1; j ++) {
  37.         if(a[j] < pivot) {
  38.             i++;
  39.             swap_(&a[j],&a[i]);
  40.         }
  41.     }
  42.     swap_(&a[i+1],&a[right]);
  43.     return (i+1);
  44. }
  45.  
  46. int quicksort(int *a, int left, int right) {
  47.     int pivot_index;
  48.     if(left < right) {
  49.         int pivot_index = partition_(a, left, right);
  50.         printf("%d\n",pivot_index);
  51.         quicksort(a,left,pivot_index - 1);
  52.         print(a,left,pivot_index-1);
  53.         quicksort(a, pivot_index + 1, right);
  54.         print(a,pivot_index-1, right);
  55.  
  56.     }
  57.  
  58. }
  59. //
  60.  
  61. // merge sort
  62.  
  63. void merge_(int *a,int left, int mid, int right) {
  64.     int length = right - left + 1;
  65.     int tmp[right+1];
  66.     int i = left; // dau cua nua trai
  67.     int j = mid + 1; // dau cua nua phai;
  68.     for(int k = left ; k <= right ;k++) {
  69.         if(i > mid) {
  70.             tmp[k] = a[j];
  71.             j++;
  72.         } else if(j > right) {
  73.             tmp[k] = a[i];
  74.             i++;
  75.         } else {
  76.                 if(a[i] < a[j]) {
  77.                 tmp[k] = a[i];
  78.                 i++;
  79.             } else if( a[i] > a[j]) {
  80.                 tmp[k] = a[j];
  81.                 j++;
  82.             }
  83.         }
  84.     }
  85.     for (int k = left; k <= right; k++)
  86.     {
  87.         a[k] = tmp[k];
  88.     }
  89.  
  90. }
  91.  
  92. void merge_sort(int *a,int left, int right) {
  93.     if( left < right) {
  94.         int mid = (left + right)/2;
  95.         merge_sort(a,left,mid);
  96.         merge_sort(a,mid+1,right);
  97.         merge_(a,left,mid,right);
  98.     }
  99.     print(a,left,right);
  100. }
  101.  
  102. void print(int *a, int array_size) {
  103.     for(int i = 0 ; i <  array_size ; i++) {
  104.         printf("%-5d",a[i]);
  105.     }
  106.     printf("\n");
  107. }
  108. void print(int *a, int left, int right) {
  109.     for(int i = left ; i <=  right ; i++) {
  110.         printf("%-5d",a[i]);
  111.     }
  112.     printf("\n");
  113. }
  114. /*
  115.     sap xep chen
  116. */
  117. void inserttion_sort(int *a, int array_size) {
  118.     int i,j, last;
  119.     for(i = 1; i < array_size ; i++) {
  120.         last = a[i];
  121.         j = i;
  122.         while((j > 0) && ( a[j-1] > last)) {
  123.             a[j] = a[j-1];
  124.             j = j - 1;
  125.         }
  126.         a[j] = last;
  127.         print(a,array_size);
  128.     }
  129. }
  130. /*
  131.     sap xep lua chon
  132. */
  133.  
  134. void selection_sort(int *a, int array_size) {
  135.     int i,j,min_,tmp;
  136.     for(i = 0; i < array_size - 1 ; i++) {
  137.         min_ = i;
  138.         for( j = i + 1; j < array_size ; j++) {
  139.             if(a[j] < a[min_]) {
  140.                 min_ = j;
  141.             }
  142.         }
  143.         swap_(&a[i],&a[min_]);
  144.         print(a,array_size);
  145.     }
  146. }
  147.  
  148. /*
  149.     sap xep noi bot
  150. */
  151.  
  152. void bubble_sort(int *a, int array_size) {
  153.     int i,j;
  154.     for(i = array_size - 1; i >= 0; i--) {
  155.         printf("i = %-10d\n",i);
  156.         for( j = 1 ; j <= i ; j++) {
  157.             if(a[j-1] > a[j]) {
  158.                 swap_(&a[j],&a[j-1]);
  159.                 print(a,array_size);
  160.             }
  161.         }
  162.         printf("\n");
  163.     }
  164. }
  165.  
  166.  
  167. /*
  168.     sap xep vun dong
  169. */
  170.  
  171. int root_tree(int *a) {
  172.     return a[1];
  173. }
  174.  
  175. int left_child(int i) {
  176.     return (i<<1);
  177. }
  178.  
  179. int right_child(int i) {
  180.     return 2*i+1;
  181. }
  182.  
  183. int parent_node(int i) {
  184.     return i<<1 + 1;
  185. }
  186.  
  187. int heap_size(int length_A) {
  188.     return length_A;
  189. }
  190.  
  191. void max_heapify(int *a, int i, int heap_size) {
  192.     int left, right,n;
  193.     int largest;
  194.     n = heap_size;
  195.     left = left_child(i);
  196.     right = right_child(i);
  197.     if(left<= n && a[left] > a[i]) largest = left;
  198.     else largest = i;
  199.     if(right<=n && a[right] > a[largest]) largest = right;
  200.  
  201.     if(largest != i)  {
  202.         swap_(&a[i],&a[largest]); // nghia la phan tu max la con trai hoac con phai
  203.         max_heapify(a,largest,n);
  204.     }
  205.  
  206. }
  207.  
  208. void min_heapify(int *a, int i, int heap_size) {
  209.     int left, right,n;
  210.     int smallest;
  211.     n = heap_size;
  212.     left = left_child(i);
  213.     right = right_child(i);
  214.     if(left<= n && a[left] < a[i]) smallest = left;
  215.     else smallest = i;
  216.     if(right<=n && a[right] < a[smallest]) smallest = right;
  217.  
  218.     if(smallest != i)  {
  219.         swap_(&a[i],&a[smallest]); // nghia la phan tu max la con trai hoac con phai
  220.         min_heapify(a,smallest,n);
  221.     }
  222.  
  223. }
  224. // neu chay bang mang thi phai set = 10
  225. // neu chay bang hang doi thi set bang 3
  226. int length_A = 10; // la kich thuoc that cua heap, khong chua phan tu a[0] = 0 mac dinh
  227. /*
  228.     khoi phuc tinh chat dong cua ca cay O(logn)
  229. */
  230. void build_max_heap(int *a) {
  231. //    printf("%d",a[2]);
  232.     int n = heap_size(length_A);
  233.     int i;
  234.     for(i = n/2 ; i>=1 ; i--) {
  235.         max_heapify(a,i,n);
  236.     }
  237. }
  238.  
  239. void build_min_heap(int *a) {
  240.     int n = heap_size(length_A);
  241.     int i;
  242.     for(i = n/2 ; i>=1 ; i--) {
  243.         min_heapify(a,i,n);
  244.     }
  245. }
  246.  
  247. /*
  248.     bat dau sap xep
  249. */
  250.  
  251. void heap_sort(int *a) {
  252. //    build_max_heap(a);
  253.     build_min_heap(a);
  254.     int i;
  255.     int n = heap_size(length_A);
  256.     for(i = n; i>=2 ; i--) {
  257.         swap_(&a[1],&a[i]);
  258. //        max_heapify(a,1,i-1);
  259.           min_heapify(a,1,i-1);
  260.     }
  261. }
  262.  
  263.  
  264. /*
  265. hang doi uu tien
  266. */
  267. int N; // so luong phan tu trong hang doi uu tien
  268. /*
  269.     phai luon duy tri tinh chat dong
  270. */
  271. void insert_element_queue_priority(int *a, int val) {
  272.     length_A = length_A + 1;
  273.     int i = length_A;
  274.     a[i] = val;
  275.     if(length_A >= 3) {
  276.         build_max_heap(a);
  277.     } else {
  278.         max_heapify(a,1,length_A);
  279.     }
  280. }
  281. /*
  282.     tra lai phan tu lon nhat trong hang doi uu tien
  283. */
  284. int max_priority_queue(int *a) {
  285.     return a[1];
  286. }
  287.  
  288.  
  289. /*
  290.     tra lai phan tu lon nhat va loai bo no ra khoi hang doi
  291. */
  292. int extract_max_priority_queue(int *a) {
  293.     if( length_A == 0) {
  294.         printf("queue empty\n");
  295.         return -1;
  296.     } else {
  297.         int tmp = a[length_A];
  298.         swap_(&a[1], &a[length_A]);
  299.         length_A = length_A - 1;
  300.         build_max_heap(a);
  301.         return a[length_A];
  302.     }
  303. }
  304. /*
  305.     tang khoa cua phan tu x(index) len gia tri  k
  306.     suy ra k > x
  307. */
  308. void increase_key(int *a,int x, int key) {
  309.     // voi truong hop max
  310.     if( key < a[x]) {
  311.         printf("khoa moi nho hon khoa hien tai\n");
  312.  
  313.     } else {
  314.         a[x] = key;
  315.         build_max_heap(a);
  316.     }
  317. }
  318. int main() {
  319. //    int a[MAX] = {10,-75,-100,0,71,-48,58,34,-70,-32};
  320. //    int array_size = 10;
  321. //    print(a,array_size);
  322. //    inserttion_sort(a,array_size);
  323. //    selection_sort(a,array_size);
  324. //    bubble_sort(a,array_size);
  325. //    merge_sort(a,0,array_size-1);
  326. //    quicksort(a,0,array_size-1);
  327.  
  328.     int A[MAX] = {0,4,1,3,2,16,9,10,14,8,7};
  329.     print(A,length_A + 1); // do bao gom phan tu dau tien  = 0
  330.     shuffle(A,length_A + 1);
  331.     print(A,length_A + 1);
  332.     heap_sort(A);
  333.     print(A,length_A+1);
  334.  
  335. //    int a[MAX];
  336. //    a[0] = 0;
  337. //    a[1] = 10;
  338. //    a[2]  = 7;
  339. //    a[3] = 9;
  340. //    print(a,length_A+1);
  341. //    insert_element_queue_priority(a,15);
  342. //    print(a,length_A+1);
  343. //    printf("phan tu lon nhat trong hang doi uu tien %d\n", max_priority_queue(a));
  344. //    extract_max_priority_queue(a);
  345. //    print(a,length_A+1);
  346. //    extract_max_priority_queue(a);
  347. //    print(a,length_A+1);
  348. //    extract_max_priority_queue(a);
  349. //    print(a,length_A+1);
  350. //    extract_max_priority_queue(a);
  351. //    print(a,length_A+1);
  352. //    extract_max_priority_queue(a);
  353. //
  354. //    insert_element_queue_priority(a,10);
  355. //    insert_element_queue_priority(a,7);
  356. //    insert_element_queue_priority(a,9);
  357. //    insert_element_queue_priority(a,15);
  358. //    print(a,length_A+1);
  359. //    increase_key(a,4,50);
  360. //    print(a,length_A+1);
  361.  
  362.     return 0;
  363. }
  364.  
Success #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0    4    1    3    2    16   9    10   14   8    7    
0    8    10   3    1    9    2    14   16   7    4    
0    16   14   10   9    8    7    4    3    2    1
https://ideone.com/ednKTB
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!