Bubble sort

Gonna start from the bottom and work my way up. Starting from Bubble sort!

Bubble sort, as the name implies, bubble up the largest element to the top of the array. For a size k array, it will iterate it k times, each times, bring the kth largest element to the top.

    vector<int> sortArray(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i ++){
            for(int j = 0; j < nums.size() - 1; j ++){
                if(nums[j] > nums[j + 1]){
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        return nums;
    }

We can optimize it 2 ways
1: we know that at kth iteration, 1st … kth largest element are already in their right place. So we can stop swapping loop at k – 1.

2: If no swapping happens in a loop, we know the array is already sorted.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax