int runningTime(vector<int> arr) {
    int i,j;
    int value;
    int result = 0;
    for(i=1;i<arr.size();i++)
    {
        value=arr[i];
        j=i-1;
        while(j>=0 && value<arr[j])
        {
            arr[j+1]=arr[j];
            j=j-1;
            result ++;
        }
        arr[j+1]=value;
    }
    return result;
}

function runningTime($arr) {
    // Write your code here
    $total = 0;
    
    for ($i=0; $i < count($arr)-1; $i++) {
        $temp = 0;
        for ($j=$i+1; $j < count($arr); $j++) {
            if ($arr[$j] < $arr[$i]) {
                $temp = $arr[$j];
                // delete array $arr[$j]
                unset($arr[$j]);
                
                // insert in front of array
                array_splice( $arr, $i, 0, $temp );
                
                // count step
                $total = $total + ($j - $i);
                
                // re-index array
                $arr = array_values($arr);
            }
        }
    } 
    return $total;
}

count = 0
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and key < arr[j]:
            count +=1
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return count

function insertionSort1(arr: number[]): [number[], number] {
    let i = arr.length - 1
    let x = arr[i]
    let s = 0

    while (x != 0) {
        let t = arr[i - 1] ?? 0
        if (t < x) {
            arr[i] = x
            x = 0
        } else {
            arr[i] = arr[i - 1]
            i--
            s++
            if (t == x) s--
        }
    }

    return [arr, s]
}

const arrayCompare = <T>(arr1: T[], arr2: T[]): boolean => {
    if (arr1.length != arr2.length) return false;
    return arr1.every((e, i) => e == arr2[i])
}

function runningTime(arr: number[]): number {
    /**
     * with small changes from previos answer, counting swaping attemp and sum em all
     */

    let swap_counter = 0

    for (let i = 1; i < arr.length; i++) {
        let [sorted_part, swaped] = insertionSort1(arr.slice(0, i + 1))
        let arr_sorted = [...sorted_part, ...arr.slice(i + 1)]

        if (!arrayCompare(arr, arr_sorted)) {
            arr = arr_sorted
            swap_counter += swaped
        }
    }

    return swap_counter;
}

    public static int runningTime(List<Integer> arr) {
        int shiftCounter = 0;
        for (int i=1; i < arr.size(); i++) {
            for (int j=0; j < i; j++) {
                if (arr.get(i) < arr.get(j)) {
                    int toInsert = arr.remove(i);
                    arr.add(j, toInsert);
                    shiftCounter += i-j;
                }
            }
        }
        return shiftCounter;
    }