Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //============================================================================
- // Name : Algo7Module2.cpp
- // Author :
- // Version :
- // Copyright : Your copyright notice
- // Description : Hello World in C++, Ansi-style
- //============================================================================
- #include <iostream>
- #include <assert.h>
- #include <cstdio>
- #include <stdlib.h>
- using namespace std;
- struct limit {
- int left;
- int right;
- limit(){
- left = 0;
- right = 0;
- }
- };
- class CQueue{
- public:
- CQueue(int n){
- this->tail = 0;
- this->head = 0;
- this->array = new limit[n];
- this->array_length = n;
- }
- ~CQueue(){
- delete (this->array);
- }
- limit pop_f();
- void push_b(limit data);
- bool isEmpty();
- private:
- int tail;
- int head;
- limit *array;
- int array_length;
- void expand();
- };
- limit CQueue::pop_f(){
- if (this->head != this->tail){
- limit result = this->array[this->head];
- this->array[this->head].left = 0;
- this->array[this->head].right = 0;
- this->head = ((this->head + 1) % this->array_length);
- return result;
- }
- };
- bool CQueue::isEmpty(){
- return this->tail == this->head;
- }
- void CQueue::expand(){
- limit *new_array = new limit[this->array_length * 2];
- int counter = 0;
- int i = this->head;
- while(counter != this->array_length){
- new_array[counter++] = this->array[i];
- i = ((i+1) % this->array_length);
- }
- this->tail = array_length;
- this->head = 0;
- this->array_length *= 2;
- delete[] this->array;
- this->array = new_array;
- }
- void CQueue::push_b(limit data){
- this->array[tail] = data;
- this->tail = ((this->tail + 1) % this->array_length);
- if ( this->tail == this->head ){
- expand();
- }
- };
- void insertionSort(int* a, int left, int right) {
- if (right - left < 2){
- return;
- } else {
- for(int i = left+1; i <= right; i++ ) {
- for(int j = i-1; j >= left && a[j] > a[j+1];j--) {
- swap(a[j], a[j+1]);
- }
- }
- }
- }
- int partition(int* arr, int left, int right, int piv) {
- int pivotValue = arr[piv];
- swap(arr[piv],arr[right]);
- for (int i = left; i < right; i++){
- if (arr[i] < pivotValue){
- swap (arr[piv],arr[left]);
- left++;
- }
- }
- swap(arr[left],arr[right]);
- return left;
- }
- void ModQuickSort(int* arr, int n) {
- CQueue range(100000);
- int left = 0;
- int right = n - 1;
- int piv = 0;
- bool flag = true;
- while (flag){
- while(true) {
- piv = left + rand() % (right - left);
- if( right - left < 11 ) {
- insertionSort(arr, left, right);
- break;
- }
- piv = partition(arr, left, right, piv);
- limit buf;
- buf.left = piv+1;
- buf.right= right;
- range.push_b(buf);
- right = piv;
- };
- while((right != n-1) && (right - left < 11)) {
- limit buf = range.pop_f();
- left = buf.left;
- right = buf.right;
- if( right - left < 11 ) {
- insertionSort(arr, left, right);
- }
- }
- if (range.isEmpty() || right-left < 11){
- flag = false;
- }
- } ;
- }
- int main() {
- int* arr = new int[25000000];
- int n = 0;
- while(true) {
- if (scanf("%d", &arr[n]) == 1){
- n++;
- } else {
- break;
- }
- }
- ModQuickSort(arr, n);
- for( int i = 9; i < n; i += 10 ) {
- cout << arr[i];
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement