сортировка строк с сортировкой в ​​кучу | C ++ - PullRequest
Новая
       39

сортировка строк с сортировкой в ​​кучу | C ++

0 голосов
/ 05 августа 2020

Я новичок в C ++. У меня проблема с кодом. Я хочу отсортировать массив строк. с сортировкой выбора он работает, но с сортировкой кучи есть проблема, что ничего не распечатывается (у меня также есть эта проблема с сортировкой слияния) Я думаю, что проблема в strcmp (), но IDK, как это исправить 

#include<iostream>
#include<cstring>
#define MAX_LEN 100

void heapify(char arr[][MAX_LEN], int size, int i);
void heapSort(char arr[][MAX_LEN], int size);
// MAIN
int main (){
  char arr[][MAX_LEN] = {"V", "Gorz", "Arta", "BM", "Monster"};
  int size = sizeof(arr) / sizeof(arr[0]);
  heapSort(arr, size);
  // printing array
  for(int i = 0; i < 0; i++){
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
  return 0;
}
//==============================================================
// heapify function: check left and right children and also the parent
// and heapify it
void heapify(char arr[][MAX_LEN], int size, int i){
  
  int largest, l, r;
  largest = i;
  l = 2 * i;
  r = 2 * i + 1;
  //left child
  if(l < size){
    if(std::strcmp(arr[l], arr[largest]) > 0)
        largest = l;
  //right child
  }
  if(r < size){
    if(std::strcmp(arr[r], arr[largest]) > 0)
        largest = r;
  //if largest != i
  }
  if(largest != i){
    std::strcpy(arr[largest], arr[i]);
    heapify(arr, size, largest);
  }
} 
//==============================================================
// main heap sort function uses heapify function and then remove element
// one by one and re arrages it and heapify again
void heapSort(char arr[][MAX_LEN], int size){
  for(int i = size / 2 - 1; i >= 0; i--){
    heapify(arr, size, i);
  }
  for(int i = size - 1; i > 0; i--){
    std::strcpy(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}

1 Ответ

1 голос
/ 05 августа 2020

Несколько проблем в вашем коде.

Начинается с heapify():

Вы вычисляете левую и правую часть элемента кучи как- 

  l = 2 * i;
  r = 2 * i + 1;

Предположим что i это 0. В этом случае l будет отображаться как 0, что неверно. Это должно быть 

  l = 2 * i + 1;
  r = 2 * i + 2;

Здесь 

  if(largest != i){
    std::strcpy(arr[largest], arr[i]);

вы копируете arr[i] в arr[largest]. Из-за этого строка с индексом largest массива arr будет перезаписана строкой с i местоположением массива arr. Вместо этого вы должны поменять их местами: 

  if(largest != i){
    std::swap(arr[largest], arr[i]);
    ^^^^^^^^^

Теперь проблемы в heapSort():

Здесь 

  for(int i = size - 1; i > 0; i--){
    std::strcpy(arr[0], arr[i]);

вы делаете ту же ошибку при копировании arr[i] на arr[0]. Вместо этого вы должны поменять их местами: 

  for(int i = size - 1; i > 0; i--){
    std::swap(arr[0], arr[i]);
    ^^^^^^^^^

Теперь перейдите к main():

Проверьте это 

  // printing array
  for(int i = 0; i < 0; i++){
                 ^^^^^

Это l oop тело никогда не будет выполнить из-за ошибки в условии l oop (i < 0). Условие l oop должно быть i < size: 

for(int i = 0; i < size; i++){
               ^^^^^^^^
...