You are not logged in. Please login at www.codechef.com to post your questions!

×

How to make this faster? This is giving TLE for QUALPREL

enter code here
#include<stdio.h>
#include<stdlib.h>

int partition(int *arr, int start, int end){  
  int i=start+1, j=end, temp;  
  while(i<j){  
    while(arr[i]>=arr[start]){
      i++;
    }
    while(arr[j]<arr[start]){
      j--;
    }
    if(i<j){
      temp=arr[i];
      arr[i]=arr[j];
      arr[j]=temp;
      j--;
    }
}
temp=arr[start];
arr[start]=arr[j];
arr[j]=temp;
return j;
}
void quicksort(int *arr, int start, int end){
  if(start<end){
    int index=partition(arr, start, end);
    quicksort(arr, start, index-1);
    quicksort(arr, index+1, end);
  }
}
int main(){
int i, t, n, k, count, *ptr;
scanf("%d", &t);
while(t--){
  scanf("%d %d", &n, &k);
  ptr=(int*)malloc(n*sizeof(int));
  for(i=0;i<n;i++){
    scanf("%d", &ptr[i]);
  }
  count=0;
  quicksort(ptr, 0, n-1);
  i=0;
  while(ptr[i]>=ptr[k-1]){
    count++;
    i++;
  }
  printf("%d\n", count);
}

return 0;
}

asked 15 Dec '18, 15:56

hardikti's gravatar image

2★hardikti
11
accept rate: 0%

edited 15 Dec '18, 16:08


Your approach is correct. But your sorting algorithm is taking a long time. Either you can use built-in c's qsort, or you can learn some faster-sorting algorithms such as Merge Sort.

link

answered 15 Dec '18, 16:44

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×729

question asked: 15 Dec '18, 15:56

question was seen: 68 times

last updated: 15 Dec '18, 16:44