누군가 피워놓은 모닥불

SMALL

일반 퀵 정렬

 

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>
#include <time.h>
#define size 12
#define num_threads 12
void quicksort(int numbers[]);
void q_sort(int numbers[], int left, int right);
void quicksort(int numbers[])
{
 q_sort(numbers, 0, size-1);
}
void q_sort(int numbers[], int left, int right)
{
 int pivot, l_hold, r_hold;
 l_hold = left;
 r_hold = right;
 pivot = numbers[left];
 while (left < right)
 {
  while((numbers[right] >= pivot) && (left < right))
   right --;
 
  if(left != right)
  {
   numbers[left] = numbers[right];
  }
  while((numbers[left] <= pivot) && (left < right))
   left ++;
  if(left != right)
  {
   numbers[right] = numbers[left];
   right --;
  }
 }
 numbers[left] = pivot;
 pivot = left;
 left= l_hold;
 right = r_hold;
 if(left < pivot)
  q_sort(numbers, left, pivot-1);
 if(right > pivot)
  q_sort(numbers, pivot+1, right);
}
 
int main()
{
 struct timeval t1,t2;
 int data[size];
 int i;
 pthread_t threads[size];
 srand(time(NULL));
 gettimeofday(&t1,NULL);
 printf("   [Sort Before]\n");
 for(i=0; i<size; i++){
  data[i] = rand() % 1000;
 printf("\t%03u ",data[i]);  
 }
 printf("\n");
 
 gettimeofday(&t2,NULL);
 printf("   [Sort After]\n"); 
 quicksort(data);
 for(i=0; i<size; i++)
 printf("\t%03u ",data[i]);
 printf("\n%.5f elapsed \n", (double)(t2.tv_sec - t1.tv_sec) +
  (double)(t2.tv_usec - t1.tv_usec) / 1.e6);
 return 0;
}
 
cs

 

 

 

 

Pthread를 이용한 Quick 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>
#include <time.h>
 
#define size 12
#define num_threads 8
 
void quicksort(int numbers[]);
void q_sort(int numbers[], int left, int right);
 
int main()
{
     int data[size];
     int i;
 
    pthread_t threads[size];
     srand(time(NULL));
 
    printf("   [Sort Before]\n");
 
    for(i=0; i<size; i++)
    {
          data[i] = rand() % 1000;
         printf("\t%03u ",data[i]);  
     }
 
    printf("\n"); 
 
    for(i=0; i<num_threads; i++)
    {
           pthread_create(&threads[i], NULL, quicksort, data);
      }
 
    for(i=0; i<num_threads; i++)
    {
          pthread_join(threads[i], NULL);
     }
 
    printf("   [Sort After]\n",data[i]);
 
    for(i=0; i<size; i++)
    {
         printf("\t%03u ",data[i]);
     }
 
     printf("\n");
    return 0;
}
 
void quicksort(int numbers[])
{
     q_sort(numbers, 0, size-1);
}
 
void q_sort(int numbers[], int left, int right)
{
 
     int pivot, l_hold, r_hold;
 
     l_hold = left;
      r_hold = right;
     pivot = numbers[left];
 
     while (left < right)
     {
          while((numbers[right] >= pivot) && (left < right))
           right --;
 
          if(left != right)
          {
               numbers[left] = numbers[right];
          }
      
        while((numbers[left] <= pivot) && (left < right))
        left ++;
  
          if(left != right)
          {
               numbers[right] = numbers[left];
               right --;
          }
 
     }
     
    numbers[left] = pivot;
     pivot = left;
     left= l_hold;
     right = r_hold;
 
     if(left < pivot)
          q_sort(numbers, left, pivot-1);
 
     if(right > pivot)
          q_sort(numbers, pivot+1, right);
}
cs

 

 


 

LIST
저작자표시 비영리 동일조건

'개인자료 > 프로그래밍' 카테고리의 다른 글

[OpenCL] PhotoMosaic  (0) 2014.05.29
[OpenCL] Photomosaic in MPI  (3) 2014.05.29
[OpenCL] Photomosaic in Multidevice  (0) 2014.05.29
[OpenCL] PhotoMosaic  (0) 2014.05.28
Pthread QuickSort  (0) 2014.05.28
Semaphore single producer single consumer problem  (0) 2014.05.28
Thread Affinity  (0) 2014.05.28
[OpenCL] 벡터 덧셈(Vec Add)  (0) 2014.05.28
거짓 공유(False Sharing, 가짜 공유)  (0) 2014.05.28
Linux 환경에서 C 기반으로 테트리스 구현하기  (2) 2014.05.28
누군가 피워놓은 모닥불 블로그의 첫 페이지로 이동

티스토리툴바