Sort array using Recursion segmentation fault core dumped

Question

I have been using recursion lately and tried to sort array using the same, though using recursion to understand it well.

I have declared all the neccesary functions here

#include<iostream>
#include<stdlib.h>
#include<vector>

void insert(std::vector<int>&,int);
void sort(std::vector<int>&);
void getArray(std::vector<int>&, int, char **);
void display(const std::vector<int>&);

This is my main function

int main(int argc, char **argv){
  std::vector<int> array;
  getArray(array,argc,argv);
  sort(array);
  display(array);

  return 0;
}

This is my Sort recusrion function.

void sort(std::vector<int>& array){
  if(array.size()==1)
    return;
  std::cout<<array.at(array.size()-1);
  int temp = array.at(array.size()-1);
  std::cout<<temp;
  array.pop_back();
  sort(array);
  insert(array,temp);
}

Insert function

void insert(std::vector<int>& array,int temp)
{
  if ((array.size()==0)||array.at(array.size()-1)<=temp)
    array.push_back(temp);
  int value = array.at(array.size()-1);
  array.pop_back();
  insert(array,temp);
  array.push_back(value);
}

input array function

 void getArray(std::vector<int>& array, int argc, char **argv){
   for (int i = 1;i<argc;i++){
     array.push_back(atoi(argv[i]));
   }
 }

Print array function

  void display(const std::vector<int>& array){
    for (auto i : array){
      std::cout<<i<<std::endl;
     }
  }

Basically I used logic of popping last element of array to sort recursively and adding popped element after sorting at end using insert and sort function.

But I am getting segmentation fault for running

  $ g++ -std=c++14 -o main main.cpp
  $ ./main 0 7 2 5 1 9
  output : Segmentation fault (core dumped)

while if I input

  $ ./main 5 
  output : 5

i.e for single input I get base case returned but not for for array.

If you run the program in a debugger (for example, "gdb --args ./main 0 7 2 5 1 9" in the shell, then "run" in gdb), you can examine the stack trace ("bt" in gdb) when it stops. That will show you where the problem is. — Buster
– Buster, Commented Aug 16, 2020 at 9:17

bruno · Accepted Answer · 2020-08-16 08:52:25Z

in insert when ((array.size()==0)||array.at(array.size()-1)<=temp) is true you need to only array.push_back(temp) and not to do the rest of the function else you recurse without ending and have a stack overflow

so for instance :

void insert(std::vector<int>& array,int temp)
{
  if ((array.size()==0)||array.at(array.size()-1)<=temp) {
    array.push_back(temp);
  }
  else {
    int value = array.at(array.size()-1);

    array.pop_back();
    insert(array,temp);
    array.push_back(value);
  }
}

After that (removing the debug output in sort you cannot see because there is no std::cout<<std::endl), compilation and execution :

pi@raspberrypi:/tmp $ g++ -Wall s.cc
pi@raspberrypi:/tmp $ ./a.out 0 7 2 5 1 9
0
1
2
5
7
9
pi@raspberrypi:/tmp $

Out of that

do not use atoi, atoi("aze") silently returns 0.
your way to sort is very expensive (out of the fact std::sort already exists)
there is nothing specific to C++14 nor even C++11, the tag / way to compile is useless

Collectives™ on Stack Overflow

Sort array using Recursion segmentation fault core dumped

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related