Translate

Chủ Nhật, 4 tháng 12, 2016

Sorting and Searching Algorithms

created by Frank


1. Sorting 

in this section, we will compare the performance of basic sorting algorithms: bubble sort, selection sort, insertion sort, quick sort, and heap sort.

  • in these algorithms, quick sort and heap sort are fastest but hardest to implement. (quick sort is usually fastest)
  • bubble sort is simplest but the its performance is lowest 
about the complexity of algorithms:
  • bubble sort: O(n2)
  • insertion sort: O(n2)
  • selection sort: O(n2)
  • quick sort: average is O(nlogn), worst case is O(n2)
  • heap sort: O(nlogn)
because these algorithms are common, we do not mention their principle here
below is source code of sort algorithms

1.1 bubble sort

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h><stdio .h="">
#include <stdlib.h><stdlib .h="">
#include <time.h><time .h="">
 
#define NUM 100000
 
int main()
{
  int arr[NUM];
  int i, j, k;
  int temp;
  double avg = 0;
  FILE *f;
 
  for (k = 0; k < 6; ++k)
  {
    char c = k + 48;
    char name[]={c};
    f = fopen(name, "r");
    printf("%s%s%s\n","reading file ", name,"..." );
    for (i = 0; i < NUM; ++i)
    {
      fscanf(f, "%d", &arr[i]);
    }
    fclose(f);
 
    printf("%s\n", "sorting ...");
    clock_t start = clock();
    for(i = (NUM - 1); i >= 0; i--)
    {
      for(j = 1; j <= i; j++)
      {
        if(arr[j-1] > arr[j])
        {
          temp = arr[j-1];
          arr[j-1] = arr[j];
          arr[j] = temp;
        }
      }
    }
    clock_t end = clock();
    printf("%s\n", "sorted...");
    double t = (double)(end - start)/CLOCKS_PER_SEC;
    avg += t;
    printf("time = %f\n\n",t);
  }
  printf("sum of time = %f\n",avg);
  printf("average time = %f\n", avg/6);
  // for(i = 0; i < NUM; i++)
  //   printf(" %d", arr[i]);
 
  // printf("\n");
  return 0;
}
</time></stdlib></stdio>

1.2 insertion sort


?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio .h="">
#include <stdlib .h="">
#include <time .h="">
 
#define NUM 100000
 
int main()
{
  int i, j, k;
  int arr[NUM];
  double avg = 0;
  FILE *f;
 
  for (k = 0; k < 6; ++k)
  {
    char c = k + 48;
    char name[]={c};
    f = fopen(name, "r");
    printf("%s%s%s\n","reading file ", name,"..." );
    for (i = 0; i < NUM; ++i)
    {
      fscanf(f, "%d", &arr[i]);
    }
    fclose(f);
 
    printf("%s\n", "sorting ...");
    clock_t start = clock();
   
    for (i=0; i < NUM; i++)
    {
          int index = arr[i];
          int j = i;
          while (j > 0 && arr[j-1] > index)
          {
             arr[j] = arr[j-1];
             j--;
          }
          arr[j] = index;
    }
    clock_t end = clock();
    printf("%s\n", "sorted...");
    double t = (double)(end - start)/CLOCKS_PER_SEC;
    avg += t;
    printf("time = %f\n\n",t);
  }
  printf("sum of time = %f\n",avg);
  printf("average time = %f\n", avg/6);
   
  return 0;
}</time></stdlib></stdio>

1.3 selection sort

