Nie działający mergesort

0

Witam, prosiłbym o pomoc z tym programem. Cały kod wydaje się być poprawnie zapisany, natomiast ani w Devie, ani w Visualu nie udaje mi się go skompilować. Visual wskazuje na zatrzymanie w momencie rozpoczynanie procedury merge_sort.

#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <time.h>
#include <cmath>
using namespace std;

void merge(int tab[], int l, int srodek, int r)
{
	int *tab_pom = new int[r - l]; // utworzenie dynamicznej tablicy pomocniczej
	int i = l;
	int j = srodek + 1;
	int k = 0; // indeksy tablicy pomocniczej

	while (i <= srodek && j <= r) // przepisujemy mniejszy element, dopóki któryś z podzielonych podzbiorów się nie skończy
	{
		if (tab[j] < tab[i])
		{
			tab_pom[k] = tab[j];
			j++;
		}

		else
		{
			tab_pom[k] = tab[i];
			i++;
		}

		k++;
	}

	if (i <= srodek) // jeśli zostały nam tylko elementy lewego podzbioru
	{
		while (i <= srodek)
		{
			tab_pom[k] = tab[i]; // po prostu przepisujemy elementy
			i++;
			k++;
		}
	}

	else
	{
		while (j <= r) // jeśli zostały nam elementy prawej podzbioru
		{
			tab_pom[k] = tab[j]; // przepisujemy elementy
			j++;
			k++;
		}
	}

	for (i = 0; i <= r - l; i++)
		tab[l + i] = tab_pom[i]; // przepisujemy elementy do tablicy głównej
	delete tab_pom;
}

void merge_sort(int tab[], int l, int r)
{
	int srodek;

	if (l != r)
	{
		srodek = (l + r) / 2;

		merge_sort(tab, l, r);
		merge_sort(tab, srodek + 1, r);
		merge(tab, l, srodek, r);
	}
}


int main()
{
	const int d = 10;
	int tab2[d] = { 23, 45, 23, 11, 24, 65, 931, 11, 2, 40 };

	cout << "PRZED SORTOWANIEM:" << endl << endl;
	for (int i = 0; i < d; i++) // wypisanie posortowanej tablicy
		cout << "tab[" << i << "] = " << tab2[i] << endl;
	cout << endl;

	merge_sort(tab2, 0, 9);

	cout << "PO SORTOWANIU:" << endl << endl;
	for (int i = 0; i < d; i++) // wypisanie posortowanej tablicy
		cout << "tab[" << i << "] = " << tab2[i] << endl;

	system("pause");
}
2

Udaje Ci się go skompilować**!**
To co otrzymujesz to błąd wykonania.
Gdzieś próbujesz maziać po nie swojej pamięci.
Niestety nie odpalę za Ciebie valgrinda.

0

Fakt, pojawiają się jakieś zapisy szesnastkowe wskazujące właśnie na pamięć, ale cóż to mogłoby oznaczać? Dodam, że program działał, zanim nie zamieniłem deklarowanych nazw (np "start" na "l", albo "koniec" na "r").

0

To przywróć swój program do stanu, w którym nazwy nie będą z czapy. Gdzieś się w tym wszystkim pogubiłeś.
Oczywiście jeśli nie trzymałeś tego w systemie kontroli wersji to wywal całość i pisz od nowa.

0
  1. nie używaj l jako zmiennej! Bo źle się czyta
  2. nie
  delete tab_pom;

a

  delete []tab_pom;
  1. nie chce mi się analizowac wszystkich przypadków, ale czy jest pewność, że k >= r - 1 (funkcja merge)
  2. tu na pewno wyjeżdzasz o 1 element za daleko:
     for (i = 0; i <= r - l; i++)
        tab[l + i] = tab_pom[i]; 

PS.: OT: do autora kodu forum, czy w edytorze ctrl + v mogłoby nie być przeciążane, bo wkurza ździebko!

1 użytkowników online, w tym zalogowanych: 0, gości: 1