Skip to content

Commit ea7b15b

Browse files
committed
Merge branch 'johnhuichen-gh-pages' into gh-pages
2 parents e7cace5 + 35e6d8d commit ea7b15b

2 files changed

Lines changed: 57 additions & 39 deletions

File tree

‎algorithm/sorting/comb/basic/code.js‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,8 @@ do{
1515
swapped = false; // initialize swapped
1616
// a single comb over the input list
1717
for( var i=0; i+gap < N; i++ ){
18+
tracer._select(i)._select(i+gap)._wait();
19+
1820
if( D[i] > D[i+gap] ){
1921
logger._print('swap ' + D[i] + ' and ' + D[i+gap]); // log swap event
2022

@@ -27,5 +29,6 @@ do{
2729

2830
swapped = true; // Flag swapped has happened and list is not guaranteed sorted
2931
}
32+
tracer._deselect(i)._deselect(i+gap);
3033
} // End of combing
3134
} while( gap!=1 || swapped )
Lines changed: 54 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -1,57 +1,72 @@
1-
logger._print( 'original array = [' + D.join(', ') + ']' );
1+
logger._print('original array = [' + D.join(', ') + ']');
22
var N = D.length;
33
var writes = 0;
44
var pos;
55
var item;
66
var temp;
7-
for( var cycleStart=0; cycleStart<=N-2; cycleStart++ ){
8-
item = D[cycleStart];
9-
pos = cycleStart;
10-
for( var i=cycleStart+1; i<=N-1; i++ ){
11-
if( D[i]<item ){
12-
pos++;
13-
}
14-
}
15-
if( pos == cycleStart ){
16-
continue;
17-
}
18-
while( item == D[pos] ){
19-
pos++;
20-
}
21-
temp = D[pos];
22-
D[pos] = item;
23-
item = temp;
7+
for (var cycleStart = 0; cycleStart <= N - 2; cycleStart++) {
8+
item = D[cycleStart];
9+
pos = cycleStart;
10+
tracer._select(cycleStart);
2411

25-
logger._print( 'Rewrite '+D[pos]+' to index '+pos );
12+
for (var i = cycleStart + 1; i <= N - 1; i++) {
13+
tracer._select(i)._wait()._deselect(i);
14+
if (D[i] < item) {
15+
pos++;
16+
}
17+
}
18+
if (pos == cycleStart) {
19+
tracer._deselect(cycleStart);
20+
continue;
21+
}
22+
while (item == D[pos]) {
23+
pos++;
24+
}
2625

27-
tracer._notify(pos, D[pos])._notify(cycleStart, D[cycleStart])._wait();
28-
tracer._denotify(pos)._denotify(pos);
26+
temp = D[pos];
27+
D[pos] = item;
28+
item = temp;
2929

30+
if (pos !== cycleStart) {
31+
logger._print('Rewrite ' + D[pos] + ' to index ' + pos + '; the next value to rewrite is ' + item);
32+
} else {
33+
logger._print('Rewrite ' + D[pos] + ' to index ' + pos);
34+
}
35+
tracer._select(pos)._wait()._deselect(pos);
36+
tracer._notify(pos, D[pos])._notify(cycleStart, D[cycleStart])._wait();
37+
tracer._denotify(pos)._denotify(cycleStart);
3038

31-
while( pos != cycleStart ){
32-
pos = cycleStart;
33-
for( i=cycleStart+1; i<=N-1; i++ ){
34-
if( D[i]<item ){
35-
pos++;
36-
}
37-
}
39+
while (pos != cycleStart) {
40+
pos = cycleStart;
3841

39-
while( item == D[pos] ){
40-
pos++;
41-
}
42-
temp = D[pos];
43-
D[pos] = item;
44-
item = temp;
42+
for (i = cycleStart + 1; i <= N - 1; i++) {
43+
tracer._select(i)._wait()._deselect(i);
44+
if (D[i] < item) {
45+
pos++;
46+
}
47+
}
4548

46-
logger._print( 'Rewrite '+D[pos]+' to index '+pos );
49+
while (item == D[pos]) {
50+
pos++;
51+
}
4752

48-
tracer._notify(pos, D[pos])._notify(cycleStart, D[cycleStart])._wait();
49-
tracer._denotify(pos)._denotify(pos);
53+
temp = D[pos];
54+
D[pos] = item;
55+
item = temp;
5056

51-
writes++;
57+
if (pos !== cycleStart) {
58+
logger._print('Rewrite ' + D[pos] + ' to index ' + pos + '; the next value to rewrite is ' + item);
59+
} else {
60+
logger._print('Rewrite ' + D[pos] + ' to index ' + pos);
5261
}
62+
tracer._select(pos)._wait()._deselect(pos);
63+
tracer._notify(pos, D[pos])._notify(cycleStart, D[cycleStart])._wait();
64+
tracer._denotify(pos)._denotify(cycleStart);
5365

5466
writes++;
67+
}
68+
69+
writes++;
5570
}
5671

57-
logger._print( 'Number of writes performed is ' + writes );
72+
logger._print('Number of writes performed is ' + writes);

0 commit comments

Comments
 (0)