C++

Forum

 
MergeSort using pointers [NOT SOLVED YET]

giovanninokr (6)
Goodmorning Everybody!

Can I ask to help me with this code?
It's just an exercise about the pointers.
I'd like to do a MergeSort with sentinels and order the pointers, not the values!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
#include <iostream>
#include <limits>
using namespace std;

void
stampa (int *n)
{
  int i;
  for (i = 0; i < 10; i++)
    {
      cout << n[i] << " ";
    }
  cout << endl;
  return;
}
void
stampa2 (int** n)
{
  int i;
  for (i = 0; i < 10; i++)
    {
      cout << *n[i] << " ";
    }
  cout << endl;
  return;
}
void
merge (int** a, int p, int q, int r)
{
  int n1, n2;
  n1 = q - p + 1;
  n2 = r - q;
  int* L[n1];
  int* R[n2];

  for (int i = 0; i < n1; i++)
    L[i] = a[p + i];

  *L[n1] = numeric_limits < int >::max ();

  for (int j = 0; j < n2; j++)
    R[j] = a[q + j + 1];

  *R[n2] = *L[n1];
  int i = 0;
  int j = 0;
  for (int k=p; k<=r; k++)
    {
      if (*L[i] <= *R[j])
      a[k] = L[i++];
      else
      a[k] = R[j++];
    }
}
void
ordina_mergesort (int** a, int p, int r)
{
  int q=0;

  if (p < r)
    {
      q = (p + r) / 2;
      ordina_mergesort (a, p, q);
      ordina_mergesort (a, q+1, r);
      merge (a, p, q, r);

    }
}

int
main ()
{

  int scombinati[] = { 9, 1, 8, 2, 0, 3, 7, 4, 6, 5 };
  int **ordinati;

  ordinati = new int *[10];

  for(int i=0; i<10; i++)
   ordinati[i] = scombinati+i;

   ordina_mergesort(ordinati, 0, 9);

  cout << "Stampo i numeri scombinati: (9, 1, 8, 2, 0, 3, 7, 4, 6, 5)" << endl;
  stampa (scombinati);

  cout << "\nStampo i numeri ordinati: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)" << endl;
  stampa2 (ordinati);

  delete [] ordinati;
  return 0;
}


Thanks!
giovanninokr (6)
Is there anybody out there??? =)
giovanninokr (6)
=(
(up)
codewalker (394)
Do you have any specific question/problem here?
abhishekm71 (820)
What is the problem that you are facing?
giovanninokr (6)
OH THANKS!!!
:)

I have to do the ordering (It's just an example) but with the pointer.
I had 0 error and 0 warning but doesn't work.
The problem, I guess, is the function where I do the merge...
giovanninokr (6)
I tryed to do the same (TO ORDER AN ARRAY WITH POINTERS) with a QUICKSORT and it works properly!
Like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
#include <iostream>
using namespace std;


void
stampa (int *n)
{
  int i;
  for (i = 0; i < 10; i++)
    {
      cout << n[i] << " ";
    }
  cout << endl;
  return;
}

void
stampa2 (int * n[])
{
  int i;
  for (i = 0; i < 10; i++)
    {
      cout << *n[i] << " ";
    }
  cout << endl;
  return;
}



int unisci(int** input, int p, int r)
{
    int* pivot;

    pivot = input[r];

    while ( p < r )
    {
        while ( *input[p] < *pivot )
            p++;

        while ( *input[r] > *pivot )
            r--;

        if ( *input[p] == *input[r] )
            p++;
        else if ( p < r )
        {
            int *tmp = input[p];
            input[p] = input[r];
            input[r] = tmp;
        }
    }

    return r;
}

void ordina_quicksort(int** input, int p, int r)
{
    if ( p < r )
    {
        int j = unisci(input, p, r);
        ordina_quicksort(input, p, j-1);
        ordina_quicksort(input, j+1, r);
    }
}

int
main ()
{

  int scombinati[] = { 9, 1, 8, 2, 0, 3, 7, 4, 6, 5 };
  int **ordinati;

  ordinati = new int *[10];

  for(int i=9; i>=0; i--)
   ordinati[i] = (scombinati+9)-i;

  cout << "Stampo i numeri scombinati al contrario : (5, 6, 4, 7, 3, 0, 2, 8, 1, 9)" << endl;
  stampa2 (ordinati); // li metto per gioco al contrario

  ordina_quicksort(ordinati, 0, 9);

  cout << "Stampo i numeri scombinati dati: (9, 1, 8, 2, 0, 3, 7, 4, 6, 5)" << endl;
  stampa (scombinati);

  cout << "\nStampo i numeri ordinati: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)" << endl;
  stampa2 (ordinati);

  delete [] ordinati;
  return 0;
}


But Not the MERGESORT.......
abhishekm71 (820)
Please specify exactly what doesn't work. Take the help of a debugger or manually trace your code execution. Then find out the point where your code deviates from the expected behaviour.
KyiannaJones (20)
Here is a link that should be helpful.
This is an example of Merge Sort with a pointer
Please reply and let me know if this helpful:

http://www.cplusplus.com/forum/beginner/105600/


MERGE_SORT

giovanninokr (6)
=(
Topic archived. No new replies allowed.