Bubble sort, select sort, insert sort c and python implementation

Bubble sort:

Bubble sorting is one of the classical sorting algorithms, with time complexity of O(n2). The basic principle is as follows:

python implementation:

# Bubble sorting
# Compare two elements at a time and repeat the visit
# The largest number in the series will be directly moved to the last after multiple comparisons, and will not participate in the next comparison
# Because smaller elements will slowly'float'To the top of the sequence, so it is called bubble sorting

# routine

def bubblesort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j]


c. realize:

void bubble_sort(int arr[], int len)
    int i, j, temp;
        for (j = 0; j < len - 1 - i; j++)
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

By comparing the two programs, we can see that both of them realize the bubble sorting function through two-stage for loop. In python, the declaration of variables is simplified, and array members are directly exchanged through a,b=b,a.



Insert sort:

(generally discussed according to the worst time complexity) the time complexity is O(n2). Through the c routine, see its implementation method.

First store arr[1] in temp, and then enter the next for loop. At this time, if arr[j-1], that is, arr[0] is greater than temp, the elements in arr[0] are placed in arr[1], and the elements in previous arr[1] are placed in arr[0]. Simple summary: arr[1] is compared with the previous array elements, and the large ones are put behind. The small one is in front.

Then, the second for loop comes, i=2. At this time, it is not difficult to see that in the for (J = I; J > 0 & & arr [J - 1] > temp; J --) loop, arr[2] (temp) is compared with the previous elements in turn. If the previous element is greater than temp, the previous element will move backward once. If the previous element is less than temp, temp will be placed behind this element. This is the core meaning of "insert" sorting. (it is easier to understand by looking up picture materials, which is omitted here)

c implementation

//Insert sort:For unordered data, scan backward and forward in the sorted sequence, find the corresponding position and insert

void insertion_sort(int arr[], int len)
    int i, j, temp;
    for (i = 1; i < len; i++)
        temp = arr[i];
        for (j = i; j > 0 && arr[j - 1] > temp; j--)
            arr[j] = arr[j - 1];
        arr[j] = temp;


python implementation

# Insert sort
def insertionSort(arr):

    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key




Select sort:

Time complexity O(n2). Algorithm implementation: first find the minimum value in all array elements and put it in the front, then remove the sorted minimum value array elements, and then find the minimum value of the remaining elements (i.e. "select the minimum value") and put it in the front until all elements are sorted.

c. realize:

//Select sort

void swap(int *a, int *b)
    int temp = *a;
    *a = *b;
    *b = temp;
void selection_sort(int arr[], int len)
    int i, j;
    for (i = 0; i < len - 1; i++)
        int min = i;
        for (j = i + 1; j < len; j++)  //Visit unsorted programs
            if (arr[min] > arr[j])
                min = j;  //Record the minimum position of the number of unsequenced
            swap(&arr[i], &arr[min]);  //Minimum and arr[i]Make an exchange


python implementation:

# Select sort
# Specify an element
# Compare in turn and put the smallest element first
# Then continue to compare the remaining elements until the sorting is completed

# routine

def seletesort(A):
    for i in range(len(A)):
        min_id = i
        for j in range(i+1, len(A)):
            if A[min_id] > A[j]:
                min_id = j
        #  take i Sign position and min_id Value exchange of sign position(actually a,b=b,a It's a change of address)
        A[i], A[min_id] = A[min_id], A[i]


(refer to the official website of rookie tutorial for some program ideas)

Posted by aprinc on Mon, 23 May 2022 13:24:01 +0300