//quicksort with lomuto partition
void qs( int a[ ] , int l, int r) {
if ( l < r) {
int i = l - 1 , x = a[ r] ;
for ( int j = l ; j < r; j++ ) {
if ( a[ j] < x) {
++ i;
swap( a[ i] , a[ j] ) ;
}
}
++ i;
swap( a[ i] , a[ r] ) ;
qs( a, l, i - 1 ) ;
qs( a, i + 1 , r) ;
}
}
//quicksort with hoare partition, pivot is the last element of segment
void qs2( int a[ ] , int l, int r) {
int i = l, j = r, x = a[ r] ;
while ( i <= j) {
while ( a[ i] < x) ++ i;
while ( a[ j] > x) -- j;
if ( i <= j) {
swap( a[ i] , a[ j] ) ;
++ i; -- j;
}
}
if ( i < r) qs2( a, i, r) ;
if ( l < j) qs2( a, l, j) ;
}
Ly9xdWlja3NvcnQgd2l0aCBsb211dG8gcGFydGl0aW9uCgp2b2lkIHFzKGludCBhW10sIGludCBsLCBpbnQgcil7CglpZihsIDwgcil7CgkJaW50IGkgPSBsIC0gMSwgeCA9IGFbcl07CgkJZm9yKGludCBqID0gbCA7IGogPCByOyBqKyspewoJCQlpZihhW2pdIDwgeCl7CgkJCQkrK2k7CgkJCQlzd2FwKGFbaV0sIGFbal0pOwoJCQl9CgkJfQoJCSsraTsKCQlzd2FwKGFbaV0sIGFbcl0pOwoJCXFzKGEsIGwsIGkgLSAxKTsKCQlxcyhhLCBpICsgMSwgcik7Cgl9Cn0KCi8vcXVpY2tzb3J0IHdpdGggaG9hcmUgcGFydGl0aW9uLCBwaXZvdCBpcyB0aGUgbGFzdCBlbGVtZW50IG9mIHNlZ21lbnQKdm9pZCBxczIoaW50IGFbXSwgaW50IGwsIGludCByKXsKCWludCBpID0gbCwgaiA9IHIsIHggPSBhW3JdOwoJd2hpbGUoaSA8PSBqKXsKCQl3aGlsZShhW2ldIDwgeCkgKytpOwoJCXdoaWxlKGFbal0gPiB4KSAtLWo7CgkJaWYoaSA8PSBqKXsKCQkJc3dhcChhW2ldLCBhW2pdKTsKCQkJKytpOyAtLWo7CgkJfQoJfQoJaWYoaSA8IHIpIHFzMihhLCBpLCByKTsKCWlmKGwgPCBqKSBxczIoYSwgbCwgaik7Cn0K
compilation info
prog.cpp: In function ‘void qs(int*, int, int)’:
prog.cpp:9:5: error: ‘swap’ was not declared in this scope
swap(a[i], a[j]);
^~~~
prog.cpp:13:3: error: ‘swap’ was not declared in this scope
swap(a[i], a[r]);
^~~~
prog.cpp: In function ‘void qs2(int*, int, int)’:
prog.cpp:26:4: error: ‘swap’ was not declared in this scope
swap(a[i], a[j]);
^~~~
stdout