Hi,
We need to sort 7 numbers each of 4 digits. What is the number of
comparisons in worst case . Options are as follows:
1) 40
2) 38
3) 47
4) 280
Please also explain why so?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
^^ true, sort the rows and then a K-way merge.
On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote:
I guess sort the array such that elements are sorted finally in such a way
that if we print them row by row, the result is a sorted array.
K-way merge can be useful.
*
@Shady Rows are already sorted ...
On Wed, Jan 11, 2012 at 1:53 PM, shady sinv...@gmail.com wrote:
^^ true, sort the rows and then a K-way merge.
On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote:
I guess sort the array such that elements are sorted finally in such
But the question says without extra space ? How do we do that without space
?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:24 AM, Ankur
If we use K merge I think the time complexity would be nm lognm
I think we must try doing in O(m*n)
On Wed, Jan 11, 2012 at 1:54 PM, Ankur Garg ankurga...@gmail.com wrote:
@Shady Rows are already sorted ...
On Wed, Jan 11, 2012 at 1:53 PM, shady sinv...@gmail.com wrote:
^^ true, sort the
How can it be mn log mn ?
it will be O(mn) as we elements are sorted, we simply pick minimum at each
iteration of the loop. Since there are mn elements, so complexity will be
O(mn).
Correct me if m wrong.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of
Where do we store the sorted list ? How do we do it in place ?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:34 AM, Sanjay Rajpal
Question says without extra space how can you sort it using K way merge.
eg:-
input:-
1 3 4 8 9
2 5 18 25 50
6 7 22 45 55
output:-
12 3 45
67 8 9 18
22 25 45 50 55
On Wed, Jan 11, 2012 at 2:05 PM, Sanjay Rajpal sanjay.raj...@live.inwrote:
Where do
@Lucifer : I came up with a similar algorithm as yours but I dont
understand your complexity analysis : sum over all i (1 to M} { i*(M+N-i)
} .
Shouldnt it be M * sum over all i(1 to N) {(M+N-i)} ? M= no of
columns, N= no of rows . Since we always have the min element at the 0th
column of
only reason for considering k way merge was to do it O(n*m) time,
but currently i am having problem merging even two sorted arrays in time
linear to the sum of their size without extra space. any help ?
On Wed, Jan 11, 2012 at 2:30 PM, atul anand atul.87fri...@gmail.com wrote:
Question says
Given 2D array.
The rows are sorted in ascending order and the colums are sorted in
ascending order.
We have to sort the whole matrix in ascending array.
We cannot use extra space.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
sort the whole matrix in ascending array means?
can you please explain ?
On Wed, Jan 11, 2012 at 12:53 PM, atul anand atul.87fri...@gmail.comwrote:
Given 2D array.
The rows are sorted in ascending order and the colums are sorted in
ascending order.
We have to sort the whole matrix in
I guess sort the array such that elements are sorted finally in such a way
that if we print them row by row, the result is a sorted array.
K-way merge can be useful.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra -
Given an array of size n wherein elements keep on increasing
monotically upto a certain location after which they keep on
decreasing monotically, then again keep on increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra
memory)
--
Regards,
Navneet
--
Radix sort is one of the solution.
because this Question is in the section Radix sort in CLRS. :)
On Tue, Aug 2, 2011 at 11:10 AM, Ravinder Kumar ravinde...@gmail.comwrote:
I have little thought on this :
divide the whole array by n and store their remainder also in an array
now number in
Can you please elaborate ??
On 2 August 2011 12:38, sunny agrawal sunny816.i...@gmail.com wrote:
Radix sort is one of the solution.
because this Question is in the section Radix sort in CLRS. :)
On Tue, Aug 2, 2011 at 11:10 AM, Ravinder Kumar ravinde...@gmail.comwrote:
I have little
I think that we can do it by first passing through an array once and convert
all the interger to the base N in O(N). Since all elements are in the range
1 to N^2 they can have atmost 3 digits.Now apply radix sort which will be O(
dn ) where d=3 in this case .= O(n) when done convert them back to
It may create duplicate numbers while converting into base N. How
do recognize them while converting into base(N^2)??
On 2 August 2011 17:20, Harshit Kapoor kapoor...@gmail.com wrote:
I think that we can do it by first passing through an array once and
convert all the interger to the base N in
we can use radix sort
On Tue, Aug 2, 2011 at 7:41 PM, payel roy smithpa...@gmail.com wrote:
It may create duplicate numbers while converting into base N. How
do recognize them while converting into base(N^2)??
On 2 August 2011 17:20, Harshit Kapoor kapoor...@gmail.com wrote:
I think that
int a[N^2]={0},i,j;
for(i=0;iN^2;i++)
{
cinj;
a[j]++;
}
for(i=0;iN^2;i++)
{
if(a[i]!=0)
{
while(a[i]--)
{
couti\t;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To
How is it possible??
On Tue, Aug 2, 2011 at 7:41 PM, payel roy smithpa...@gmail.com wrote:
It may create duplicate numbers while converting into base N. How
do recognize them while converting into base(N^2)??
On 2 August 2011 17:20, Harshit Kapoor kapoor...@gmail.com wrote:
I think that
You have an integer array of length N, containing values in the range
1,2,3…N^2. Sort the array in O(N) time
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from
How is it possible.If the range is 1 to N then we could use counting
sort.But how can we do it in linear time .Any kind of sorting algorithm
exists for this case??
On 1 August 2011 21:03, payel saha smithpa...@gmail.com wrote:
You have an integer array of length N, containing values in the
@raja : The range is 1-N^2 and not 1-N. Had it been 1-N , we could have
easily sorted the array in O(N) time using bit map.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To
@ankit:
Thats what i am saying as well .If The range is till N^2. how can we sort it
in linear time??
If you know the answer please post it.
On 1 August 2011 21:47, ankit sambyal ankitsamb...@gmail.com wrote:
@raja : The range is 1-N^2 and not 1-N. Had it been 1-N , we could have
easily sorted
I have little thought on this :
divide the whole array by n and store their remainder also in an array
now number in original array are in range 1-n
sort the array and when two number with same break the tie using remainder
array
recreate the array using remainder array .
--
*With Regards :*
Check this
*int isconsecutive(int a[], int n) {*
*if (n 1) {*
*return 0;*
*}*
*int max = a[0], min = a[0];*
*int i = 0;*
*
*
*int *hash = (int*) calloc(n, sizeof (int));*
*
*
*//find min and max from the array*
*for (i = 1; i n; i++) {*
*if (a[i]
How about doing like this ?.
Without loss of generality, I can assume that numbers starts from 1
(if not, if it starts from ZERO, add by 1 to all the numbers,
if it is negative, find the min value, assume it is X, add by (-X)+1))
Now assume numbers are M, compute the product of the numbers and
@ Sathaiah Dontula
i think this won't work
Because product of m consecutive integers is divisible by m! but reverse is
not true ie.
if product of m integers is divisible by m! then they are consecutive ??
correct me if i am wrong!!
On Wed, Jul 6, 2011 at 12:55 PM, Sathaiah Dontula
Given an array, A, find if all elements in the sorted version of A are
consecutive in less than O(nlogn).
eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive --
true
A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive -
false
--
You received this message because you
you have an array of size n where first n/2 is sorted and the sencond half
is sorted . You need to sort the entire array inplace
Its second modification version is where first part is sorted and other is
NOT sorted . You need to make entire sorted .
--
Regards,*
Aanchal Goyal*.
--
You received
its like inplace mergesort
On Tue, Jun 21, 2011 at 10:13 PM, aanchal goyal goyal.aanch...@gmail.comwrote:
you have an array of size n where first n/2 is sorted and the sencond half
is sorted . You need to sort the entire array inplace
Its second modification version is where first part is
i think we can use insertion sort
On Tue, Jun 21, 2011 at 10:56 PM, Anika Jain anika.jai...@gmail.com wrote:
its like inplace mergesort
On Tue, Jun 21, 2011 at 10:13 PM, aanchal goyal
goyal.aanch...@gmail.comwrote:
you have an array of size n where first n/2 is sorted and the sencond
@anika: yar merge sort vl tk nlogn timeinstead u cn do dt maintain two
ptrs one at the beginning and one intitially pointing to middle of the
array...
thn compare the elemnts pointed by them and swap the values if necesary nd
incremnt d ptr as u go on...
ths vl tk (n/2)+(n/2)-1 =O(n) time
ya...we can do it in O(n) n time!!!
nice question!
On Tue, Jun 21, 2011 at 11:01 PM, himanshu kansal
himanshukansal...@gmail.com wrote:
@anika: yar merge sort vl tk nlogn timeinstead u cn do dt maintain two
ptrs one at the beginning and one intitially pointing to middle of the
array...
Given n elements, sort the elements. Here, only one operation is
permitted decreaseValue..
Note that you cannot swap the values.. output should be a sorted
list..
if input is 4 5 2 1 3
output is 3 3 3.. There can be many answers.. Give the optimum
solution with minimum cost. where as cost is the
pls send more example
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
Given an array with two subparts sorted. How will you make a final sorted
array.
i/p: 1, 5, 7, 9, 11, 23, 2, 3, 8, 9, 21
o/p:
1, 2, 3, 5, 7, 8, 9, 9, 11, 21, 23
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
--
You received this message because you are subscribed to the Google
use merge sort
On Tue, Apr 12, 2011 at 3:07 PM, Akash Agrawal akash.agrawa...@gmail.comwrote:
Given an array with two subparts sorted. How will you make a final sorted
array.
i/p: 1, 5, 7, 9, 11, 23, 2, 3, 8, 9, 21
o/p:
1, 2, 3, 5, 7, 8, 9, 9, 11, 21, 23
Regards,
Akash Agrawal
This is obvious solution what if u have contant space?
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Tue, Apr 12, 2011 at 3:48 PM, rajul jain rajuljain...@gmail.com wrote:
use merge sort
On Tue, Apr 12, 2011 at 3:07 PM, Akash Agrawal
akash.agrawa...@gmail.comwrote:
Given
Maintain two pointers, and swap elements...
On Tue, Apr 12, 2011 at 4:42 PM, Akash Agrawal akash.agrawa...@gmail.comwrote:
This is obvious solution what if u have contant space?
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Tue, Apr 12, 2011 at 3:48 PM, rajul jain
The LL is in alternating ascending and descendin orders. Sort the list
efficiently
egs: 1-2-3-12-11-2-10-6-NULL
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe
I think in this case bubble sort with early exit will be efficient
On Wed, Mar 2, 2011 at 8:16 PM, snehal jain learner@gmail.com wrote:
The LL is in alternating ascending and descendin orders. Sort the list
efficiently
egs: 1-2-3-12-11-2-10-6-NULL
--
You received this message because
find two consecutive sequences(can be two increasing2I, 1i1d,1d1i,2D), merge
them and then merge every next sequence with this merged sequence
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Mar 2, 2011 at 8:33 PM, Shreyas VA
Smaple Data :
input : abcdacdc
Output : cadb
If the count is same for characters. maintain the original order of
the characters from input string.
Please do let me know for any clarification.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
we can use the count sort array in this to count the frequencies of
character (array size would be fixed 26)
and sort that counting array by again count sort or quick sort in decrsaing
order and than print the valur in ascci format '97+i'.
On Thu, Jan 13, 2011 at 11:53 AM, Davin
we can also the concept of HASHING to count the frequency of each character
.
On Thu, Jan 13, 2011 at 11:53 AM, Davin dkthar...@googlemail.com wrote:
Smaple Data :
input : abcdacdc
Output : cadb
If the count is same for characters. maintain the original order of
the characters from
Given an array having 16000 unique integers, each lying within the
range 12, how do u sort it. U can load only 1000 numbers at a
time in memory
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
See External Sort at Wiki.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
Given an array of size n wherein elements keep on increasing
monotically upto a certain location
after which they keep on decreasing monotically, then again keep on
increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra
memory).
--
You received this
First determine the point from which array becomes decreasing. Then In-place
merge sort.
On 14 December 2010 23:22, divya sweetdivya@gmail.com wrote:
Given an array of size n wherein elements keep on increasing
monotically upto a certain location
after which they keep on decreasing
you are given n integers in the range 0 to n3-1 ((n to the power 3) - 1) .
how can u sort the numbers in O(n)?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from
use radix sort
On Sat, Oct 2, 2010 at 10:32 PM, Harshal ..Bet oN iT!! hc4...@gmail.comwrote:
you are given n integers in the range 0 to n3-1 ((n to the power 3) - 1) .
how can u sort the numbers in O(n)?
--
You received this message because you are subscribed to the Google Groups
but the range (k) is cubic in n, if we use counting sort also in radix sort,
k wont be of the order n, so how can solution be in linear time?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
There is a theorem which states that a sorting algorithm must take o(nlogn) to
sort a list of any possible values. however there are certain sorts like
insertion sort where o(n) in the best case ie when a list is sorted.
On 02-Oct-2010, at 10:32 PM, Harshal ..Bet oN iT!! hc4...@gmail.com
You are given a doubly link list and out of some nodes of this
doubly linked list, some other doubly link list emerge and from some
of these emerging doubly linked list, more doubly link list emerge.
You have to write a quick algo that merges all these doubly linked
list into a singly linked list
if we have 1 2 5 7 3 4 6
can you explain how to do in place merge... the elements are in an array
?
On Sun, Jul 11, 2010 at 10:29 AM, jalaj jaiswal
jalaj.jaiswa...@gmail.comwrote:
its easy
suppose the array is 12345 4321 2345 4321
it increases then dcreases then increases and
Given an array of size n wherein elements keep on increasing
monotically upto a certain location
after which they keep on decreasing monotically, then again keep on
increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra
memory).
--
You received this
thr is no search option there ..
if u can gimme the link that will be good ..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
its easy
suppose the array is 12345 4321 2345 4321
it increases then dcreases then increases and decreases again
first of all in a single scan find the location of decreasing sub-arrays
here it is 5 to 8 and 13-16
and reverse the decreasing array.
so the array becomes
12345 1234 2345 1234
now
for sort you have to traverse array atleast once ..and after it some sorting
procedure will come.
On Fri, Jul 9, 2010 at 12:55 PM, Devendra Pratap Singh
dpsingh.ii...@gmail.com wrote:
plz write a code to
Sort n integer in the range 1 to n^2 in O(n)
--
You received this message because
take auxillary array O(n^2) space .. will it do.. or are there some more
constraints ??
On Sat, Jul 10, 2010 at 1:25 AM, Devendra Pratap Singh
dpsingh.ii...@gmail.com wrote:
plz write a code to
Sort n integer in the range 1 to n^2 in O(n)
--
You received this message because you are
plz write a code to
Sort n integer in the range 1 to n^2 in O(n)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
left child=2*i+1,right child=2*i+2,parent=(i-1)2
#includeiostream
using namespace std;
void sort(int );
int a[]={100,50,150,25,75,125,200};
int main(){
sort(0);
system(pause);
return 0;
}
void sort(int i){
int n=7;
if(i=0i=n-1){
sort(2*i+1);
The most useful data structure would be BST.
Each node will have data value and its count. count indicates the number of
times it is repeated in a sequence. Below is the algo to creat a binary
search tree.
insert_node(int data, node root)
{
if(root == NULL)
{
root = malloc();
you will have to call insert functuon for every integer
for 1 to n
insert(int n , node *root)
wouldn't that be n*logn
correct me if i'm wrong..!!!
On Fri, Jun 25, 2010 at 10:37 PM, Anand anandut2...@gmail.com wrote:
The most useful data structure would be BST.
Each node will have
if there is no space constraint we can use counting sort .. with O(logm)
space and time complexity will be O(n)
On Fri, Jun 25, 2010 at 5:51 PM, sharad kumar sharad20073...@gmail.comwrote:
You are given an unordered sequence of n integers with many duplications,
such that the number of
Hi All,
Suppose I have a big file (~100M) containing integer data. I want to sort
this file. The problem is I don't want to load the complete file data into
main memory in one shot. I mean I can read the file in batches and sort the
batch and save it in another file but cannot store the entire
If the numbers are unique you could use a bitmap-sort this way you could
easily read just parts of the file at a time.
If they aren't unique it gets a bit trickier.
/L
dinesh bansal wrote:
Hi All,
Suppose I have a big file (~100M) containing integer data. I want to sort
this file. The
On Mon, Dec 21, 2009 at 6:47 PM, Linus Probert linus.prob...@gmail.comwrote:
If the numbers are unique you could use a bitmap-sort this way you could
easily read just parts of the file at a time.
If they aren't unique it gets a bit trickier.
/L
dinesh bansal wrote:
Hi All,
Suppose I
could you describe what kind of data exists . i mean are duplicates allowed?
On Mon, Dec 21, 2009 at 6:47 PM, Linus Probert linus.prob...@gmail.comwrote:
If the numbers are unique you could use a bitmap-sort this way you could
easily read just parts of the file at a time.
If they aren't
A merge sort would be helpful i guess... it can also happen in parallel and
IIRC databases use them internally.
Please correct me if im wrong.
Regards,
Abhilash
On Mon, Dec 21, 2009 at 7:06 PM, dinesh bansal bansal...@gmail.com wrote:
On Mon, Dec 21, 2009 at 6:47 PM, Linus Probert
This wikipedia article on external sorting may help :
http://en.wikipedia.org/wiki/External_sorting
On Mon, Dec 21, 2009 at 8:18 PM, Abhilash L L llabhil...@gmail.com wrote:
A merge sort would be helpful i guess... it can also happen in parallel
and IIRC databases use them internally.
The LL is in alternating ascending and descendin orders. Sort the list
efficiently
egs: 1-2-3-12-11-2-10-6-NULL
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe
give algorithm for the following -:
1. sort a 2-d array
2. sort a 2-d array in snake order
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
75 matches
Mail list logo
