asked on insertion sort and bubble sort and merge sort and quick sortalgorithm
hi,
How is insertion sort algorithm different from bubble sort, quick sort, merge sort algorithm. which one to use where. what are advantages and disadvantages of each.
why we need inner for loop for all these sort algorithm and also temp variable.
also for loop declaration before inserting and displaying why the increment used as ++i rather that i++ as below
int[] content= new int[size];
for(int i = 0; i < size; ++i) {
please advise
How is insertion sort algorithm different from bubble sort, quick sort, merge sort algorithm. which one to use where. what are advantages and disadvantages of each.
why we need inner for loop for all these sort algorithm and also temp variable.
also for loop declaration before inserting and displaying why the increment used as ++i rather that i++ as below
int[] content= new int[size];
for(int i = 0; i < size; ++i) {
please advise
Java EEJavaProgramming Languages-Other
Last Comment
dpearson
SOLUTION
THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
SOLUTION
THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
ASKER CERTIFIED SOLUTION
THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
Bubble sort ... when given an already sorted, or almost sorted, list it is O(n).True, but that's not how insertion sort algorithm is different from bubble sort.
"I'm an old C developer and when I grew up computers were a lot slower than they are today"Or, a developer used to more recent languages in which i could be a large complex object that takes a lot more work to copy than just an int.
ASKER
let me understand more on these posts.
By the way i like the graphics here
http://www.sorting-algorithms.com/
I do see some wiki page has similar graphic but not forgot. please advise
By the way i like the graphics here
http://www.sorting-algorithms.com/
I do see some wiki page has similar graphic but not forgot. please advise
HI!
The links I provided in my earlier comment gives you the pros / cons of each algorithm as well as
the code and working live example.
Regards,
Tomas Helgi
The links I provided in my earlier comment gives you the pros / cons of each algorithm as well as
the code and working live example.
Regards,
Tomas Helgi
That graphical site is really cool - helps you grasp how those algorithms are really working, which can be hard to understand if you just stare at the code. Nice find.
Doug
Doug
ASKER
Insertion
Selection
Bubble
Shell
Merge
Heap
Quick
Quick3
Random
Nearly Sorted
Reversed
Few Unique
Discussion
These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to:
Show how each algorithm operates.
Show that there is no best sorting algorithm.
Show the advantages and disadvantages of each algorithm.
Show that worse-case asymptotic behavior is not always the deciding factor in choosing an algorithm.
Show that the initial condition (input order and key distribution) affects performance as much as the algorithm choice.
The ideal sorting algorithm would have the following properties:
Stable: Equal keys aren't reordered.
Operates in place, requiring O(1) extra space.
Worst-case O(n·lg(n)) key comparisons.
Worst-case O(n) swaps.
Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.
There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.
Sorting is a vast topic; this site explores the topic of in-memory generic algorithms for arrays. External sorting, radix sorting, string sorting, and linked list sorting—all wonderful and interesting topics—are deliberately omitted to limit the scope of discussion.
i am trying to understand this in detail. I was not clear which one is good and what are advantages and disadvantages of each.
What are those 4 initial conditions. I see pictures are moving but what to interpret from the graphics there. please advise
Random: no correlation between initial position and final position
Nearly Sorted: correlation between initial position and final position is close to 1
Reversed: correlation between initial position and final position is -1
Few Unique: most of the entries have duplicate values
Nearly Sorted: correlation between initial position and final position is close to 1
Reversed: correlation between initial position and final position is -1
Few Unique: most of the entries have duplicate values
ASKER
Reversed: correlation between initial position and final position is -1
what it mean by correclation and what it means by -1
please advise
http://www.merriam-webster.com/dictionary/reverse
in this context, it means in the opposite order, as in low to high vs high to low.
in this context, it means in the opposite order, as in low to high vs high to low.
ASKER
Nearly Sorted: correlation between initial position and final position is close to 1
what it means by above statement. please advise. what is 1
"nearly sorted" means the list is already close to sorted at the start.
E.g. "A,B,C,E,D,F,H,G" is nearly sorted.
Correlation is a measure of how similar two things are and goes from -1 (completely different) to +1 (completely the same).
So a nearly sorted list is very similar (has a correlation close to 1) to the final sorted list.
Make sense?
Doug
E.g. "A,B,C,E,D,F,H,G" is nearly sorted.
Correlation is a measure of how similar two things are and goes from -1 (completely different) to +1 (completely the same).
So a nearly sorted list is very similar (has a correlation close to 1) to the final sorted list.
Make sense?
Doug
++i and i++ have equivalent effects when the value of the operation is unused, as in the increment clause of a for loop,
however, if a return value is actually generated and not optimized out when not used, then not saving the value prior to the increment could save some effort.