?

  1. #include <stdio .h="">  
  2. #include <stdlib .h="">  
  3. #include <time .h="">  
  4.    
  5. #define NUM 100000  
  6.    
  7. int main()  
  8. {  
  9.   int i, j, k;  
  10.   int arr[NUM];  
  11.   double avg = 0;  
  12.   FILE *f;  
  13.    
  14.   for (k = 0; k < 6; ++k)  
  15.   {  
  16.     char c = k + 48;  
  17.     char name[]={c};  
  18.     f = fopen(name, "r");  
  19.     printf("%s%s%s\n","reading file ", name,"..." );  
  20.     for (i = 0; i < NUM; ++i)  
  21.     {  
  22.       fscanf(f, "%d", &arr[i]);  
  23.     }  
  24.     fclose(f);  
  25.    
  26.     printf("%s\n", "sorting ...");  
  27.     clock_t start = clock();  
  28.     for (i = 0; i < NUM-1; i++)  
  29.     {  
  30.         int min = i;  
  31.         for (j = i+1; j < NUM; j++)  
  32.             if (arr[j] < arr[min]) min = j;  
  33.         int temp = arr[i];  
  34.         arr[i] = arr[min];  
  35.         arr[min] = temp;  
  36.     }   
  37.     clock_t end = clock();  
  38.     printf("%s\n", "sorted...");  
  39.     double t = (double)(end - start)/CLOCKS_PER_SEC;  
  40.     avg += t;  
  41.     printf("time = %f\n\n",t);  
  42.   }  
  43.    
  44.   printf("sum of time = %f\n",avg);  
  45.   printf("average time = %f\n", avg/6);  
  46.     
  47.  return 0;  
  48. }  

1.4 quick sort

?

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <time.h>  
  4.    
  5. #define NUM 100000  
  6.    
  7. void quickSort( int[], int, int);  
  8. int partition( int[], int, int);  
  9.    
  10. void main()   
  11. {  
  12.  //int a[] = {7, 12, 1, -2, 0, 15, 4, 11, 9};  
  13.   int a[NUM];  
  14.  int i, k;  
  15.   long double avg = 0;  
  16.   FILE *f;  
  17.    
  18.   for (k = 0; k < 6; ++k)  
  19.   {  
  20.     char c = k + 48;  
  21.     char name[]={c};  
  22.     f = fopen(name, "r");  
  23.     printf("%s%s%s\n","reading file ", name,"..." );  
  24.     for (i = 0; i < NUM; ++i)  
  25.     {  
  26.       fscanf(f, "%d", &a[i]);  
  27.     }  
  28.     fclose(f);  
  29.    
  30.     printf("%s\n", "sorting...");  
  31.     clock_t begin = clock();  
  32.     quickSort(a, 0, NUM);  
  33.     clock_t end = clock();  
  34.     printf("%s\n", "sorted!!!");  
  35.    
  36.     long double t = (long double)(end - begin) / CLOCKS_PER_SEC;  
  37.     printf("time = %Lf\n\n", t);  
  38.     avg += t;  
  39.   }  
  40.    
  41.  printf("sum of time = %Lf\n",avg);  
  42.   printf("average time = %Lf\n", avg/6);  
  43.     
  44.      
  45.    
  46.  // printf("\n\nSorted array is:  ");  
  47.  // for(i = 0; i < NUM; ++i)  
  48.  //  printf(" %d ", a[i]);  
  49.    
  50. }  
  51.    
  52. void quickSort( int a[], int l, int r)  
  53. {  
  54.    int j;  
  55.    
  56.    if( l < r )   
  57.    {  
  58.        j = partition( a, l, r);  
  59.        quickSort( a, l, j-1);  
  60.        quickSort( a, j+1, r);  
  61.    }  
  62.     
  63. }  
  64.    
  65. int partition( int a[], int l, int r) {  
  66.    int pivot, i, j, t;  
  67.    pivot = a[l];  
  68.    i = l; j = r+1;  
  69.      
  70.    while( 1)  
  71.    {  
  72.     do ++i; while( a[i] <= pivot && i <= r );  
  73.     do --j; while( a[j] > pivot );  
  74.     if( i >= j ) break;  
  75.     t = a[i]; a[i] = a[j]; a[j] = t;  
  76.    }  
  77.    t = a[l]; a[l] = a[j]; a[j] = t;  
  78.    return j;  
  79. }  

1.5 heap sort

