TSORT : used Quick Sort O(nlogn)

general
1

#include<stdio.h>
long arr[1000001];
quicksort(long,long);
partition(long,long);
main()
{
long T=0,i=0,temp=0,j=0;
scanf("%ld",&T);
while(i<T)
{
scanf("%ld",&arr[i]);
i++;
}

quicksort(0,T-1);

i=0;
while(i<T)
{
printf("%ld\n",arr[i]);
i++;
}
}

quicksort(long start,long end)

{
long pindex;
if(start<end)
{
pindex = partition(start,end);
quicksort(start,pindex-1);
quicksort(pindex+1,end);
}

}

partition(long start,long end)
{
long i ,pivot , pindex,temp;
pivot = end;
pindex = start;
i=start;
while(i<end)
{
if(arr[i]<=arr[pivot])
{
temp = arr[i];
arr[i] = arr[pindex] ;
arr[pindex] = temp;

         pindex = pindex +1;

     }
 i++;
 }


 temp = arr[pivot];
 arr[pivot] = arr[pindex];
 arr[pindex] = temp;

 return(pindex);

}

Comments
Guys i’m here trying “Quick Sort” O(nlogn) and i guess this is good sorting technique and among one of the fastest and still im getting time limit error … Plz if any of you guys can help me in optimizing so that i can decrease Execution and compilation time
i tried fast IO but was not able to understand its code and it didnt work for me.

2

Quicksort is having Best case complexity as O(nlogn) and worst case complexity as O(n^n)…!! Thus your code must be exceeding time limit for worst case. Use Merge sort or Heap Sort both are having best case and worst case complexity as O(nlogn). OR go for hash sort or counting sort

here is the link: http://ideone.com/HKcedJ

Execution Time: 2.15 sec

Execution Time with fast I/O: 1.29 sec

As constraints are given as N [0 <= N <= 10^6] , we can create an array of size 10^6 initialized to zero at first, then according to the input , increase the count of the value at the index of that number!! And then we can directly print sorted numbers using that array!

1 Like
3

Instead of quick sort use merge sort.

4

hey @rgpt

For turbo sort counting sort is the best sorting technique i found.

Here is the Algorithm:

# variables:
#    input -- the array of items to be sorted; key(x) returns the key for item x
#    n -- the length of the input
#    k -- a number such that all keys are in the range 0..k-1
#    count -- an array of numbers, with indexes 0..k-1, initially all zero
#    output -- an array of items, with indexes 0..n-1
#    x -- an individual input item, used within the algorithm
#    total, oldCount, i -- numbers used within the algorithm
 
# calculate the histogram of key frequencies:
for x in input:
    count[key(x)] += 1
 
# calculate the starting index for each key:
total = 0
for i in range(k):   # i = 0, 1, ... k-1
    oldCount = count[i]
    count[i] = total
    total += oldCount
 
# copy to output array, preserving order of inputs with equal keys:
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1
 
return output

Take a look at my submission:

http://www.codechef.com/viewsolution/5204230

Let me explain you if you don’t know about counting sort, btw let me tell you guy at the top of problem scoreboard used counting sort to solve this problem.

Consider constraints as: Input number be <= 10, instead of 10^6.

Then,

Sample Input:
5
1
2
3
1
4

Initialize an array of size 12 (lets say a[12]) and assign 0 to each index either using memset() or using a for loop.

i.e. a[12] should be [0,0,0,0,0,0,0,0,0,0,0,0]

Get the input (say variable inp) from stdin and increment a[inp] by 1.

as input is 1 2 3 1 4,

So your code should work like:

inp=1, a[1]++ , [0,1,0,0,0,0,0,0,0,0,0,0]

inp=2, a[2]++ , [0,1,1,0,0,0,0,0,0,0,0,0]

inp=3, a[3]++ , [0,1,1,1,0,0,0,0,0,0,0,0]

inp=1, a[1]++ , [0,2,1,1,0,0,0,0,0,0,0,0]

inp=4, a[4]++ , [0,2,1,1,1,0,0,0,0,0,0,0]

Thats it,

Now using 2 for loop one to iterate over array a and second for range of values of array a print index,

i.e.

for(i=0;i<size;i++)
{
    for(j=0;j<a[i];j++)
        print(i);
}

Output will be :
2 times 1, 1 time 2, 3 and 4.

Output:
1
1
2
3
4

Code execution time : 0.56 sec using fast input and output

Hope You understood… :slight_smile:

1 Like
5

I don’t know the reason, but your solution will get accepted if you use inbuilt qsort() function instead of writing it.

6

#include<stdio.h>
int swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;

}
int partition(int arr[],int start,int end)
{
int pivot=arr[end];
int pIndex=start;
int i;
for(i=start;i<end;i++)
{
if(arr[i]<=pivot)
{
swap(&arr[i],&arr[pIndex]);
pIndex++;

    }
}
swap(&arr[pIndex],&arr[end]);
return pIndex;

}
void quicksort(int A[],int start,int end)
{
if(start<end)
{
int pIndex=partition(A,start,end);
quicksort(A,start,pIndex-1);
quicksort(A,pIndex+1,end);
}
}
int main()
{
int a,b,c;
scanf("%d",&a);
int Ar[a];
for(b=0;b<a;b++)
{
scanf("%d",&Ar[b]);
}
quicksort(Ar,0,a-1);
for(c=0;c<a;c++)
{
printf("%d\n",Ar[c]);
}
return 0;
}
Please point out precisely why it id giving TLE?

7

You can also use Counting SOrt approach.

I implemented it using STL Map in C++.

Here’s my


[1]


  [1]: https://www.codechef.com/viewsolution/10633578
1 Like