Difference between sorting methods selection dort, insert sort and bubble sort

4

I am studying the Data structure discipline and I am developing C ++ programs.

I know basically three sorts of sorts (sorts sort, insertion sort and bubble sort), but I do not know in detail the difference between three types.

What are these differences and in what cases use each type of order?

If this is also possible, I would like an example of each sorting type.

    
asked by anonymous 11.11.2016 / 22:29

1 answer

5
  • Selection Sort : At each iteration, it searches the entire unordered portion of the vector for the smallest (or largest) element and places it in the correct position. Thus, in the i-th iteration, the i-th lowest element goes to the i position, and so on.

  • Insertion Sort : Increasingly between positions. For each position, take its element and return it in the vector until it fits in the correct position (when it finds the first element smaller than it).

  • Bubble sort : Get two adjacent elements and change them if, and only if, they are out of order. It does this with all pairs of elements at each iteration. At the end of it, the smallest (or largest) element not yet ordered will be in the correct position. Repeat this until the end.

You can see them running visually here .

All of these are elementary algorithms that are easy to implement. Both Bubble and Selection have complexity O (n²) in all cases. Insertion , on the other hand, runs in O (n) at best (such as if the vector is already in ascending order). So it turns out to be a better algorithm for general purposes.

    
11.11.2016 / 22:59