[SOLVED] Doing quicksort in ags, problems with pointers and managed types

[eri0o]

I sort of needed a quicksort in AGS and decided to read Wikipedia, pick up the easiest algorithm and implement it.

this lead to:
qsort.ash

Code: ags

import void qsort(int arr[], int size);

qsort.asc

Code: ags

void _swap(int arr[], int p1, int p2){
  int temp = arr[p1];
  arr[p1] = arr[p2];
  arr[p2] = temp;  
}

int _partition(int arr[], int lo, int hi) {
  int pivot = arr[hi];
  int i = lo;
  int j;
  for (j = lo; j<hi; j++) {
    if(arr[j] < pivot) {
      _swap(arr, i, j);
      i = i + 1;
    }
  }
  _swap(arr, i, j);
  return i;
}

void _quicksort(int arr[], int lo, int hi){
  if( lo < hi) {
    int p = _partition(arr, lo, hi);
    _quicksort(arr, lo, p-1);
    _quicksort(arr, p+1, hi);
  }  
}

void qsort(int arr[], int size) {
  _quicksort(arr, 0, size-1);
}

so far so good, decided to make a little room experiment to verify this works.

room1.asc

Code: ags

// room script file
#define ARRAY_SIZE 32

int my_a[];
int my_a_size = ARRAY_SIZE;

String _print_array(int arr[], int size){
  String str = "";
  int column_count = 3;
  for(int i=0; i<size; i++){
    str = str.Append(String.Format("  \[%02d]: %02d ", i, arr[i]));
    if((i+1)%column_count == 0)str = str.Append("\n");
  }
  return str;
}

void _randomize_array(int arr[], int size){
  for(int i=0; i<size; i++){
    arr[i] = Random(40);
  }
}

function room_Load()
{
  my_a = new int[my_a_size];
  _randomize_array(my_a, my_a_size);
}


function room_AfterFadeIn()
{
  Display("This is an array we want to sort");
  Display(_print_array(my_a, my_a_size));
  Display("let's use qsort!");
  qsort(my_a, my_a_size);
  Display(_print_array(my_a, my_a_size));
  QuitGame(1);
}

Edit: I previously had the following error, which CW picked up in the post below!  The code above is fixed thanks to him, but file attached below here is the wrong old wrong code!



But my room script doesn't compile: room1.asc(25): Error (line 25): Type mismatch: cannot convert 'int*' to 'int[]'

I kinda forgot how pointers and things worked, I tried to switch int arr[] to int* arr in the function _randomize_array, but it led to "room1.asc(17): Error (line 17): Cannot declare pointer to non-managed type".

I am rusty, how should I pass array of integers in functions?

To make things easier, here is the project: Quicksort.zip

[Crimson Wizard]

It looks like you are passing non-dynamic array (my_a) into functions that expect a dynamic array (qsort, _randomize_array).

Make my_a also a dynamic array:

Code: ags

int my_a[];

you'd have to allocate it somewhere, e.g.

Code: ags

void create_my_array()
{
     my_a = new int[ARRAY_SIZE];
}

[eri0o]

Boom! Thanks! That was it! Now I can fix all the other errors! Thanks so much CW!

Edit: It works!