Question 39: Quicksort vs Linear Search

Kleid-0 · 04-17-2005, 07:38 AM

Quote:

Would you rather wait for the results of a quicksort, a linear search, or a bubble sort on a 200000 element array?

Quicksort
Linear Search
Bubble Sort

The answer is linear search but I believe this question is hard to answer because I don't know if the results are coming from a sorting algorithm or a search. If we're talking about a sort the answer would be quicksort, and if we're searching it would obviously be linear search, am I right?

Perspective · 04-17-2005, 10:47 AM

A linear search is O(n). Quick sort is O(n log(n)) [in its best case]. Bubble sort is O(n^2).

Which is the shortest of those three? O(n)

Whether your searching or sorting is irrelevant. The point of the question is to see which algorithm runs in the fastest time.

adrianxw · 04-17-2005, 11:03 AM

<pedant>Without a statement that says the dataset is not in order, the question is meaningless.</pedant>

04-17-2005, 10:47 AM	#2
Perspective Crazy Fool Join Date: Jan 2003 Location: Canada Posts: 2,596	A linear search is O(n). Quick sort is O(n log(n)) [in its best case]. Bubble sort is O(n^2). Which is the shortest of those three? O(n) Whether your searching or sorting is irrelevant. The point of the question is to see which algorithm runs in the fastest time. __________________ jeff.bagu.org - Terrain rendering and other random stuff
Perspective is offline

04-17-2005, 11:03 AM	#3
adrianxw It's full of stars Join Date: Aug 2001 Posts: 4,833	<pedant>Without a statement that says the dataset is not in order, the question is meaningless.</pedant> __________________ Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.
adrianxw is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Contest Results - May 27, 2002	ygfperson	A Brief History of Cprogramming.com	18	06-18-2002 01:27 PM
Search Engines :: Winsock	kuphryn	Windows Programming	3	06-18-2002 12:31 PM
Again Character Count, Word Count and String Search	client	C Programming	2	05-09-2002 11:40 AM
Linear search and 2d arrays?	sven	C Programming	0	02-08-2002 05:26 AM
Linear Search: the recursive way.	Nutshell	C Programming	7	01-15-2002 03:15 AM