Question

Bubble and Selection Sort

For this assignment, you are to consider bubble and selection sort. Both are O(n^2) however it may be possible to classify one algorithm as being more efficient than the other. You are to discuss which algorithm you feel is the most efficient and in what cases it will be more efficient. Provide any relevant test cases and code to support your belief. Submit a pdf containing your findings and test results along with any relevant code supporting your findings to the dropbox.

Answer 1

If we talk about bubble and selection sort then these both algo's having same complexity in all cases like:

1) Worst case complexity (O(n^2)) for both sorting
2) Best case complexity (O(n^2)) for both sorting
3) Average case complexity (O(n^2)) for both sorting

Although having the same complexity if we compare both the alog's then the selection sorting is more efficient than bubble sorting due to following reasons:

i) In bubble sorting we required more number of comparision , so the swap time taken in bubble sort is also high while in selection sort the swap time is less.
ii) Selection sort is also effecient because with selection sort memory writes are also very less, while with bubble sort memory writing is done more often.
So if in your environment memory writting is more costly then we have to prefer selection sort.
iii) As bubble sort having more memory writes which will take time, so response time of bubble sort is also slow.