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

[Osiris8732]

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]

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]

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]

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]

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

 

[xeriphic]

then it means bubble sort could also be appropriate as long as you justify right

 

[token girl]

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]

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]

i thought it was insertion as on average it uses less number of comparisons than the other two.

 

[xeriphic]

it was insertion, just that the reasons he used to justify his choice wasn't correct that's all

 

[Archman]

... so whats the correct reason?

 

[PoP 'n' Fresh]

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]

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

 

[xeriphic]

... so whats the correct reason?

reasons which is similar to Jason's post above

 

[Archman]

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]

The correct answer is anything but bubble as my teacher said afterwards. But even bubble was acceptable if you could justify why.

 

[sladehk]

ummm

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

 

[D-Train]

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.