The topic comes from a question:
Would you rather wait for the results of a quicksort, a linear search,
or a bubble sort on a 200000 element array?
1Quicksort
2Linear Search
3Bubble Sort
The answer is 2Linear Search
Could someone explain why Linear Search, not the other two options?
Or I misunderstood the original question?
Thanks you guys! 26 2579
On 4 May, 23:27, mike-yue <needpass...@gm ail.comwrote:
The topic comes from a question:
Would you rather wait for the results of a quicksort, a linear search,
or a bubble sort on a 200000 element array?
1Quicksort
2Linear Search
3Bubble Sort
The answer is 2Linear Search
Could someone explain why Linear Search, not the other two options?
Well, it's a poor question: asking what /you/ would prefer to do; but
presuming you want to wait as little time as possible wouldn't option
2 finish soonest? The fact that sorting and searching accomplish
different things also seems to be there to confuse.
You might be better asking questions on programming (i.e. not on C) in
comp.programmin g.
--
mike-yue said:
The topic comes from a question:
Would you rather wait for the results of a quicksort, a linear search,
or a bubble sort on a 200000 element array?
1Quicksort
2Linear Search
3Bubble Sort
The answer is 2Linear Search
Could someone explain why Linear Search, not the other two options?
Or I misunderstood the original question?
The question is testing your knowledge of algorithmic complexity.
As the number of data items rises (especially past the limit where you can
reasonably think of all numbers as being basically the same size), you can
begin to ignore minor factors like the cost of overheads (e.g. opening a
file) and even, to some extent, the machine speed! All that matters, for
large N, is how this N affects the algorithm.
Quicksort is O(N * log N). Linear search is O(N). Bubble sort is O(N * N).
To understand, plot the graphs.
--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
mike-yue wrote:
The topic comes from a question:
Would you rather wait for the results of a quicksort, a linear
search, or a bubble sort on a 200000 element array?
1Quicksort
2Linear Search
3Bubble Sort
The answer is 2Linear Search
Could someone explain why Linear Search, not the other two options?
Or I misunderstood the original question?
Given that 1 and 3 are sorts, and 2 is a search, and given that it's
far from clear what 'result' you're supposedly waiting for, I'd say
you have misunderstood, or you've mis-remembered it.
In any case, this is a general programming question, not a question
on the C language.
--
Peter
All very good answers. many thanks for you guys,
In a word, the Liner Search is the cheapest method to search. the
other two are complicated and expensive.
I know it is about algorithmic complexity, but I totally forget the
defination of the O, even the Log. University time seems a century ago
I almost forget everything.
I think it is useless for 99% programmer jobs, unfortunately it's
always been asked. Once a interviewer asked me to explain the
algorithmic complexity of quick sort!
Thanks again
mike-yue said:
All very good answers. many thanks for you guys,
In a word, the Liner Search is the cheapest method to search. the
other two are complicated and expensive.
Whilst your claim is true, it is meaningless. Linear search is a search
technique. The other two are sorting techniques. It's tempting to say that
you're comparing apples with oranges, but it's more like comparing apples
with October.
I know it is about algorithmic complexity, but I totally forget the
defination of the O, even the Log. University time seems a century ago
I almost forget everything.
I think it is useless for 99% programmer jobs,
That's only true because 99% of programming jobs don't actually require
very much programming skill.
unfortunately it's
always been asked. Once a interviewer asked me to explain the
algorithmic complexity of quick sort!
Well, that's a reasonable question, isn't it? And hardly difficult.
--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
mike-yue <ne*********@gm ail.comwrites:
All very good answers. many thanks for you guys,
In a word, the Liner Search is the cheapest method to search. the
other two are complicated and expensive.
Please quote some context when you post a followup.
The missing context is the question in your original article:
| Would you rather wait for the results of a quicksort, a linear search,
| or a bubble sort on a 200000 element array?
| 1Quicksort
| 2Linear Search
| 3Bubble Sort
but neither Quicksort nor Bubblesort is a searching algorithm. Since
they do entirely different things, asking which one you'd rather wait
for doesn't make a whole lot of sense.
I know it is about algorithmic complexity, but I totally forget the
defination of the O, even the Log. University time seems a century ago
I almost forget everything.
I think it is useless for 99% programmer jobs, unfortunately it's
always been asked. Once a interviewer asked me to explain the
algorithmic complexity of quick sort!
And this was a problem? That's certainly something I'd expect any
good programmer to know. If you're going to be writing code that does
sorting and searching, and you don't know this stuff, there's an
excellent chance your code is going to be unacceptable slow.
(Quicksort is O(N log N) best case and average case; a straightforward
implementation is O(N**2) worst case, but it can be made O(N log N)
with a little tweaking.)
--
Keith Thompson (The_Other_Keit h) <ks***@mib.or g>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
>>>>"my" == mike-yue <ne*********@gm ail.comwrites:
myThe topic comes from a question: Would you rather wait for the
myresults of a quicksort, a linear search, or a bubble sort on a
my200000 element array?
I myself would rather wait for the results of a bubble sort; this
means I have much more chance of my tea being ready before the result
set is.
Charlton
--
Charlton Wilbur cw*****@chromat ico.net
Richard Heathfield wrote:
mike-yue said:
>All very good answers. many thanks for you guys, In a word, the Liner Search is the cheapest method to search. the other two are complicated and expensive.
Whilst your claim is true, it is meaningless. Linear search is a search
technique. The other two are sorting techniques. It's tempting to say that
you're comparing apples with oranges, but it's more like comparing apples
with October.
>I know it is about algorithmic complexity, but I totally forget the defination of the O, even the Log. University time seems a century ago I almost forget everything.
I think it is useless for 99% programmer jobs,
That's only true because 99% of programming jobs don't actually require
very much programming skill.
Or in my case, 99% of programming has been making hardware or web pages
tick, without a bit O in sight!
--
Ian Collins.
mike-yue wrote:
>
The topic comes from a question:
Would you rather wait for the results of a quicksort, a linear
search, or a bubble sort on a 200000 element array?
1Quicksort
2Linear Search
3Bubble Sort
The answer is 2Linear Search
Could someone explain why Linear Search, not the other two
options? Or I misunderstood the original question?
It's a poor question. Quicksort is O(nLOGn), Linear search is
O(n), and bubble sort is O(n*n), where n is the size of the array,
here 200000. However linear searching doesn't require sorting, it
only requires examining each member of the original array for
equality. Since you get the linear answer quickest, and don't need
the array sorted, that is the optimum answer. The code is also the
simplest:
for (i = 0; i <= 200000; i++) {
if (a[i] == item) break;
}
if ((i <= 200000) && (a[i] == item)) return i;
else /* failure */ return -1;
--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.
** Posted from http://www.teranews.com ** This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: LRW |
last post by:
I have a page that's doing a search of a database, create an array and
displays it. And I have it displaying the array just fine, but when I
try to sort it, I get the error:
Warning: sort() expects parameter 1 to be array, null given in
/home/iestud/public_html/gto/search.php on line 43
(line 43 is the sort() function).
Here's the page--go to:
http://gto.ie-studios.net/item.php?itemid=3
|
by: pertheli |
last post by:
Hello,
I have a large array of pointer to some object. I have to run test
such that every possible pair in the array is tested.
eg. if A,B,C,D are items of the array,
possible pairs are AB, AC, AD, BC and CD.
I'm using two nested for loop as below, but it is running very slow
whenever I access any data in the second loop.
|
by: John Bullock |
last post by:
Hello,
I am at wit's end with an array sorting problem. I have a
simple table-sorting function which must, at times, sort on columns that
include entries with nothing but a space (@nbsp;). I want all of the
spaces to be put in the first slots of the array. IE 6 does this. But
Firefox 0.9.1 doesn't, and I don't know why.
I have not been able to reproduce it in very simple form (which
is itself a puzzle). But example code is...
|
by: Roy Gourgi |
last post by:
Hi,
My program seems to slow down drastically because as I fill my array and
table with many values, the program suffers tremendously. The first thing my
program does is to search the jagged array to try to find an element in that
array. If it does not find that element in that array, then it adds another
element and that is the problem. Once I have many elements in that array, it
takes a long time to do a search. Furthermore, not...
|
by: Chris |
last post by:
Wondering the best way of storing my data.
This is data pulled and stored in the database but a lot of data
manipulation goes on the client side. I never have to remove items but
will sometimes clear them all out. It seems to me the best way,
resource wise, would be just a string array and then use redim when I
have to add a new "row" of data. Arraylist & datatables seem easier to
work with, but since I don't need much of the extra's...
| |
by: yeti349 |
last post by:
Hi, I'm using the following code to retrieve data from an xml file and
populate a javascript array. The data is then displayed in html table
form. I would like to then be able to sort by each column. Once the
array elements are split, what is the best way to sort them? Thank you.
//populate data object with data from xml file.
//Data is a comma delimited list of values
var jsData = new Array();
jsData = {lib: "#field...
|
by: karan.shashi |
last post by:
Hey all,
I was asked this question in an interview recently:
Suppose you have the method signature
bool MyPairSum(int array, int sum)
the array has all unique values (no repeats), your task is to find two
|
by: Nobody |
last post by:
I've been looking for a job for a while now, and have run into this
interview question twice now... and have stupidly kind of blown it twice...
(although I've gotten better)... time to finally figure this thing out...
basically the interview question is: given an unsorted listed such as:
3,1,3,7,1,2,4,4,3
find the FIRST UNIQUE number, in this case 7... and of course the list can
be millions long...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| | |