Solid algorithm foundation (1) – bubble sort and selection sort algorithm

Sorting algorithms are the basis for other algorithms, many of which are based on sorted arrays. In real life, in many cases, some data are arranged in order from small to large or from large to small. For sorted sequences, it is very convenient to find maximum, minimum, traverse, calculate, and solve

Basic concepts of sorting

The sorting

Arrange a set of data according to certain rules. The basic sorting object is integer, and the basic sorting rules include sorting from smallest to largest and sorting from largest to smallest.

The most basic sort algorithm

• Commutative sorting algorithm
• Selective sorting algorithm
• Insertion sort algorithm
• Merge sort algorithm
• Multi – way merge sort algorithm

Here, the multi-path merge sort algorithm divides the file into several small parts that can be read into the memory, and then reads them separately for sorting. After multiple processing, the sorting of large files is completed.

Sorting algorithm efficiency

The algorithm name	The average velocity	The slowest speed
Bubble sort	$O(n^2)$	$O(n^2)$
Quick sort	$O(n \log n)$	$O(n^2)$
Selection sort	$O(n^2)$	$O(n^2)$
Heap sort	$O(n \log n)$	$O(n \log n)$
Insertion sort	$O(n^2)$	$O(n^2)$
The shell sort	$O(n^{3/2})$	$O(n^2)$
Merge sort	$O(n \log n)$	$O(n \log n)$

Selection sort

Sorting algorithms are easy to understand, even if you don’t know any algorithms, if you were to give a sorting scheme, in fact, the scheme you give is probably the first choice sort that WE’re going to talk about today

Selection sort is a simple and intuitive sorting algorithm. How it works

• For the first time, the smallest (or largest) element is selected from the data elements to be sorted and stored at the beginning of the sequence
• It then finds the smallest (largest) element from the remaining unsorted elements and places it at the end of the sorted sequence
• And so on until the total number of data elements to be sorted is zero

• First at initialization I and j are 0, which is the current minimum of 5
• Point the current value to the next location and compare the current value to the current minimum because 2 is less than 5 (the current minimum)
• Then continue to move the current value pointer forward to the next position 3, comparing the current value with the current minimum value because 3 is greater than 2 (the current minimum value), this does not move the current minimum pointer forward

• As the current value continues to move forward to the last position 1
• Compare the current value 1 to the current minimum value 2 and move the pointer to the current minimum value to position 1
• Since the current value is at the end of the array, this swaps the first position value with the current minimum value (Step 6).

• The last outer iteration completes by replacing the first value of the array with the minimum value, and then the next iteration
• In this iteration, the second is replaced by the minimum value of the remaining n-1 array length
• Repeat the above steps until you iterate to the last value

class Solution:
    def selectionSortArray(self, nums:List[int]) - >List[int] :
        n = len(nums) - 1
        for i in range(n):
            min_index = i
            for j in range(i + 1, n):
                if (nums[j] <= nums[min_index]):
                    min_index = j
                temp = nums[i]
                nums[i] = nums[min_index]
                nums[min_index] = temp
        return nums
Copy the code

• We have n elements starting at 0 up to n-1
• The first loop goes from zero to n minus one each element, each loop
• The second loop repeats the currently sorted position

On time Complexity

When I = 0, j cycles n-1, when I = 1, j cycles n-1-1, when I = n-2, j = 1

Bubble sort

Bubble sort is the most basic of all sorting algorithms, the simplest sorting algorithm, with this algorithm efficiency is relatively low, but can be written quickly, in the sorting element is relatively small more useful.

Bubble sort algorithm flow

• For each data in the array, compare the size of two adjacent elements
• If the preceding data is greater than the following data, the two data are swapped. After the first round of multiple comparison sorts, the smallest data can be sorted
• The rest of the data is then compared in the same way, and the array is sorted from smallest to largest

So we have four elements here 5, 2, 3, 1 and we want to arrange these from smallest to largest, so first we’re going to look at the first logarithm 5 and 2 because we’re sorting from smallest to largest so we’re not sorting correctly, so we’re going to switch 5 and 2, and then we’re going to move forward, 5 and 3 and compare them, The relationship between them is also not correct, so we need to switch positions, and then we continue to move forward and compare the two adjacent elements, adjusting the position as needed, until we get to the end of the array, and then we finish an iteration, in which we move 5 forward to the end of the array. If you rotate the array by 90 it feels like 5 is going up and up like a bubble in water, and that’s how bubble sort gets its name.

class Solution:
    def bubbleSortArray(self, nums) :
        n = len(nums)
        for i in range(n):
            for j in range(0, n-i-1) :if nums[j] > nums[j+1]:
                    nums[j],nums[j+1] = nums[j+1],nums[j]
        return nums

Copy the code