Insertion Sort - Part 2

Sort by

recency

|

577 Discussions

|

  • + 0 comments
    def insertionSort2(n, arr):
        # Write your code here
        
        for i in range(1, n):
            key = arr[i]
            j = i - 1
            while j >= 0 and key < arr[j]:
                arr[j+1] = arr[j]
                j -= 1
            arr[j+1] = key
            print(" ".join(str(x) for x in arr))
    
  • + 0 comments

    Here is problem solution in python java c++ c and Javascript - https://programmingoneonone.com/hackerrank-insertion-sort-part-2-problem-solution.html

  • + 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;
        }
    }
    
  • + 0 comments

    Python Solution:

    def insertionSort2(n, arr):
        # Write your code here
        for i in range(len(arr)):
            part_sorted = sorted(arr[:(i+1)]) + arr[i+1:]
            if i > 0:
                print(' '.join([str(x) for x in part_sorted]))
    
  • + 0 comments

    My Java solution with o(n^2) time complexity and o(1) space complexity:

    public static void insertionSort2(int n, List<Integer> arr) {
            if(n == 1) System.out.println(arr.get(0)); //len of 1 is already sorted
            
            //separate arr into sorted and unsorted portions
            for(int i = 1; i < arr.size(); i++){
                int j = i - 1;
                int currVal = arr.get(i);
                int prevVal = arr.get(j);
                
                //compare prev element with curr element
                if(currVal < prevVal){
                    while(currVal < prevVal){
                        arr.set(j + 1, prevVal);
                        arr.set(j, currVal);
                        j--;
                        if(j >= 0) prevVal = arr.get(j);
                        else break;
                    }
                }
                
                //print the arr
                arr.forEach(l -> System.out.print(l + " "));
                System.out.println();
            }
        }