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 1
  5. Discussions

Insertion Sort - Part 1

Sort by

recency

|

895 Discussions

|

  • robertbielicki
     + 0 comments

    RUST: 

    fn insertionSort1(n: i32, arr: &[i32]) {
    let mut result = arr.to_vec();
    let number = result.pop().unwrap();
    result.insert((n-1) as usize, *result.last().unwrap());

    for idx in 1..=n {
        if idx < n && result[(n - idx -1) as usize] > number{
            result[(n - idx) as usize] = result[((n - idx - 1)) as usize];
        } else {
            result[(n-idx) as usize] = number;
            let strin = result.iter().map(|&x| x.to_string()).collect::<Vec<String>>().join(" ");
            println!("{}", strin);
            break;  
        }
        let strin = result.iter().map(|&x| x.to_string()).collect::<Vec<String>>().join(" ");
        println!("{}", strin);
    }
}

  • alban_tyrex
     + 0 comments

    Here is my c++ solution, you can watch the explanatoin here : https://youtu.be/xFqneyHR96g

    void printArr(vector<int> arr){
    for(int i = 0; i < arr.size(); i++){cout << arr[i] << " ";}
    cout << endl;
}
void insertionSort1(int n, vector<int> arr) {
    int last = arr[arr.size()-1];
    for(int i = arr.size() - 1; i >= 0; i--){
        if(last < arr[i-1]) {
            arr[i] = arr[i-1];
            printArr(arr);
        }
        else{
            arr[i] = last;
            printArr(arr);
            break;
        }
    }
}

  • patrickgao2020
     + 0 comments

    Here's 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]
            print(" ".join([str(i) for i in arr]))
        else:
            arr[i + 1] = insert
            print(" ".join([str(i) for i in arr]))
            return
    arr[0] = insert
    print(" ".join([str(i) for i in arr]))

  • mrsushilpatel201
     + 1 comment

    Python3: Time Complexity: O(n) (Extra) Space Complexity: O(1)

    def printArray(arr):
    for x in arr:
        print(x, end=' ')
    print()

def insertionSort1(n, arr):
    i = n - 2
    lastElement = arr[n - 1]
    while(i >= 0 and arr[i] > lastElement):
        arr[i + 1] = arr[i]
        printArray(arr)
        i = i - 1
    arr[i + 1] = lastElement
    printArray(arr)

  • michaelchen0611
     + 0 comments

    Time Complexity: O(n)

    Space Complexity: O(1)

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

// Done inplace
void insertionSort1(int n, int arr_count, int* arr) {
    int right_most_idx = arr_count-1;
    int num = arr[right_most_idx];
    while(num < arr[right_most_idx-1]){
        arr[right_most_idx] = arr[right_most_idx-1];
        printf_arr(n,arr);
        right_most_idx --;
    }
    arr[right_most_idx] = num;
    printf_arr(n, arr);
}