Hint 1: If taken the assumption that you have ~6GB RAM (out of this 3.7GB
is for the input itself) you do not need any external sorting to do this.
Hint 2: 1,000,000,000 (2 30)
Hint 3: Read this http://en.wikipedia.org/wiki/Bit_array#Sorting up
On Thu, Jun 13, 2013 at 2:06 AM, MAC
How would one sort 1 billion integers. .. I gave external sorting answer
but he waned more .. What should i say ?
Asked me to tell him how would the problem change if total of 4 threads
are given. How would you solve ?
thanks
--mac
--
You received this message because you are subscribed
//To sort an array of integers by not moving the element itself ..we
can only use array of pointers...to adjust the pointers
I have used bubble sortbut it only runs for the first pass when i
= 0 ..but not for further values of i
void sort(int A[])
{
int i ;
//int **a = ptr[0];
this will be so because when in your case j=MAX-1, then ptr[j+1] will try
to access ptr[MAX] which is not existing..so segmentation fault occurs
On Fri, Jun 22, 2012 at 3:35 PM, vindhya chhabra
vindhyachha...@gmail.comwrote:
@deepika-ur program was running only for 1 iteration because of ur
+1 mithun kumar !!
using bit array or bitmap index gives the best solution ( O(n) )
the only limitation is we should know the maximum limit of the number,
which is provided in this problem :D
Thanks Regards
Saurabh Yadav
--
You received this message because you are subscribed to the Google
using bit array we can sort elements in O(1)
-mithun
On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.comwrote:
How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
After giving some thought,I think even radix sort may not be sufficient.
Complexity of radix sort is O(k*n) where k is the number of buckets
required to sort the given range.
The number of buckets is proportional to the number of bits required to
represent the *maximum number in the given
Hi all,
I am new to this group.
My last post was deleted i do not know the reason behind it.
I will explain my logic here:-
as the range is 1 to n^2 we have a input array like input[n^2].
We can take a auxillary array of size n^2 like aux[n^2].
Scan the input array.
For each input input[i]
Consider the case
n=6
array elements :-
{36 36 36 36 36 36}
How many iterations your code makes?
Consider another case
n=100
array={1e12,1e12 ..repeated 10^6 times}
How many iterations your code make?
Are the iterations still proportional to n that is the number of elements
in the array?
How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PGgMdaIbGIsJ.
To post to this group, send
The range 1 to n^2 is already sorted
On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.com wrote:
How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view
@cegprakash They are n numbers lying in the range 1 to n^2.Not necessarily
sorted.
eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the problem)
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Sat, May 5, 2012 at 5:17 AM, Prakash D
Hi,
Could any point out me any algorithm and program if we need to sort to
large data
like 10 ^ 80 with memory constraint. Suppose you have minimum memory like 4
MB.
I am not sure that this algo discussed or not but i was not able to find in
this group.
Thanks
Abhishek
--
You received this
External sort.
On Sat, Jan 14, 2012 at 11:39 PM, Abhishek Goswami
zeal.gosw...@gmail.comwrote:
Hi,
Could any point out me any algorithm and program if we need to sort to
large data
like 10 ^ 80 with memory constraint. Suppose you have minimum memory like
4 MB.
I am not sure that this
if you have 4 mb ram and no external m/m then where is input is coming
from???
On Sat, Jan 14, 2012 at 11:47 PM, Abhishek Goswami
zeal.gosw...@gmail.comwrote:
But in external sort you use external memory but in case if you have 4 MB
RAM and do not have external
memory device. than how will
External Memory Sort. The Algorithm is based on Merge Sort.
Divide data into chunks of the size of your RAM. Let's say you have k
chunks. Such that k x size of RAM = size of your total data.
Sort the chunks independently.
Perform a k-way merge of these chunks.
On Sat, Jan 14, 2012
Could any
Question: If given string with sorted order with some disorder in
between for example
abcfedghi you need to make it as abcdefghi with no extra space
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
What is the efficient way to sort a M*N matrix.
eg: Given a 3*4 matrix
2 6 7 12
11 8 5 1
9 3 4 10
The ouput should be
1 2 3 4
5 6 7 8
9 10 11 12
Matrix may contain duplicates..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
is there any algo better than bruteforce for this :
O(m*n*log(m*n))
On Sat, Sep 24, 2011 at 7:56 PM, teja bala pawanjalsa.t...@gmail.comwrote:
What is the efficient way to sort a M*N matrix.
eg: Given a 3*4 matrix
2 6 7 12
11 8 5 1
9 3 4 10
The ouput should be
1 2 3 4
5 6 7 8
9 10
Is the range of numbers provided ?
On 24 September 2011 10:26, teja bala pawanjalsa.t...@gmail.com wrote:
What is the efficient way to sort a M*N matrix.
eg: Given a 3*4 matrix
2 6 7 12
11 8 5 1
9 3 4 10
The ouput should be
1 2 3 4
5 6 7 8
9 10 11 12
Matrix may contain
I think it can be proved by contradiction that there does not exist a better
sorting algorithm than O(mnlogmn)
because if there is one then that means we can sort an array better than
O(nlgn) by assuming an array as 2D array of k rows and Ceiling(n/k) columns.
and if the elements belongs to some
@praveen raj: yes bubble sort takes O(N) in best case,
but selection sort it depends the selection algo(does the selection
starts from the first(then itsO(n)) or last(then its O(N^2))
Thank you,
Sid.
On Fri, Sep 9, 2011 at 11:20 AM, praveen raj praveen0...@gmail.com wrote:
for checking whther
very easy qus...which is the best sorting tech. n why?
--
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
which is best sorting tec. n why???
--
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
Merge sort
Quicksort--number of comparisons and exchanges lesser than heapsort...if
worst case not occurs...
--
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
if list is sorted nd when list is unsorted.
and which one quick sort or merge sort.
--
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
It depends on the use cases.
If you have less elements of order of( say 100) then even insertion sort can
be a better choice. It's in-place sorting algo and can
perform sorting as it receives the elements like a stream.
If you have large number of elements and all the elements can't be
Randomized quick sort .. even the worst case in this algo is O(n^2) also,
this is best sorting algo ..
It is showed that nearly 20-25% of time O.S spends its time in sorting.In
unix based systems , they are using this algo only ..
A random choice will only choose from middle parts half the time.
for checking whther given array sorted or not... bubble sort or insertion
sort... takes O(n).. time...
With regards,
Praveen Raj
DCE-IT 3rd yr
735993
praveen0...@gmail.com
On Thu, Sep 8, 2011 at 11:32 PM, aayush jain ajain...@gmail.com wrote:
thanx @piyush
--
You received this
Given a file containing roughly 300 million social security numbers(9-
digit numbers) find a 9-digit number that is not in the file.
You have unlimited drive space but only2megabytes of RAM at your
disposal.
--
You received this message because you are subscribed to the Google Groups
Algorithm
Hi every one:-
I encounter a problem in which we have to sort.
You come across a collection of 20 stone statues in a line. You want to
sort them by height, with the shortest statue on the left. The statues are
very heavy and you want to move them the least possible distance.
Design a sorting
*The statues are
very heavy and you want to move them the least possible distance.*
On Sun, Aug 21, 2011 at 12:31 AM, priya ramesh
love.for.programm...@gmail.com wrote:
in quick sort the pivot is positioned to it's proper position. (no
intermediate swaps)
--
You received this message
index the stones 1 to 10:
suppose the list is {3,1,4,5};
so the original list looks like
1-3
2-1
3-4
4-5
Now sort the indexes based on the value of height..
2-1
1-3
3-4
4-5
Now reorder the indexes from 1 to 4.Can be implemented elegantly with C++
overloading quite elegantly.,
On Sun, Aug 21,
Hi,
How can we sort one unsorted int array with O(n).
Unsorted : {4,2,6,1,5,5,1,2,45,444,44,45,4,1}
Sorted : {1,1,1,2,2,4,4,5,5,6,44,45,45,444}
Is there any sorting method which gives us O(n) time complexity???
Please tell the algo if anybody knows it.
--
AMAN AGARWAL
Success is not final,
Counting sort, radix sort, .
On Wed, Aug 3, 2011 at 10:58 AM, AMAN AGARWAL mnnit.a...@gmail.com wrote:
Hi,
How can we sort one unsorted int array with O(n).
Unsorted : {4,2,6,1,5,5,1,2,45,444,44,45,4,1}
Sorted : {1,1,1,2,2,4,4,5,5,6,44,45,45,444}
Is there any sorting method which
counting sort
http://en.wikipedia.org/wiki/Counting_sort
Thanks
NItin
On Wed, Aug 3, 2011 at 10:58 AM, AMAN AGARWAL mnnit.a...@gmail.com wrote:
Hi,
How can we sort one unsorted int array with O(n).
Unsorted : {4,2,6,1,5,5,1,2,45,444,44,45,4,1}
Sorted : {1,1,1,2,2,4,4,5,5,6,44,45,45,444}
Given a valid range sort keys, the linked list can be sorted in O9n) time
using counting sort which takes O(n+k) comparisons to sort the list of K
elements .
On Sat, Jul 23, 2011 at 9:58 AM, Ankur Khurana ankur.kkhur...@gmail.comwrote:
10^9--10^9 - 8- 7- NULL . It wont help in this case...
How to sort Linked lists in O(n) time ??
Give the algorithm or the explanation or clue to tackle the problem
--
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
use counting sort..
On Sat, Jul 23, 2011 at 1:22 AM, rShetty rajeevr...@gmail.com wrote:
How to sort Linked lists in O(n) time ??
Give the algorithm or the explanation or clue to tackle the problem
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
For linklist? How
On Sat, Jul 23, 2011 at 1:23 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
use counting sort..
On Sat, Jul 23, 2011 at 1:22 AM, rShetty rajeevr...@gmail.com wrote:
How to sort Linked lists in O(n) time ??
Give the algorithm or the explanation or clue to tackle the
actually its a work around...first traverse the list and store it in an
array..
sort the array in o(n)
then replace the content of the linked list using the values in the array
On Sat, Jul 23, 2011 at 1:24 AM, Pankaj jatka.oppimi...@gmail.com wrote:
For linklist? How
On Sat, Jul 23, 2011 at
Cannot be done in O(N) if elements of list can take any value because then
counting sort wont help
On Sat, Jul 23, 2011 at 1:24 AM, Pankaj jatka.oppimi...@gmail.com wrote:
For linklist? How
On Sat, Jul 23, 2011 at 1:23 AM, Kamakshii Aggarwal kamakshi...@gmail.com
wrote:
use counting
n logn merge sort.count sort only when range is known.
On Sat, Jul 23, 2011 at 1:35 AM, sunny agrawal sunny816.i...@gmail.comwrote:
Cannot be done in O(N) if elements of list can take any value because then
counting sort wont help
On Sat, Jul 23, 2011 at 1:24 AM, Pankaj
counting sort ll help to some extent... find the min and max element O(n)
now u just need an array of size max-min to store the values then
just traverse the list and while updating u do value+min... still it is not
suitable if the magnitude is high.
On Sat, Jul 23, 2011 at 9:45 AM,
10^9--10^9 - 8- 7- NULL . It wont help in this case...
On Sat, Jul 23, 2011 at 9:55 AM, keyan karthi keyankarthi1...@gmail.comwrote:
counting sort ll help to some extent... find the min and max element O(n)
now u just need an array of size max-min to store the values then
just
Given a sequence of numbers in the range of 1-N^2, what is the most
efficient way to sort the numbers (better than NlgN)..
Can counting sort be used here? Is an O(N) solution possible..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
Yes ! Count Sort !!
On Sun, Jun 26, 2011 at 1:44 PM, ross jagadish1...@gmail.com wrote:
Given a sequence of numbers in the range of 1-N^2, what is the most
efficient way to sort the numbers (better than NlgN)..
Can counting sort be used here? Is an O(N) solution possible..
--
You received
Everyone here's mentioned O(n^2) Pancake sorting. Here's a solution in O(n
log n)
A run is defined as a sequence of consecutive values in the array.
1. Go through the array and reverse descending runs - O(n) as reverse(i, j)
is supplied. Now you have an array with many runs in ascending order.
On a closer look, you can clearly see that as per my approach to the
problem, I have defined something similar to the swap(i, j) operator.
Given this operator, you can implement any O(n log n) sort that you desire.
swap(i, j) = reverse(i + 1, j), reverse(i, i + 1), reverse(i+1, j)
Have fun
Oops, there's a bug in my analysis! the sort complexity is even better at
O(N) :)
If you're doing K merges of subarrays of size O( N / K ) (which is the
worst case for this algo due to the merge cost of O(min{N, M}) ) using the
reverse operation you've supplied, the result is an O(N) sort
Really really sorry for polluting this thread, but there's small issue in
that analysis:
The cost O(N) is in terms of reverse operations executed (that is swaps) and
not in terms of the number of comparisons. The number of comparisons remain
O(N log N) but the maximum number of swaps is O(N)
There is an array in an external system (i.e. u cannot access the
array elements directly).
The system exposes 3 functions of O(1) - (assume) :
length() - returns the length of the array.
get(i) - returns the element at index i.
reverse(i,j) - reverses the elements in the array from index i to
@rossI have a doubt regarding reverse function...
does it rotate the array or reverse it??
for say it is 12345
reverse(0,4) make it 51234 or 54321???
On 6/12/11, ross jagadish1...@gmail.com wrote:
There is an array in an external system (i.e. u cannot access the
array elements directly).
How to output the number in a sorted way in which The sorting is done
based on string sorting and not on numerical
(Eg:121 comes before 2 because the Most Significant Digit is 1 in 121
which is less than 2)
disp(int low, int high);
disp(5, 1113);
Required Output is:
10
100
1000
11
12
.
.
19
101
I am not sure if this what you are looking for.
Assuming that the arrays are sorted in ascending order.
Choose one of the 2 arrays as a Reference Array.
for each element element in reference array, do a binary search to find all
elements that are less than the current element in reference and
Suppose we'd like to implement a sorting variant where every element
is compared only a small number of times.
a) devise a divide and conquer algorithm to merge 2 sorted arrays of
length n , which guarantees that every element is included in at most
O(log n ) comparisons.
b) using this modified
Let A[1..n] be an array such that the first (n − √n) elements are
already sorted
(though we know nothing about the remaining elements). Give an
algorithm that
sorts A in substantially better than (n log n) steps.
This question is from chapter 4 : Algorithm Design Manual by S Skiena
--
You
Can't we use bubble sort on remaining elements?
On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote:
Let A[1..n] be an array such that the first (n − √n) elements are
already sorted
(though we know nothing about the remaining elements). Give an
algorithm that
sorts A in
merge sort or quick sort or insert last root(n) element . This will take max
n time . now merge the last root(n) element with the starting element .this
will take n time . so final time complexity is nnlog(n)
Rahul
--
You received this message because you are subscribed to the Google
ooops wrong approach... :(
On Thu, Aug 26, 2010 at 10:44 PM, Naveen Kumar
naveenkumarve...@gmail.comwrote:
Can't we use bubble sort on remaining elements?
On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote:
Let A[1..n] be an array such that the first (n − √n) elements are
Hi Sourav,
I will first inplace sort the last √n elements in O(n) and then merge the
two sorted arrays in O(n).
The only problem: O(n) merging will not be inplace.
On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote:
Let A[1..n] be an array such that the first (n − √n) elements
Can anyone suggest a sorting algorithm that sorts in linear time without
using extra space.
--
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
Count sort..
From: Subhranil Banerjee riku...@gmail.com
To: algogeeks@googlegroups.com
Sent: Mon, August 23, 2010 3:36:12 AM
Subject: [algogeeks] Sorting algorithm
Can anyone suggest a sorting algorithm that sorts in linear time without using
extra space
, 2010 3:36:12 AM
*Subject:* [algogeeks] Sorting algorithm
Can anyone suggest a sorting algorithm that sorts in linear time without
using extra space.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge
:* [algogeeks] Sorting algorithm
Can anyone suggest a sorting algorithm that sorts in linear time without
using extra space.
--
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
radix sort...
On Mon, Aug 2, 2010 at 10:22 AM, Apoorve Mohan apoorvemo...@gmail.comwrote:
Counting Sort.
On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote:
There are N numbers in an array and each number is in the range [0,
n*n -1]. Is there a way to sort the
Counting Sort.
On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote:
There are N numbers in an array and each number is in the range [0,
n*n -1]. Is there a way to sort the elements in O(n)?
Thanks,
Praveen
--
You received this message because you are subscribed to
i dont think counting sort can be applied since its time cpmplexity is
O(n+k) where numbers are in the range 1...k and here k=O(n^2). so the
overall complexity will again go to O(n^2) :(
On Mon, Aug 2, 2010 at 10:22 AM, Apoorve Mohan apoorvemo...@gmail.comwrote:
Counting Sort.
On Mon,
There are N numbers in an array and each number is in the range [0,
n*n -1]. Is there a way to sort the elements in O(n)?
Thanks,
Praveen
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Which is a better measure for sorting
1)no of elements on their rank position
2)longest increasing subsequence
--
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
Here is my approach;
Sort the two arrays and reverse one of the array list and append it to make
a bitonic sequence and then apply bitonic merge sort to get a final sorted
list.
Here is an example for it.
http://codepad.org/8Uv7AOKo
thanks,
Anand
On Sun, Jun 13, 2010 at 8:13 PM, sharad kumar
@ vadivel,yes i mean the former has got unused space in which the latter
can occupy
--
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
@ sharad... DO u mean the former has got unused space in which the latter
can occupy
On Sun, Jun 13, 2010 at 11:02 AM, harit agarwal agarwalha...@gmail.comwrote:
sort both arrays separetely and then perform merge operation ..it is
O(mlogm+nlog)...
--
You received this message because
an algorithm to sort two unsorted arrays, the former enough lengthy to
accomodate all the elements in the latter, in place
--
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
is it like this sort 2 unsorted arrays of size m and n such mn such that
array of size m can hold all n element apart from m element.an inplace
solution is required???
if it is so then copy the elements from n size array elements to m size
array and then perform quick sort ..
On Sat, Jun 12,
Consider
Array C = {a1, b1, a2, b2, a3, b3, ... }
such that
a1a2a3
b1b2b3
Input: *array C *
Output: *Sorted array C* with complexity O(n * log n)
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Hi
are there any sorting algorithms which run in O(nlogn) time apart from
heap sort and merge sort?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Dean of Computer Science department wants to keep the motivation
levels of students of data structure course high by giving incentives.
He has suggested that after the second minor the top lon students be
distributed samosas and the next sqrt(n) students be given gulab
jamuns. However, he has
hi guys,
can anyone mail me the sorting algorithms and other greedy algorithms in animated format...i want it vey badly so as to study for the univ examination...pls mail me...
Sriram.N
--~--~-~--~~~---~--~~
You received this message because you are subscribed to
Sorting the marked nodes infibonachi heap modulo Q
where q is integer and positive number.
Hello i need an efficiant algorithm to sort the marked nodes in
infibonachi heap
modulo Q.
I remind that the marked nodes are nodes that lost a son (one or more)
, since they
become (the marked node)
80 matches
Mail list logo