?

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <time.h>  
  4.    
  5. #define NUM 100000  
  6.     
  7. // To heapify a subtree rooted with node i which is  
  8. // an index in arr[]. n is size of heap  
  9.    
  10. void heapify(int arr[], int n, int i)  
  11. {  
  12.     int largest = i;  // Initialize largest as root  
  13.     int temp;  
  14.     int l = 2*i + 1;  // left = 2*i + 1  
  15.     int r = 2*i + 2;  // right = 2*i + 2  
  16.     
  17.     // If left child is larger than root  
  18.     if (l < n && arr[l] > arr[largest])  
  19.         largest = l;  
  20.     
  21.     // If right child is larger than largest so far  
  22.     if (r < n && arr[r] > arr[largest])  
  23.         largest = r;  
  24.     
  25.     // If largest is not root  
  26.     if (largest != i)  
  27.     {  
  28.         //Swap(&arr[i], &arr[largest]);  
  29.         temp = arr[i];  
  30.         arr[i] = arr[largest];  
  31.         arr[largest] =temp;  
  32.     
  33.         // Recursively heapify the affected sub-tree  
  34.         heapify(arr, n, largest);  
  35.     }  
  36. }  
  37.     
  38. // main function to do heap sort  
  39. void heapSort(int arr[], int n)  
  40. {  
  41.     // Build heap (rearrange array)  
  42.     int i;  
  43.     int temp;  
  44.     for (i = n / 2 - 1; i >= 0; i--)  
  45.         heapify(arr, n, i);  
  46.     
  47.     // One by one extract an element from heap  
  48.     for (i=n-1; i>=0; i--)  
  49.     {  
  50.         // Move current root to end  
  51.         //Swap(&arr[0], &arr[i]);  
  52.         temp = arr[0];  
  53.         arr[0] = arr[i];  
  54.         arr[i] =temp;  
  55.     
  56.         // call max heapify on the reduced heap  
  57.         heapify(arr, i, 0);  
  58.     }  
  59. }  
  60.     
  61. // Driver program  
  62. int main()  
  63. {  
  64.     //int arr[] = {12, 11, 13, 5, 6, 7, 1, 2, 5, 7, 9, 10};  
  65.     int a[NUM];  
  66.     int i, k;  
  67.     long double avg = 0;  
  68.     FILE *f;  
  69.    
  70.    
  71.      for (k = 0; k < 6; ++k)  
  72.     {  
  73.       char c = k + 48;  
  74.       char name[]={c};  
  75.       f = fopen(name, "r");  
  76.       printf("%s%s%s\n","reading file ", name,"..." );  
  77.       for (i = 0; i < NUM; ++i)  
  78.       {  
  79.         fscanf(f, "%d", &a[i]);  
  80.       }  
  81.       fclose(f);  
  82.    
  83.       printf("%s\n", "sorting ...");  
  84.       clock_t begin = clock();  
  85.       heapSort(a, NUM);  
  86.       clock_t end = clock();  
  87.       printf("%s\n", "sorted...");  
  88.    
  89.       long double t = (long double)(end - begin) / CLOCKS_PER_SEC;  
  90.       printf("time = %Lf\n\n", t);  
  91.       avg += t;  
  92.     }  
  93.        
  94.     printf("sum of time = %Lf\n",avg);  
  95.     printf("average time = %Lf\n", avg/6);  
  96.        
  97. }  

for simple, we use rand() function to generate input data of programs. the number of test case is 5 and the result is average of them.
download input data
The system for implementation: 
  • Intel core I7-6820HQ CPU 2.7 GHz
  • OS ubuntu 12.04 64bit
  • Compiler: gcc ubuntu/linaro 4.6.3
See run time of these algorithms, we can see the dramatic difference among algorithms

bubble
Selection
Insertion
Quick
Heap
Test case 0
30.30
9.38
6.01
0.02
0.03
Test case 1
30.39
9.39
5.99
0.01
0.03
Test case 2
30.41
9.48
5.98
0.01
0.02
Test case 3
30.38
9.43
5.95
0.01
0.03
Test case 4
30.74
9.73
5.98
0.01
0.03
Test case 5
30.38
9.55
6.08
0.01
0.03
Average 
30.4333
9.4933
5.9983
0.0133
0.0283

download input data here

2. Searching 

in this section, we will review 2 common searching: sequence searching and binary searching. 
  • sequence searching: 

References

Người đăng:

Không có nhận xét nào:

Đăng nhận xét

Đăng ký: Đăng Nhận xét (Atom)