Why the fuck do you start with j = 2?
>>58711152
Because 2 > 1 which makes it way better
>>58711152
Look at the inner loop
>i = j - 1
i is trailing j as it iterates through the loop. when j=2, i =1 and it hits the first element.
This is the correct function
>>58711152
A is 1 indexed and you compare against j-1
>>58711152
A is indexed from 1 to A.length
A[1] is already sorted
>>58711152
Because A[1] is initialized to some pre-computed value which is needed to compute A[2] and so on. However, only values starting at A[2] need to be computed. It's similar to x! = (x-1)!x so you define it as A[1] = 1 A[2] = 1 A[n] = A[n-1] * n.
>reading CLRS
>Arrays are 1-indexed for sorting algorithms
>Arrays are 0-indexed for hash tables
>algorithms textbook co-authored by people who invented RSA
>>58711152
A better question is why the fuck are you bothering with insertion sort? Merge sort and quick sort are the only ones worth mentioning and the reality is that 99.99% of programmers will never have to write a sort algorithm themselves.
>>58716286
Insertion sort is the fastest for small arrays, and any good quicksort algorithm will have a threshold in the partioning step where it does an insertion sort on the remaing bits.
>>58711152
- Because CLRS uses 1-based arrays.
- And you need to compare the jth element to the element before it.
- So, you have to start at j = 2 so you can compare A[j] to A[j-1] (which is A[1])
>>58716286
Maybe he just started reading the book.