SenselessCoder - 1 year ago
457 0

No description

C

# WEWEQEQE

``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LIM_LOW 10
#define LIM_HIGH 2000

#define REVERSE_POS 0
#define SORTED_POS 1

void bound(int* x, int l, int h) {
if(*x > h)
*x = h;
if(*x < l)
*x =  l;
}

int** cut(int* arr, int N, int k) {
int** res = (int **) malloc(sizeof(int *) * 2);
res[REVERSE_POS] = (int *) malloc(sizeof(int) * (N - k));
res[SORTED_POS] = (int *) malloc(sizeof(int) * k);
// copy sorted
for(int i = 0; i < k; ++i)
res[SORTED_POS][i] = arr[i];
// reverse copy
for(int i = 0; i < N - k; ++i) // if even we have overlap, so prevent it
res[REVERSE_POS][i] = arr[N - i - 1];
return res;
}

void dostuff(int* arr, int N) {
int lower = 2, higher = N - 2;
bound(&lower, 2, N);
bound(&higher, 1, N - 2);
int k = (rand() % (higher - lower) + lower);
printf("Cutting at %d\n", k);
int** partitioned = cut(arr, N, k);

// edit our array
for(int i = 0; i < N - k; ++i)
arr[i] = partitioned[REVERSE_POS][i];
for(int i = 0; i <= k; ++i)
arr[N - k + i] = partitioned[SORTED_POS][i];
for(int i = 0; i < 2; ++i)
free(partitioned[i]);
free(partitioned);
}

void show_arr(int* arr, int N) {
for(int i = 0; i < N; ++i)
printf("%d ", arr[i]);
}

void find_elem(int* arr, int N, int rank) {
// find negative difference position
int low, high;
for(low = N - 2, high = N - 1; high < N && arr[high] - arr[low] >= 0; --low, --high);
// high holds the beginning of sorted area, low holds end of reverse area
printf("%d %d\n", low, high);
int count = 0, temp = rank, pos = high;
while(temp) {
if(high < N)
pos = high++;
else if(low >= 0)
pos = low--;
++count;
--temp;
}
printf("Element on rank %d is: %d", rank, arr[pos]);
}

int main() {
srand(time(0));
int N, *arr;
printf("How many elements [%d .. %d]: ", LIM_LOW, LIM_HIGH);
scanf("%d", &N);
printf("%d Enter array elements...\n", N);
bound(&N, LIM_LOW, LIM_HIGH);
arr = (int *) malloc(sizeof(int) * N);
for(int i = 0; i < N; ++i) {
printf("a_%d: ", i);
scanf("%d", &arr[i]);
}
dostuff(arr, N);
show_arr(arr, N);
int r;
printf("\nEnter rank: ");
scanf("%d", &r);
bound(&r, 1, N);
find_elem(arr, N, r);
free(arr);
return 0;
}``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download