Insertion + sort dynamic array

This is a discussion on Insertion + sort dynamic array within the C++ Programming forums, part of the General Programming Boards category; I wrote this code to do insertion and sort, but I encounter segmentaion fault error when running it. I think ...

  1. #1
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    452

    Insertion + sort dynamic array

    I wrote this code to do insertion and sort, but I encounter segmentaion fault error when running it. I think i didn't use 'new' correctly. Would someone help me fix this?

    Code:
    // Header file for class
    #ifndef INSERTION_SORT_H
    #define INSERTION_SORT_H
    
    class Insert_sort
    {
     private:
      int n; // Dimension of the array;
      int * arr; // Dynamic array with size n
     public:
      Insert_sort();
      Insert_sort(int size, int p[]);
      ~Insert_sort();
      void sort();
      void show();
    };
    
    
    #endif
    Code:
    #include <iostream>
    #include "insertion_sort.h"
    using std::cout;
    
    
    // Constructor + Destructor
    Insert_sort::Insert_sort()
    {
      cout<< "Please use Insert_Sort(int size, int * p])\n";
      cout<< "n is set to 0 and arr is set to NULL";
      arr = 0;
      n = 0;
    }
    Insert_sort::Insert_sort(int size, int p[])
    {
      n = size;
      arr = new int[n];
      for (int i = 0 ; i < n ; i++)
        {
          arr[ i ] = p [ i ];
        }
    }
    Insert_sort::~Insert_sort()
    {
      delete [] arr;
    }
    
    // Methods
    void Insert_sort::sort()
    {
      int key;
      int i,j;
      for (j = 1 ; j<n ; j++)
        {
          key = arr[i];
          i = j-1;
          while(i>-1 & arr[i]>key)
    	{
    	  arr[i+1] = arr[i];
    	  i = i-1;
    	}
          arr[i+1] =key;
        }
    }
    void Insert_sort::show()
    {
      for ( int i = 0; i<n; i++)
        cout << arr[i];
    }
    Code:
    // implementation file
    
    #include <iostream>
    #include "insertion_sort.h"
    using namespace std;
    
    
    int main()
    {
      int p[] = {9,100,0,3,4};
      Insert_sort A( 5 , p);
      A.show();
      A.sort();
      A.show();
    
      return 0;
    }

  2. #2
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    if your using gcc add the -g flag so you can debug using GDB

    ex:

    Code:
    g++ d_arr.cpp -g -o d_arr
    gdb d_arr
    once in gdb, type r to run your program, it will tell you the line number where your seg fault happens

  3. #3
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    452
    Thanks rodrigorules,
    I found the problem by using the gdb. It's in the sort() method. I used the wrong index letter. That was such as stupid mistake, but so difficult to find out.

  4. #4
    Registered User
    Join Date
    Dec 2010
    Posts
    8

    hi!

    i try this code in visual studio 2010 win32 console application
    and this is error pls help me.Sorry for my badly english
    cannot open source file "insertion_sort.h"
    cannot open include file "insertion_sort.h": No such file or directory

  5. #5
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    Yuo should create a new file insertion_sort.h with the following bit of code

    Code:
    // Header file for class
    #ifndef INSERTION_SORT_H
    #define INSERTION_SORT_H
    
    class Insert_sort
    {
     private:
      int n; // Dimension of the array;
      int * arr; // Dynamic array with size n
     public:
      Insert_sort();
      Insert_sort(int size, int p[]);
      ~Insert_sort();
      void sort();
      void show();
    };
    
    
    #endif
    ssharish
    Life is like riding a bicycle. To keep your balance you must keep moving - Einstein

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,506
    > cannot open include file "insertion_sort.h": No such file or directory
    Did you save the first snippet as insertion_sort.h ?
    Did you save the second snippet as insertion_sort.cpp ?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Dec 2010
    Posts
    8
    Quote Originally Posted by Salem View Post
    > cannot open include file "insertion_sort.h": No such file or directory
    Did you save the first snippet as insertion_sort.h ?
    Did you save the second snippet as insertion_sort.cpp ?
    thanks
    i find it.İt is "insert_sort.h".I make a stupid mistake.
    Now there is no error but still it doesn't sorting the array.
    Last edited by targetz0ne; 12-05-2010 at 08:57 AM.

  8. #8
    Registered User
    Join Date
    Dec 2010
    Posts
    8
    i cant show my code where is the code tags

  9. #9
    Registered User
    Join Date
    Dec 2010
    Posts
    8
    //its my inserttion sort.there is no error but i cant point the sorting list in the main.
    //A.sort(); // is it true?
    [
    Code:
    void Insert_sort::sort()
    {
      int key,i,k;
      for(i=1;i<n;i++)
      {
    	  key=arr[i];
    	  for(k=i-1;k>=0 && key<=arr[k];k--)
    	  {
    		  arr[k+1]=arr[k];
    		  arr[k+1]=key;
    	  }
      }
    }
    ]

  10. #10
    Registered User
    Join Date
    Dec 2010
    Posts
    8
    //its full of my code it doesnt sorting the numbers;
    //.h
    Code:
    #pragma once
    #ifndef INSERTION_SORT_H
    #define INSERTION_SORT_H
    
    class Insert_sort
    {
    private:
    	int n; // Dimension of the array;
      int * arr; // Dynamic array with size n
    
    public:
    	Insert_sort();
    	Insert_sort(int size, int p[]);
    	~Insert_sort();
    	void sort();
    	void show();
    };
    
    #endif
    
    //.cpp
    #include "StdAfx.h"
    #include "insert_sort.h"
    #include<iostream>
    using namespace std;
    
    Insert_sort::Insert_sort()
    {
      cout<< "Please use Insert_Sort(int size, int * p])\n";
      cout<< "n is set to 0 and arr is set to NULL";
      arr = 0;
      n = 0;
    }
    
    
    Insert_sort::Insert_sort(int size, int p[])
    {
      n = size;
      arr = new int[n];
      for (int i = 0 ; i < n ; i++)
        {
          arr[ i ] = p [ i ];
        }
    }
    Insert_sort::~Insert_sort()
    {
      delete [] arr;
    }
    // Methods
    void Insert_sort::sort()
    {
      int key,i,k;
      for(i=1;i<n;i++)
      {
    	  key=arr[i];
    	  for(k=i-1;k>=0 && key<=arr[k];k--)
    	  {
    		  arr[k+1]=arr[k];
    		  arr[k+1]=key;
    	  }
      }
    }
    void Insert_sort::show()
    {
      for ( int i = 0; i<n; i++)
        cout << arr[i] <<",";
    }
    
    //.cpp.cpp
    #include "stdafx.h"
    #include <iostream>
    #include "insert_sort.h"
    #include<conio.h>
    using namespace std;
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int p[] = {9,2,7,3,4};
    	
    
    	Insert_sort A( 5 , p);
        A.show();
    	printf("\n");
        A.sort();
    	printf("\n");
        A.show();
    	getch();
    
    	return 0;
    }

  11. #11
    Registered User
    Join Date
    Dec 2010
    Posts
    8
    and it is the console
    9,2,7,3,4,

    9,2,7,3,4

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,506
    arr[k+1]=arr[k];
    arr[k+1]=key;
    One of these assignments is redundant.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    Registered User
    Join Date
    Dec 2010
    Posts
    8
    thank you dude

  14. #14
    Registered User
    Join Date
    Dec 2010
    Posts
    8
    insertion sort is working now i'm trying merge sort its my code. it is working but it doesnt sorting.
    Code:
    //merge_sort.h
    #pragma once
    #ifndef MERGE_SORT_H
    #define MERGE_SORT_H
    
    class merge_sort
    {
    public:
    	private:
    	int n; // Dimension of the array;
        int * arr; // Dynamic array with size n
    
    public:
    	merge_sort(int size, int p[]);
    	~merge_sort();
    	void sort();
    	void show();
    };
    
    #endif
    
    //mergesort.cpp
    
    #include "StdAfx.h"
    #include "merge_sort.h"
    #include<iostream>
    using namespace std;
    
    merge_sort::merge_sort(int size, int p[])
    {
      n = size;  
      arr = new int[n];
      for (int i = 0 ; i < n ; i++)
        {
          arr[ i ] = p [ i ];
        }
    }
    merge_sort::~merge_sort()
    {
      delete [] arr;
    }
    // Methods
    void merge_sort::sort()
    {
       int *t, *q, *buf;
       int   left, len, count1, count2, source1, source2, dest;
    
       if (n <= 1)
          return;
       buf = q = (int *) malloc(n * sizeof(int));
       if (buf == NULL) {
          printf("not enough memory!");
          exit(EXIT_FAILURE);
       }
       len = 1;
    
       do {
          left = n;
          source1 = dest = 0; source2 = len;
          do {
             left -= count1 = (left >= len) ? len : left;
             left -= count2 = (left >= len) ? len : left;
             while (count1 > 0 && count2 > 0) {
                if (arr[source1] < arr[source2]) {
                   q[dest++] = arr[source1++];
                   count1--;
                }
                else {
                   q[dest++] = arr[source2++];
                   count2--;
                }
             }
             while (--count1 >= 0)
                q[dest++] = arr[source1++];
             while (--count2 >= 0)
                q[dest++] = arr[source2++];
             source1 += len; source2 += len;
          } while (left > 0);
          t = arr;
          arr = q;
          q = t;
          len *= 2;
       } while (len < n);
       if (arr == buf)
          while (--n >= 0)
             q[n] = arr[n];
       free(buf);
    
    }
    void merge_sort::show()
    {
      for ( int i = 0; i<n; i++)
        cout << arr[i] <<" ";
    }
    
    //main
    
    #include "stdafx.h"
    #include <iostream>
    #include <time.h>
    #include "insert_sort.h"
    #include <conio.h>
    #include "merge_sort.h"
    using namespace std;
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	srand(time(NULL));
    	int length;
    	printf("lenth of array: ");
    	scanf("%d",&length);
    	int *aptr=new int [length];
    	int *iptr,*mptr;
    	iptr=aptr;
    
    	for(int i=0;i<boyut;i++)
    	{
    		*iptr=rand()%100;
    		iptr++;
    	}
    	iptr=aptr;
    	merge_sort A(length,iptr);
    	printf("\nRandom \n");
        A.show();	
    	printf("\n\nMerge sort \n");
        A.sort();
    	printf("\n");
        A.show();
    	printf("\n");
    Last edited by targetz0ne; 12-06-2010 at 12:06 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Replies: 5
    Last Post: 08-02-2008, 06:23 AM
  3. Insertion Sort on Array
    By swanley007 in forum C++ Programming
    Replies: 0
    Last Post: 10-01-2005, 06:25 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21