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

   :: 首页 :: 新随笔 ::  ::  :: 管理 ::

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 阅读(382) 评论(0)  编辑 收藏 引用 所属分类: Data Structures & Algorithms
By JonsenElizee