sorting strings with heap sort | C++

Question

I'm new to c++ I have a problem with my code I want to sort an array of string. with selection sort, it works but with heap sort, there is a problem that nothing gets printed out (i also have this problem with merge sort) I think the problem is strcmp(), but IDK how to fix it

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

Time to learn how to *debug* your programs. With a *debugger* you can step through your code statement by statement (and step into your function calls), while monitoring variables and their values. — Some programmer dude, Aug 05 '20 at 10:30
You tagged the question with C++ but your code looks like C with iostream. Is there a reason you didn't use STL? — Thomas Sablik, Aug 05 '20 at 10:32
You may want to read these two links: 1. [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) 2. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) — Andreas Wenzel, Aug 05 '20 at 10:40

H.S. · Accepted Answer · 2020-08-05T11:11:38.747

Several problems in your code.

Starts with heapify():

You are calculating the left and right of a heap element as-

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

Assume that i is 0. In that case, it will give l as 0 which is incorrect. It should be

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

Here,

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

you are copying arr[i] to arr[largest]. Due to this, the string at largest index of array arr will be overwritten by string at i location of array arr. Instead, you should swap them:

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

Now, problems in heapSort():

Here,

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

you are doing same mistake of copying arr[i] to arr[0]. Instead, you should swap them:

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

Now, come to main():

Check this

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

This loop body never going to execute due to the mistake in the loop condition (i < 0). The loop condition should be i < size:

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

Nice work, if only the OP knew how to use a debugger, they could have found all these problems for themselves. But for some reason debugger use isn't taught to newbies. — john, Aug 05 '20 at 11:26

sorting strings with heap sort | C++

1 Answers1