Paste Search Dynamic
Recent pastes
quickSort
  1. #include<iostream>
  2. #include<time.h>  
  3. using namespace std;
  4.  
  5. void swap(int &a, int &b)
  6. {
  7.     int temp=a;
  8.     a=b;
  9.     b=temp;
  10. }
  11.  
  12. void printArray(int a[], int n)
  13. {
  14.     cout<<"Mang tang dan: ";
  15.     for(int i=0; i<n; i++)
  16.     {
  17.         cout<<a[i]<<" ";
  18.     }
  19. }
  20.  
  21. void quickSort(int a[], int left, int right)
  22. {
  23.     int i, j, x;
  24.     if (left >= right)  return;
  25.     x = a[(left+right)/2];
  26.     i = left; j = right;
  27.     while(i < j)
  28.     {
  29.         while(a[i] < x)
  30.         {
  31.             i++;
  32.         }
  33.         while(a[j] > x)
  34.         {
  35.             j--;
  36.         }
  37.         if(i <= j)
  38.         {
  39.             swap(a[i], a[j]);
  40.             i++;
  41.             j--;
  42.         }
  43.     }
  44.     quickSort(a, left, j);
  45.     quickSort(a, i, right);
  46. }
  47.  
  48. struct Node
  49. {
  50.     int data;
  51.     Node* pNext;
  52. };
  53. struct LinkedList
  54. {
  55.     Node* Head;
  56.     Node* Tail;
  57. };
  58.  
  59. void init(LinkedList &list)
  60. {
  61.     list.Head = list.Tail =null;
  62. }
  63.  
  64. bool isEmpty(LinkedList list)
  65. {
  66.     return (list.Head==null && list.Tail == null);
  67. }
  68.  
  69. Node* createNode(int data)
  70. {
  71.     Node *newNode = new Node;
  72.     if(newNode == null) return null;
  73.     newNode->data=data;
  74.     newNode->pNext=null;
  75.     return newNode;
  76. }
  77.  
  78. void insertEmptyList(LinkedList &list, int x)
  79. {
  80.     Node *newNode = createNode(x);
  81.     list.Head=list.Tail=newNode;
  82. }
  83. void insertTail(LinkedList &list, int x)
  84. {
  85.     if(isEmpty(list)) insertEmptyList(list,x);
  86.     else
  87.     {
  88.         Node *newNode = createNode(x);
  89.         list.Tail ->pNext = newNode;
  90.         list.Tail=newNode;
  91.     }
  92. }
  93.  
  94. void swapNode(LinkedList &list, Node* pA, Node* pB)
  95. {
  96.     Node* p1 = new Node;
  97.     Node* p2 = new Node;
  98.     Node* p3 = new Node;
  99.     if(pA->pNext == pB)
  100.     {
  101.         if(pA == list.Head)
  102.         {
  103.             Node* temp= pB->pNext;
  104.             pB->pNext = pA;
  105.             pA->pNext = temp;
  106.             list.Head=pB;
  107.         }
  108.         else
  109.         {
  110.             for (Node* p = list.Head; p != null; p = p->pNext)
  111.                 if (p->pNext == pA)
  112.                 {
  113.                     p1 = p;
  114.                     p2 = p1->pNext;
  115.                     p3 = p2->pNext;
  116.                     break;
  117.                 }
  118.                 Node* temp = p3->pNext;
  119.                 p1->pNext = p3;
  120.                 p3->pNext = p2;
  121.                 p2->pNext = temp;
  122.         }
  123.     }
  124.     else
  125.     {
  126.         if(pA==list.Head)
  127.         {
  128.             for (Node* p = list.Head; p != null; p = p->pNext)
  129.             {
  130.                
  131.                 if (p->pNext == pB)
  132.                 {
  133.                     p1 = p;
  134.                     p2 = p->pNext;
  135.                     break;
  136.                 }
  137.             }
  138.             Node *Temp = p2->pNext;
  139.             p2->pNext = pA->pNext;
  140.             p1->pNext=pA;
  141.             pA->pNext = Temp;
  142.             list.Head=p2;
  143.         }
  144.         else
  145.         {
  146.             Node* p4 = new Node;
  147.        
  148.             for (Node* p = list.Head; p != null; p = p->pNext)
  149.             {
  150.                 if (p->pNext == pA)
  151.                 {
  152.                     p1 = p;
  153.                     p2 = p->pNext;
  154.                 }
  155.                 if (p->pNext == pB)
  156.                 {
  157.                     p3 = p;
  158.                     p4 = p->pNext;
  159.                     break;
  160.                 }
  161.             }
  162.             p1->pNext = p4;
  163.             Node* pTemp = p4->pNext;
  164.             p4->pNext = p2->pNext;
  165.             p3->pNext = p2;
  166.             p2->pNext = pTemp;
  167.         }
  168.     }
  169.     if (p2->pNext == null)
  170.         list.Tail = p2;
  171. }
  172.  
  173. void selectionSortLinkedList(LinkedList &list)
  174. {
  175.     Node* min;
  176.     for(Node* curNode1= list.Head; curNode1 !=list.Tail; curNode1=curNode1 ->pNext)
  177.     {
  178.         min=curNode1;
  179.         for(Node* curNode2=curNode1->pNext; curNode2 !=null; curNode2=curNode2->pNext)
  180.         {
  181.             if(curNode2 ->data < min->data) min=curNode2;
  182.         }
  183.         if(curNode1!=min) swap(curNode1->data,min->data);
  184.     }
  185. }
  186. void printLinkedList(LinkedList &list)
  187. {
  188.     if(isEmpty(list)) cout<<"Danh sach dang rong! ";
  189.     else
  190.     {
  191.         cout<<"nDanh sach lien ket tang dan: ";
  192.         Node *curNode = list.Head;
  193.         while(curNode != null)
  194.         {
  195.             cout<<curNode->data<<" ";
  196.             curNode = curNode -> pNext;
  197.         }
  198.     }
  199. }
  200.  
  201.  
  202. int main()
  203. {
  204.     int n;
  205.     cout<<"Nhap so phan tu cua day: ";
  206.     cin>>n;
  207.     int *a= new int[n];
  208.     LinkedList list;
  209.     init(list);
  210.     cout<<"Day so random duoc tao ra: ";
  211.     for(int i=0; i<n; i++)
  212.     {
  213.         int temp=rand()%25000;
  214.         cout<<temp<<" ";
  215.         a[i]=temp;
  216.         insertTail(list,temp);
  217.     }
  218.     cout<<endl;
  219.     cout<<endl;
  220.     clock_t start, end;
  221.     double time_use_array;
  222.     start = clock();
  223.     quickSort(a,0,n-1);
  224.     end = clock();
  225.     time_use_array = (double)(end - start) / clocks_per_sec;
  226.     printArray(a,n);
  227.  
  228.     double time_use_list;
  229.     start = clock();
  230.     selectionSortLinkedList(list);
  231.     end = clock();
  232.     time_use_list = (double)(end - start) / clocks_per_sec;
  233.     printLinkedList(list);
  234.     cout<<"nThoi gian chay cua Quick Sort tren mang: "<<time_use_array<<endl;
  235.     cout<<"Thoi gian chay cua Selection Sort tren DSLK: "<<time_use_list;
  236.     return 0;
  237. }
Parsed in 0.022 seconds