C++
- @Linda_pp
- 清楚なC++メイドBOT
- 長谷川一輝
- @jj1bdx
- 安藤敏彦
- Siv3D
- @hnokx
- @ishidakei
- TAKEI Yuya
- I (@wx257osn2)
- Tommy6
- @nekketsuuu
- LouiS0616
- @volanja
- 大鎌広
- むてら
- ガチKGB
- 三重野賢人
x
66
1
2
3
int n;4
int* a;5
6
template<class ItemType>7
int insertionsort(ItemType theArray[], int n) {8
int counter = 0; //keeps track of number of comparisons9
10
for (int unsorted = 1; unsorted < n; unsorted++) {11
ItemType nextItem = theArray[unsorted];12
int loc = unsorted;13
//counter++;//increment here14
15
while ((loc > 0) && (counter++,theArray[loc - 1] > nextItem)) {16
//if(theArray[loc - 1] > loc){17
//counter++; //increment here18
//}19
theArray[loc] = theArray[loc - 1];20
loc--;21
}22
theArray[loc] = nextItem;23
}24
25
return counter;//returns the number of comaparisons26
}27
28
29
int* makeRandomArray(int n, int seed) {30
srand(seed);31
int * a = new int[n];32
for (int i = 0; i < n; i++) {33
a[i] = rand() % 1000;34
}35
return a;36
}37
38
int main(){39
const int seed = 9000;40
/******************************/41
/* Start of Insertion Sort */42
/******************************/43
44
std::cout << "Insertion sort";45
46
n = 10;47
a = makeRandomArray(10, seed);48
std::cout <<std::setw(13)<< insertionsort(a, n);49
delete[] a;50
51
n = 100;52
a = makeRandomArray(100, seed);53
std::cout <<std::setw(13)<< insertionsort(a, n);54
delete[] a;55
56
n = 1000;57
a = makeRandomArray(1000, seed);58
std::cout <<std::setw(13)<< insertionsort(a, n);59
delete[] a;60
61
n = 10000;62
a = makeRandomArray(10000, seed);63
std::cout <<std::setw(13)<< insertionsort(a, n)<<std::endl;64
delete[] a;65
}66
$ g++ prog.cc -Wall -Wextra -std=c++11 -pedantic
Start
Insertion sort 38 2600 242928 25053566
0
Finish