# https://www.codechef.com/problems/HORSES

how can i make i run faster??

#include
using namespace std;

void selsort(int ar[],int n)
{
for(int i=0;i<n-1;i++)
{
int imin=i;
for(int j=i+1;j<n;j++)
{
if(ar[j]<ar[imin])
imin=j;
}

``````	int temp=ar[i];
ar[i]=ar[imin];
ar[imin]=temp;

}
``````

}

int main()
{
int t,n;
scanf("%d",&t);
int s[t];
for(int i=0;i<t;i++)
{
scanf("%d",&n);
for(int j=0;j<n;j++)
{
scanf("%d",&s[j]);
}

``````selsort(s,n);
int diff,min=s[1];
for(int i=0;i<n;i++)
{
diff=(s[i+1]-s[i]);
if(diff<min&&diff>=0)
{
min=diff;
}

}
printf("%d\n",min);
}

return 0;
``````

}

Sort the array using mergesort or quicksort as they are faster than selection sort. Once the array is sorted, pick 2 adjacent elements at every step and compute the difference between the two. The minimum difference obtained will be our answer. This is because for every horse, the horse closest to its skill will be represented by the element just before it, and just after it.

The sorting process takes O(nlogn) time, and computing the difference of every element with its neighbour takes O(n) time, so the overall complexity of the code reduces to O(nlogn) + O(n) = O(nlogn), from the previous O(n^2) because of the selection sort.