CODEWITHSUNDEEP
c++
Sam Gunner
Sam Gunner

Reputation: 13

My program freezes at the end, after it has finished

I've been working on a class for an insertion sort thing that I'm playing around with. However, when I run my program, it seems to work just fine for the most part (gets to return 0; in main and then freezes). I don't know why or how it's freezing, and it's gotten me quite confused.

The only method that is called from the insertionSort object is sort, if you don't count generateNums.

Main.cpp:

#include "stdafx.h"
#include "insertionSort.h"
#include <iostream>


int main()
{
    int* gotNums;
    const int INT_LENGTH = 100;

    //Create new insertionSort object
    insertionSort insSort(INT_LENGTH); //Length: 100
    std::cout << "hey";

    return 0;
}

insertionSort.h:

#pragma once
class insertionSort
{
private:
    int* _nums; //Sorted and unsorted nums
    int _sortedBegins; //Point at which sorted items begin. This minus one is the first unsorted item
    int _length;
    void shiftUnsorted();
public:
    insertionSort(int length);
    int* getNums();
    void sortNums();
    void generateNums();
};

insertionSort.cpp

#include "stdafx.h"
#include "insertionSort.h"
#include <random>
#include <iostream>

//Constructor and destructors
insertionSort::insertionSort(int length)
{
    _nums = new int(length + 1); //+1 to accomodate empty space between sorted & unsorted.
    std::cout << "made arr ";
    _sortedBegins = length + 1;
    std::cout << "made sorted ";
    _length = length + 1;
    std::cout << "made len ";
    this->generateNums();
}


/* Custom functions */

//Populate array with new numbers
void insertionSort::generateNums() {
    for (int i = 0; i < _length - 1; i++) { //Don't fill the last array; it's an empty place for the sorted items.
        _nums[i] = rand() % 100 + 1; //generate number between 1 and 100
    }
    _nums[_length] = -1; //Create buffer
}

//The main part of it all - sort the array
void insertionSort::sortNums() {
    int currPos = _sortedBegins - 1; //Loop backwards through the unsorted items so that there is minimal shifting.
    int currInt;

    while (currPos > 0) {
        currInt = _nums[currPos];
        for (int i = _length; i > _sortedBegins; i++) {
            if (i < currInt) { //Time to shift the sorted to the left
                _nums[_sortedBegins - 1] = 0; //Shift buffer left
                for (int i2 = _sortedBegins + 1; i2 <= i; i2++) { //Shift main sorted content left
                    _nums[i2] = _nums[i2 + 1];
                }
                _nums[i] = currInt;
                break;
            }
        }
        currInt--;
    }
}

//Get nums from array
int* insertionSort::getNums() {
    return _nums;
}

//Shift unsorted items to the left to make way for new data in sorted. NOTE: does not assign new value to sortedBegins.
void insertionSort::shiftUnsorted() {
    for (int i = 0; i < _sortedBegins - 1; i++) {
        _nums[i] = _nums[i + 1];
    }
    _nums[_sortedBegins - 1] = 0;
    //And, it's hopefully shifted!
}

Anyone got an idea as to why this isn't working properly?

Thanks,

- Sam

Upvotes: 1

Views: 113

Answers (2)

Roland Illig
Roland Illig

Reputation: 41686

This code looks suspicious to me:

_nums = new int(length + 1);

I would have expected square brackets instead of round parentheses. Because like this, you are only creating a pointer to a single int that is initialized with the value 101. But instead you wanted to create an array of 101 ints and later fill it with values. So write this:

_nums = new int[length + 1];

Upvotes: 0

Barmar
Barmar

Reputation: 782407

Change:

_nums[_length] = -1; //Create buffer

to:

_nums[_length - 1] = -1; //Create buffer

Valid indexes for _nums are from 0 to length-1. Your code is writing outside the array, which causes undefined behavior.

The for loop in sortNums is also doesn't look right:

for (i = _length; i > _sortedBegins; i++) {

It makes no sense to start at _length, which is after the end of the array. And adding to it goes even farther out of the array. I haven't really analyzed the logic in that loop, so I'm not sure what the correct code is. But you need to start by making sure you stay inside the array.

But since your program doesn't currently call sortNums, it won't cause a problem now.

When shiftUnsorted does

_nums[_sortedBegins - 1] = 0;

you'll write outside the array if _sortedBegins is 0. You don't currently call this, either. When you add the call to it, make sure it can never be called when that's true, or add a check for this into the function.

Upvotes: 4

Related Questions