JonsenElizee

Software Developing Blog

"An idea is fragile . It can be killed by a scornful smile or a yawn .It can be mound down by irony and scared to death by a cold look."
"Most cultures throughout human history have not liked creative individuals .They ignore them or kill them.It is a very efficient way of stopping creativity."

------Advertising boss Charles Browe and Howard Gardner ,professor at Harvard

Find kth in O(n) TC


Refer Find kth number in O(n) TC

#include <stdio.h>

#include <stdlib.h>

#include <time.h>



#define N 20



void init_a(int A[])

{

  int i = 0;

  for(;i<N;i++)

    A[i] = rand()%100; 

}



void print_array(int A[])

{

   int i = 0;

   for(;i<N;i++)

    {

     if(i==9)

      printf("%d\n",A[i]);

     else

      printf("%d\t",A[i]);

    } 

}



void swap(int* a, int* b)

{

   int tmp = *a;

   *a = *b;

   *b = tmp; 

}



int rand_partition(int A[], int start, int end)

{

   int i = start-1;

   int j = start;

   int num = rand()%(end-start+1)+start;

   swap(A+num,A+end);

   int x = A[end];

   

   for(;j<end;j++)

    {

      if(A[j]<=x)

       {

          i++;

         swap(A+i,A+j); 

        } 

     }

   swap(A+i+1,A+end);



   return i+1;

}





int random_select(int A[], int start, int end, int k)

{

  int i = 0; 

  if(start == end)

    return A[start];

    

  int q = rand_partition(A, start, end);

   i = q-start+1;

  

  if(i == k)

    return A[q];

  else if(i<k)

    return random_select( A, q+1, end, k-i);

  else

    return random_select( A, start, q-1, k); 

} 



void quick_sort(int A[], int start, int end)

{

  if(start<end) 

   {

     int q = rand_partition(A, start, end);

  

      quick_sort( A, q+1, end);

      quick_sort( A, start, q-1);

  } 

} 

   

int main(int argc, char *argv[])

{

  int A[N];

  int num = 0;

  int res = 0;

  srand((unsigned)time(NULL));

   init_a(A);

   print_array(A);

  

   num = rand()%(N-10)+5;

  printf("we begin select %d minimun number\n",num);

   res = random_select( A, 0 , N-1, num); 

  printf("and num is %d\n",res);

  

   quick_sort( A, 0 , N-1);

  printf("after quick sort the array is:\n");

   print_array(A);

  system("PAUSE");    

  return 0;

}

posted on 2010-10-24 01:17 JonsenElizee 閱讀(418) 評論(0) 編輯收藏引用所屬分類: Data Structures & Algorithms

JonsenElizee

JonsenElizee

隨筆分類(28)

最新評論