CareerCup

Space Complexity:

QuickSort: O(logn)~O(n)
Bubble: O(1)
Insertion: O(1)
Merge: O(n)
BS: O(n)

They have asked memory efficient not time efficient
It has to be bubble and insertion sort...memory usage O(1)

Why quick sort takes O(logn). Quick sort is in-place sorting algorithm. it takes constant amount of memory other than the input array to sort the array.

Bubble or insertion, yes.
But on more comlex side, "in place" merge sort is also the one with no addition memory overhead. Pick yours!

space complexity:
Quick = O(1)
Bubble = O(1)
Insertion = O(1)
Merge = O(n)

Time complexities:
Quick sort: Best O(n), Average: O(nlogn), Worst case: O(n^2)
Insertion sort: Best O(n), Worst Case: O(n^2)
Bubble sort: O(n^2) (best/worst)
Merge Sort: O(nlogn)(best/worst)

So quick sort is the best algorithms, considering its time and space complexity.

space complexity of Quick sort on array is O(1).

Because at each recursive call one element position will be fixed (with only O(1) extra memory for swapping elements). there will be 2 recursive calls one on the left part and one on the right part. We can use the same original array for the recursive calls also.

So How can it take O(logn) Memory. Can you explain.

The merge-sort has an O(nlogn) comparison-based sorting algorithm. It requires very little memory, and the memory required does not depend on the number of data elements. Hence, merge-sort is the best in terms of efficient memory usages.

import java.io.*;
import java.util.*;

class replace
{
public static void main(String [] args)
{
String totest[];
int i;
String test="She is a Hot girl";
String newString="";
StringTokenizer st= new StringTokenizer(test);

while(st.hasMoreTokens())
{
String temp=st.nextToken();
if( temp.compareTo("a")==0)
newString=newString+"the ";
else
newString= newString+ temp + " ";

}
System.out.println(newString);

}
}

import java.io.*;
import java.util.*;

class replace
{
public static void main(String [] args)
{
String totest[];
int i;
String test="She is a Hot girl";
String newString="";
StringTokenizer st= new StringTokenizer(test);

while(st.hasMoreTokens())
{
String temp=st.nextToken();
if( temp.compareTo("a")==0)
newString=newString+"the ";
else
newString= newString+ temp + " ";

}
System.out.println(newString);

}
}

Many of you are forgetting the memory used when a stack frame is stored during a recursive call.

Take a look at hxxp://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

it depends on the context.... Merge is the best.... what is this binary search sorting algorithm??
Never heard of it..

put each element in a binary tree then do inorder traversal

Merge is definitely not the best for memory efficient.
Quick = O(logn)
Bubble = O(1)
Insertion = O(1)
Merge = O(n)

for Binary search, if counting the result storage, O(n)

So bubble and insertion are best.

I think quick sort is the best of the sorting algorithms, although it may be difficult to code and implement , but quick sort with an efficiency of O(n) is the best among the sorting algorithms...

I think bubble, insertion sort and quick sort are most **memory** efficient. And the storage complexity is not O(1). It's O(n). How can it be O(1)? Surely they are in place algorithms. But do you think a 5 element input array will occupy the same storage space as 50 element input array? If no then how the storage space is O(1). It depends on the input size. merge sort takes more space in addition to O(n) of input size.