C++: Sắp xếp các phần ban đầu của một mảng tăng dần và phần khác nhằm

Question

giảm dần Tôi mới đến C++ và tôi đang cố gắng để làm this:

Tôi có một mảng của N yếu tố. Người dùng có thể nhập tất cả các phần tử của một mảng và một số K. Sau đó tôi phải sắp xếp các mảng như vậy mà phần đầu tiên (yếu tố để K) được sắp xếp trong chế độ tăng dần và phần thứ hai (yếu tố K để N) được sắp xếp trong chế độ giảm dần.

Chức năng sắp xếp được thực hiện bởi chính tôi. Tôi có thể sử dụng qsort từ cstdlib, nhưng nó không thú vị lắm.

Tôi đã mã hóa để sắp xếp một mảng, nhưng tôi không thể hiểu cách sắp xếp một mảng theo hai phần.

#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

Bạn sắp xếp một nửa với:

qsort(array, 0, k); 

và tương tự, bạn cần sắp xếp một nửa khác:

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

Bây giờ, vấn đề là cả hai phần sẽ theo thứ tự tăng dần. Vì vậy, bạn cần một cách để báo cho qsort() sắp xếp một nửa theo thứ tự tăng dần và một nửa khác theo thứ tự giảm dần. Chuyển một cờ khác đến qsort() để thay đổi thứ tự trao đổi. Vì vậy, bạn có thể pas một bool để chỉ ra nó:

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); 

}

Và khi bạn gọi nó, bạn có thể vượt qua true và false để "chuyển đổi" trật tự hoán đổi:

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

Thay đổi nguyên mẫu của qsort() cho phù hợp.

Answer 2

Bạn chỉ cần thay thế dòng sau, để có được dữ liệu theo thứ tự giảm dần:

 //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

Từ những gì tôi thấy, mảng của bạn chứa các giá trị nguyên thuần túy nguyên thủy và có thể được sắp xếp bằng cách sử dụng phương pháp sắp xếp C++.

#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 

... 

Điều này sẽ giải quyết vấn đề này.

Một điểm cần lưu ý khác là loại sắp xếp theo thứ tự tăng dần này theo mặc định. Vì vậy, bạn có thể chơi xung quanh với phương pháp CompareTo và tất cả những điều đó. Nhưng mẹo ưa thích của tôi là nhân -1 với tất cả các giá trị trong mảng và sắp xếp nó và nhân -1 trở lại, kết thúc với mảng được sắp xếp theo thứ tự giảm dần.

Answer 4

C++ cách của thuật toán bằng văn bản cho các mảng và chuỗi khác của dữ liệu là thông qua 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); 
} 

Kết hợp với reverse_iterator và chúng tôi nhận hành vi mong muốn của bạn:

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