C ++: sorting the initial part of the array in ascending order, and the other part in descending order

Question

I am new to C ++ and I am trying to do this :

I have an array of N elements. The user should be able to enter all elements of the array and the number K. After that, I need to sort the array so that the first part (elements 1 to K ) is sorted in ascending mode, and the second part (elements K to N ) are sorted in descending mode.

The sorting function is implemented by me. I can use qsort from cstdlib , but it is not so interesting.

I encoded an array to sort, but I can't figure out how to sort an array in two parts.

 #include <iostream> #include <string> void print_array(int[], int); void qsort(int[], int, int); int main() { int array_length; int *array, k; std::cout << "Write array length: "; std::cin >> array_length; array = new int[array_length]; for (int i = 0; i < array_length; i++) { std::cout << "Write " << i + 1 << " element: "; std::cin >> array[i]; } print_array(array, array_length); do { std::cout << "Write k: "; std::cin >> k; } while (k >= array_length); qsort(array, 0, k); print_array(array, array_length); } void print_array(int* array, int length) { for (int i = 0; i < length; i++) { std::cout << array[i] << "\n"; } } void qsort(int arr[], int fst, int last) { int i, j, pivot, tmp; if (fst < last) { pivot = fst; i = fst; j = last; while (i < j) { while (arr[i] <= arr[pivot] && i < last) i++; while (arr[j] > arr[pivot]) j--; if (i < j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } tmp = arr[pivot]; arr[pivot] = arr[j]; arr[j] = tmp; qsort(arr, fst, j - 1); qsort(arr, j + 1, last); } } 

Answer 1

You sort one half with:

 qsort(array, 0, k); 

and similarly you need the other half:

 qsort(array+k, 0, array_length-k); 

Now the problem is that both parts will be in ascending order. Therefore, you need to specify qsort() to sort one half in ascending order and the other half in descending order. Pass another flag to qsort() to change the swap order. So you can specify bool to specify it:

 void qsort(int arr[], int fst, int last, bool pass) { .... if (pass && i < j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } if(!pass && i > j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } ... qsort(arr, fst, j - 1, pass); qsort(arr, j + 1, last, pass); 

}

And when you call it, you can pass true and false to "switch" the swap order:

  qsort(array, 0, k, true); qsort(array+k, 0, array_length-k, false); 

Change the qsort() prototype accordingly.

Answer 2

You just need to replace the following lines to get the data in descending order:

  //while (arr[i] <= arr[pivot] && i < last) while (arr[i] >= arr[pivot] && i < last) i++; //while (arr[j] > arr[pivot]) while (arr[j] < arr[pivot]) 

Answer 3

From what I see, your array contains purely integer values ​​that are primitive in nature and can be sorted using the C ++ sort method.

 #include <algorithm> // this is to access c++ std::sort method ... std::sort(array + first, array + last) // input range of index of array to be sorted ... 

That should take care of this.

Another point to pay attention to is ascending sorting by default. This way you can play using the CompareTo method and all that. But my favorite trick is to multiply -1 by all the values ​​in the array and sort it and multiply -1 back, resulting in an array sorted in descending order.

Answer 4

C ++ way of writing algorithms for arrays and other data sequences through iterators :

 template <typename Iter> void qsort(Iter begin, Iter end) { auto pivot = begin + (end - begin) / 2; std::nth_element(begin, pivot, end); qsort(begin, pivot); qsort(pivot + 1, end); } 

Combine this with reverse_iterator and we get your desired behavior:

 auto lhBegin = array; auto lhEnd = array + K; qsort(lhBegin, lhEnd); // [ 0, 1, ..., K-2, K-1 ] is now in sorted order auto rhBegin = std::make_reverse_iterator(array + N); auto rhEnd = std::make_reverse_iterator(array + K); qsort(rhBegin, rhEnd); // [ N-1, N-2, ..., K+1, K ] is now in sorted order