We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Insertion Sort - Part 2
  5. Discussions

Insertion Sort - Part 2

Sort by

recency

|

572 Discussions

|

  • alban_tyrex
     + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/419S35Kb4Nw

    void insertionSort2(int n, vector<int> arr) {
    for (int i = 1; i < n; i++) {
        int current = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
        for(int i = 0; i < n; i++) cout << arr[i] << " ";
        cout << endl;
    }
}

  • patrickgao2020
     + 0 comments

    Here is my Python solution!

    def insertionSort1(n, arr):
    insert = arr[-1]
    index = list(reversed([i for i in range(len(arr) - 1)]))
    for i in index:
        if insert <= arr[i]:
            arr[i + 1] = arr[i]
        else:
            arr[i + 1] = insert
            return arr
    arr[0] = insert
    return arr

def insertionSort2(n, arr):
    for i in range(2, len(arr) + 1):
        print(" ".join([str (i) for i in insertionSort1(len(arr[:i]), arr[:i]) + arr[i:]]))
        arr = insertionSort1(len(arr[:i]), arr[:i]) + arr[i:]

  • michaelchen0611
     + 0 comments

    Time Complexity: O(n^2)

    Space Complexity: O(1)

    void printf_arr(int n, int* arr){
    for (int i = 0; i<n; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void swap(int* a, int* b){
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

void insertionSort2(int n, int arr_count, int* arr) {
    if (n == 1) printf("%d", arr[0]);
    for (int i = 1; i<n ; i++){
        int temp_idx = i;
        while (temp_idx > 0 && arr[temp_idx] < arr[temp_idx-1]){
            swap(&arr[temp_idx], &arr[temp_idx-1]);
            temp_idx --;
        }
        printf_arr(n, arr);
    }
}

  • kunalkawate424
     + 0 comments

    Solution from my side (Python)

    def insertionSort1(n, arr):
    for i in range(len(arr)-1):
        if(arr[i]>arr[i+1]):
            temp = arr[i+1]
            arr[i+1]=arr[i]
            arr[i]=temp
            for j in range(i+1):
                for k in range(j,i+1):
                    if(arr[j]>arr[k]):
                        temp = arr[k]
                        arr[k] = arr[j]
                        arr[j] = temp
            for num in arr:    
                print(num,end=' ')
            print()
        else:
            for num in arr:    
                print(num,end=' ')
            print()

  • vuhuutuan0
     + 0 comments

    My answer in Typescript, simple

    function insertionSort2(n: number, arr: number[]): void {
    /**
     * again, simple as question request
     * loop [i] from 1, call [insertionSort1] by that sub-array
     * print each loop
     * 
     * note:    [insertionSort1] is answer of previous question 
     *          (return arr instead of print)
     */
    for (let i = 1; i < arr.length; i++) {
        arr = [
            ...insertionSort1(arr.slice(0, i + 1)),
            ...arr.slice(i + 1)
        ]
        console.log(arr.join(' '))
    }
}