-
Notifications
You must be signed in to change notification settings - Fork 0
/
InsertionSort
39 lines (32 loc) · 1014 Bytes
/
InsertionSort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Author @Brendan Han
// CSE374
// Objective: Learning how to write the insertion sort algorithm
import java.util.*;
public class Solution {
/**
* Returns the step of the insertion sort on the given step N
*
* @param list An ArrayList of the list that needs to be sorted
* @param N The step at which we want to display
* @return the ArrayList sorted at the N-th step
*/
public static int[] insertionSort(int[] list, int N) {
// A counter to stop the program when count == N
int count = 0;
for (int i = 1; i < list.length; i++) {
// Inserts list[i] into the sorted sequence list[1...i - 1]
int key = list[i];
int j = i - 1;
// A loop to traverse through the previous elements to
// compare and insert the key element in the correct index.
// An addition condition to stop the loop at the N-th step
while (j >= 0 && list[j] > key && N != count) {
list[j + 1] = list[j];
j = j - 1;
count++;
}
list[j + 1] = key;
}
return list;
}
}