Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- using namespace std;
- //void Merch( vector<int> &first, vector<int> &second){
- // int i = 0;
- // int j = 0;
- // vector<int> SortArr( first.size() + second.size() );
- //
- // while( i < first.size() && j < second.size() ) {
- // if( first[i] > second[j] ) {
- // SortArr[i+j] = second[j];
- // j++;
- // } else {
- // SortArr[i+j] = first[i];
- // i++;
- // }
- // }
- //
- // if( i == first.size() ) {
- // for( ; j < second.size(); j++ ) {
- // SortArr[i+j] = second[j];
- // }
- // } else {
- // for( ; i < first.size(); i++ ) {
- // SortArr[i+j] = first[i];
- // }
- // }
- //}
- void SiftDown( vector<int> &arr, int i, int last ){
- int j = 0;
- int left = 0;
- int right = 0;
- while( i < last ) {
- j = i;
- left = (2 * i) + 1;
- right = left + 1;
- if( left < last && arr[j] < arr[left] ) {
- j = left;
- }
- if( right < last && arr[j] < arr[right] ) {
- j = right;
- }
- if( j == i ) return ;
- swap( arr[j], arr[i] );
- i = j;
- }
- }
- void BuildHeap( vector<int> &arr, int right ) {
- for( int i = right/2 - 1 ; i >= 0; i-- ) {
- SiftDown( arr, i, right );
- }
- }
- void HeapSort( vector<int> &arr, int right ){
- int last = right;
- BuildHeap( arr, right );
- while( last > 0 ) {
- swap( arr[0], arr[last] );
- SiftDown( arr, 0, last );
- last--;
- }
- }
- int med (vector<int> &arr, int right, int left)
- {
- int middle = (right+left)/2;
- if (arr[right] > arr[middle]) {
- if (arr[left] > arr[right]){
- return right;
- }
- return (arr[middle] > arr[left]) ? middle : left;
- }
- if (arr[left] > arr[middle]){
- return middle;
- }
- return (arr[right] > arr[left]) ? right : left;
- }
- void InsertionSort( vector<int> &arr, int left, int right ){
- for( int i = left + 1; i < right; ++i ) {
- int tmp = arr[i];
- int j = i - 1;
- for( ; j >= left && tmp < arr[j]; --j ) {
- arr[j + 1] = arr[j];
- }
- arr[j + 1] = tmp;
- }
- }
- int Partition ( vector<int> &arr, int left, int right) {
- int i = left;
- int j = right - 1;
- int median = med(arr, right, left);
- int pivot = arr[median];
- while ( i <= j ) {
- for ( ; i <= right && ( arr[i] < pivot ); i++ ) {
- }
- for ( ; j >= left && ( arr[j] >= pivot ); j-- ) {
- }
- if ( i < j ) {
- swap ( arr[i++], arr[j--] );
- }
- }
- swap ( arr[i], arr[median] );
- return i;
- }
- void QSort ( vector<int> &arr, int left, int right ) {
- if ( right - left >= 11 ) {
- int part = Partition(arr, left, right);
- QSort(arr, left, part - 1);
- QSort ( arr, part + 1, right );
- } else {
- InsertionSort(arr, left, right + 1);
- }
- }
- int main() {
- int n = 0;
- int tmp = 0;
- vector<int> arr(0);
- ifstream text("input.txt");
- while (!text.eof()){
- text >> tmp;
- arr.push_back(tmp);
- }
- arr.pop_back();
- text.close();
- n = arr.size();
- QSort ( arr, 0, n - 1 );
- for ( int i = 9; i < n; i=i+10 ) {
- printf("%d", arr[i]);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement