Q22biii What search to use with 10 000 items question (1 Viewer)

Osiris8732

Member
Joined
Sep 14, 2004
Messages
48
What did people get for this question?
I said Insertion sort, because it can make use of a binary search which is much faster than a linear seach needed for a Selection Sort.
Many people in my class went with Selection, so what do people think is the correct answer?
 

ZzJasonzZ

Member
Joined
Mar 25, 2004
Messages
36
Location
Sydney
I believe the correct answer is Insertion Sort but not for the reason you said... a Bubble sort and a Selection sort need to pass through all 10,000 elements each "pass" so if on avage it needs about 8,000 passes (assuming some elements are already in order) each sort would need to go through 80,000,000 elements... on the other hand an insertion sort divides the array into two parts so the first pass only goes through 2 element, the second pass 3 elements, etc etc so it would take 1+2+3+...+10,000 which is alot less than 80 million
 

xeriphic

Member
Joined
May 7, 2004
Messages
452
Location
Sydney
I don't really think talking about sorts should related to searching, whereas talking about searching would be nice to relate to sorting, as binary search is dependent on it

then again any sort would be applicable for binary search, linear search is for array which is not in order, which means it has nothing to do with sorting
 

Jebu

New Member
Joined
Sep 17, 2004
Messages
16
an insertion sort is as you said, 1+2+3..+10,000, but a selection sort does not need to search the sorted area, hence it is 10,000+9,999+...+1 as the sorted area will grow with each pass, and since they are known to be the highest/lowest value, there is no need to search them, simply swap the next value into place.
 

PoP 'n' Fresh

Poke me! I giggle!
Joined
Aug 23, 2004
Messages
193
Location
Manly
Gender
Male
HSC
2005
i cant remember now, but was the question a "justify"... cos that means selection and insertion are both right if u just explained why whichever was better
 

token girl

Member
Joined
Nov 25, 2003
Messages
40
Location
How specific do you want? Earth do? :-p
Gender
Female
HSC
2004
Osiris8732 said:
What did people get for this question?
I said Insertion sort, because it can make use of a binary search which is much faster than a linear seach needed for a Selection Sort.
Many people in my class went with Selection, so what do people think is the correct answer?
I said the same as you. But yeah, I also think as long as it was justified well, practically anything will be ok, or you'll at last get some marks anyway.
 

xeriphic

Member
Joined
May 7, 2004
Messages
452
Location
Sydney
ehhh not to sound harsh or anything, but justifying in terms of searches is not the right answer, especially saying that insertion sort can use binary search, that doesn't make sense as all sorts are used to order the array so it can carry out binary search, and linear search uses array which is not sorted, so it doesn't use selection sort, the concept of search and sorts are a bit confused here

bubble
selection
insertion
are sorts which are used to order an array in an specific order

linear
binary
are searches to located a value from the array

while binary use the technique of spliting the array into halves and eliminating the side which does not contain the value, therefore it can only work in sorted arrays

and linear searches follows a sequential order to carry its search process, therefore since it begins at the beginning and works its way to the end, sorted array does not matter in this situation
 

Archman

Member
Joined
Jul 29, 2003
Messages
337
Gender
Undisclosed
HSC
N/A
i thought it was insertion as on average it uses less number of comparisons than the other two.
 

xeriphic

Member
Joined
May 7, 2004
Messages
452
Location
Sydney
it was insertion, just that the reasons he used to justify his choice wasn't correct that's all
 

PoP 'n' Fresh

Poke me! I giggle!
Joined
Aug 23, 2004
Messages
193
Location
Manly
Gender
Male
HSC
2005
its reasonable reasoning to me... if u think about it, it does it even faster than the ways you people described it... instead of doing 10000 searches or whatever, the binary search does it super fast
 

xeriphic

Member
Joined
May 7, 2004
Messages
452
Location
Sydney
obviously binary is faster

but relating to the question, it asked you a sorting method not searching method, therefore you have to provide features of the SORTING METHOD which will be the fastest, as for searching, it is totally irrelevant to the question
 

Archman

Member
Joined
Jul 29, 2003
Messages
337
Gender
Undisclosed
HSC
N/A
ok fine, here is what i wrote in the exam;
in a bubble sort, on the kth pass, exactly 10000-k (or was it, 1000-k-1, doesnt matter too much anyway) is needed to find the largest element in the unsorted part of the algorithm.

in a selection sort, a linear search is performed on the unsorted part at the kth pass, which again uses 10000-k comparisons.

while in a insertion sort, a MAXIMUM of k comparisons is needed on the kth pass as the we can stop once we find the correct position of the unsorted element in the sorted part.

so bubble and selection take 1+2+...+10000 each while an insertion sort takes a MAXIMUM of that same number, but in reality it usually takes a lot less as the MAXIMUM scenario rarely happens.

EDIT: sorry didn't see jason's intial post before posting. but hey, at least i know that i'm right now.
 

Whitlamsfan

New Member
Joined
Mar 3, 2004
Messages
15
The correct answer is anything but bubble as my teacher said afterwards. But even bubble was acceptable if you could justify why.
 

sladehk

le random
Joined
Jul 26, 2004
Messages
1,000
Gender
Undisclosed
HSC
2006
ummm

i chose selection because i thought insertion was the one where you needed to shift all the other unsorted ones
 

D-Train

New Member
Joined
Nov 17, 2004
Messages
1
Gender
Male
HSC
2010
correct answer

To get the full 3 marks I think you had to explain (i.e Justify) why Insertion or Selection is better than Bubble in the context of a 10,000 element array.

So you needed to explain that because Bubble swaps adjacent items until they are in the correct position it does alot more computations then say insertion which places the next item from the unsorted section of the array into its correct position in the sorted part of the array. Therefore for a 10,000 element array the difference in computations is large.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top