Sorting Algorithms (Insertion sort and bubble sort)

[Argus]

I'm having a hard time figuring out these two algorithms, or at least parts of them. My main issue is that I'm unsure of how the inner loop in both algorithms works.

Anyway this is what I have for the bubble sort:

SortingAlgos::bubbleSort(vector<int> vectorToSort)
{
    int tmpNumber;
    int numberOfElements = vectorToSort.size();
    for (int i = 0; i < numberOfElements - 1 ;i++){
        for (int j = 0; j < numberOfElements - i - 1; j++){
            if (vectorToSort[j] > vectorToSort[j+1]){
                tmpNumber = vectorToSort[j];
                vectorToSort[j] = vectorToSort[j+1];
                vectorToSort[j+1] = tmpNumber;
            }
        }
    }
}

By the inner loop I mean, the second for loop. I wrote the code myself based on what I've seen for this algorithm, but still I'm having a hard time figuring out the inner loop and as a result, I'm not so sure of what to use as a condition for it. I understand that the first loop is used to ensure that the algorithm makes all the required passes to place each element in their proper place.

If I understood correctly, the insertion sort is similar to this algorithm, it also has an inner loop, the difference as I understood it is that it compares elements one by one instead, of adjacent elements.

Anyway, if anyone can help me make sense of the inner loops I'd appreciate it.

[Duthomhas]

Bubble Sort
Bubble sort is not an obvious algorithm.

The inner loop makes a single pass over the data. For every pair of items that is out of order, it swaps them.

For example, here's an array of 6 disordered elements. Our (inner) loop will index from j=0 to j=4. Each time, j and j+1 will be compared and potentially swapped:

4 2 1 5 6 3
2 4          j=0
  1 4        j=1
    4 5      j=2
      5 6    j=3
        3 6  j=4
2 1 4 5 3 6

Now our data is closer to being properly ordered, but not entirely. We must do it again. (For this data, it must be done again twice.)

2 1 4 5 3 6  (from above after inner loop #1)
1 2 4 3 5 6  (after inner loop #2)
1 2 3 4 5 6  (after inner loop #3)

There are two things to notice. If we do another inner loop, nothing will be swapped. That is our clue that we're done.

However, there is also the worst-case possibility, sorting something in reverse:

6 5 4 3 2 1

This will take six times through the inner loop to sort it.

Now, the - i - 1 on line 6 there is because we can also reduce the number of comparisons by noticing that after each time through the inner loop, the (N-i)th element is in its final location. (More elements may also be in their location, but most bubble sorts are not optimized more than that.)


Insertion Sort
Insertion sort is easier to understand because it is one of the ways humans sort things normally. For example, if you wish to sort a deck of cards, you take the next card available and stick it in the correct spot in the sorted cards. Repeat until there are no more cards to sort.

Here's the FAQ on it, which includes a really helpful animation.

http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/insertion-sort/

The inner loop of an insertion sort takes the next item to insert and finds the insertion spot.

The outer loop repeats that for every item to insert.


Hope this helps.

[Argus]

Sorry for not answering sooner, but I was busy with something. Anyway, thank you, this made it easier to understand how it worked.