C++: Sortowanie początkową część tablicy w kolejności rosnącej i drugiej strony w kolejności

Question

malejąco Jestem nowym do C++ i próbuję zrobić this:

Mam tablicę N elementów. Użytkownik powinien mieć możliwość wprowadzania wszystkich elementów tablicy i numeru K. Potem trzeba sortować szereg tak, że pierwsza część (elementy do K) są sortowane w trybie wstępującej, a druga część (elementy K do N) są sortowane w trybie malejącym.

Funkcja sortowania jest realizowana przeze mnie. Mogę użyć qsort z cstdlib, ale nie jest to takie interesujące.

Mam kodowanie do sortowania tablicy, ale nie mogę zrozumieć, jak posortować tablicę na dwie części.

#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

Jesteś sortowania jedną połowę z:

qsort(array, 0, k); 

i podobnie, trzeba sortowanie drugiej połówki:

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

Problem polega na tym, że obie części będą w porządku rosnącym. Potrzebujesz więc sposobu, aby powiedzieć qsort(), aby posortować połowę w porządku rosnącym, a drugą połowę w porządku malejącym. Przekaż inną flagę do qsort(), aby zmienić kolejność wymiany. Więc można Pas do bool aby go wskazać:

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

}

A kiedy nazwać można przekazać true i false do "Przełącznik" kolejność wymiany:

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

zmienić prototyp z qsort() odpowiednio.

Answer 2

Po prostu trzeba wymienić następujące linie, w celu uzyskania danych w kolejności malejącej:

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

Z tego co widzę, twoja tablica zawiera wyłącznie liczby całkowite, które mają charakter pierwotny i mogą być sortowane przy użyciu metody sortowania C++.

To powinno się tym zająć.

Inną kwestią, o której należy pamiętać, jest domyślne sortowanie w porządku rosnącym. Możesz więc bawić się metodą CompareTo i tak dalej. Ale moja ulubiona sztuczka polega na pomnożeniu -1 do wszystkich wartości w tablicy i posortowaniu go i pomnożeniu -1 wstecz, kończąc na tablicy posortowanej w porządku malejącym.

Answer 4

C++ sposób algorytmów pisanie dla tablic i innych sekwencji danych jest poprzez 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); 
} 

Łącząc to z reverse_iterator i uzyskać pożądany zachowanie:

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