-
Notifications
You must be signed in to change notification settings - Fork 0
/
insertionsort.cpp
34 lines (31 loc) · 916 Bytes
/
insertionsort.cpp
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
// Insertion Sort
//
// Author: Rob Gysel
// ECS60, UC Davis
// Adapted from: Lysecky & Vahid "Data Structures Essentials", zyBooks
#include "insertionsort.h"
int InsertionSortCompares=0;
int InsertionSortMemaccess=0;
void InsertionSort(std::vector<int>* numbers) {
int i = 0;
int j = 0;
int temp = 0; // Temporary variable for swap
for (i = 1; i < (int)numbers->size(); ++i) {
j = i;
// Insert numbers[i] into sorted part
// stopping once numbers[i] in correct position
InsertionSortCompares+=1;
InsertionSortMemaccess+=2;
while (j > 0 && (*numbers)[j] < (*numbers)[j - 1]) {
// Swap numbers[j] and numbers[j - 1]
temp = (*numbers)[j];
InsertionSortMemaccess+=1;
(*numbers)[j] = (*numbers)[j - 1];
InsertionSortMemaccess+=2;
(*numbers)[j - 1] = temp;
InsertionSortMemaccess+=1;
--j;
}
}
return;
}