Pascal Quicksorting Help

viserov · Apr 22, 2004

Hi... I was wondering if I could get help with my Pascal program that is designed to quicksort an array.

I'm having difficulty compiling a Pascal program that performs a quicksort on an array. I keep getting the compiler error (using the Free Pascal compiler) that is telling me that the last end should be end; instead of end. I know this can't be true, because the ending of all Pascal programs must end with end.

Does anyone have any ideas on what the problem could be?

Thanks

Code:

program QS;

{ program's variables are declared }
var 
i, done, length : Integer;
a: array[0..10] of Integer;

{ the quicksort function than will sort the array } 
function Quicksort( left, right : Integer ) : Integer;

{ quicksort's local variables are declared } 
var marker : Integer;
   x : Integer;
   y : Integer;
   temp : Integer;
   
begin      
     
   while ( right - left ) > 0 do
   begin
       
       { set the pivot to be the left element and placeholds x and y to be }
       { one less than and one greater than left and right, respectively   }
       marker := a[left];
       x := left - 1;
       y := right + 1;
       
       { infinite loop that will swap out two elements upon successful completion of an iteration }
       while 1 = 1 do
       begin
           x := x + 1;
           y := y - 1;
           
           { increment x while the element in a[x] is smaller than the marker }
           while a[x] < marker do 
           begin
               x := x + 1;
           end;
           
           { decrement y while the element in a[y] is larger than the marker }
           while a[y] > marker do 
           begin
               x := x + 1;
           end;
           
           { break out of the while loop of x and y overlap }
           if x >= y then
           break;
           
           { swap the data in a[x] and a[y] }
           temp := a[x];
           a[x] := a[y];
           a[y] := temp;
                      
           
        end;
        
     if y - left + 1 < right - y  then
     begin
           { recursive call to quicksort the subarray spanning from a[left] through a[y] }
           done := Quicksort( left, y );
           left := y + 1;
     end
          
     else
     begin
           { recursive call to quicksort the subarray spanning from a[y+1] through a[right] }
           done := Quicksort( y + 1, right );
           right := y;
     end;
     
      { output the array }   
    writeln( ' Implementing quicksort... ' );     
    while i <= length do
    begin
        writeln( a[i] );
        i := i + 1;
    end;          
end;



{ begin the program here }
begin
i := 0;
length := 10; { the length is set to be 10 }

writeln( ' The array length is 10. Please enter the elements of this array: ' );

{ take in user input for each elememt of the array } 
while i <= length do
    begin
        readln( a[i] );
        i := i + 1;
    end;

{ output the array }   
writeln( ' The unsorted array: ' );     
while i <= length do
    begin
        writeln( a[i] );
        i := i + 1;
    end;    
    
done := Quicksort( 0, 10 );   

i := 0;

{ output the array }   
writeln( ' The sorted array: ' );     
while i <= length do
    begin
        writeln( a[i] );
        i := i + 1;
    end;   

end.

FuzzyDonkey · Apr 22, 2004

use code tags. [ code ] and [ /code ] around your source to preserve indenting.

You have 12 begins, and 11 ends. find where you have an end missing, or an extra begin, and fix it.

viserov · Apr 22, 2004

I spent 3 hours trying to figure out what was wrong and couldn't find that error. Thanks, you were right, I was missing an end for the big while loop.

viserov · Apr 22, 2004

Okay, everything works except for one issue. For some reason, when running, the Swap procedure call in the Quicksort procedure is never executed. I've compared this program with a fully functional C version and everything seems fine. Anyone have any ideas?

Ignore some of the writeln's, as they've been helping me tracking the stupid bug.

Code:

program QS;

{ ------------------------------------------------------------------- }	
{  The global variables are declared here.                            }
{ ------------------------------------------------------------------- }

var	
	i : Integer;
	a: array[0..10] of Integer;
	
const length : Integer = 10;


{ ------------------------------------------------------------------- }	
{  The Swap procedure swaps out two elements inside the array.        }
{ ------------------------------------------------------------------- }

procedure Swap( e1, e2 : Integer );

var temp : Integer;

begin
    writeln( 'eee' );
    temp  := a[e1];
    a[e1] := a[e2];
    a[e2] := temp;
end;			
	
	
{ ------------------------------------------------------------------- }	
{  The Print procedure prints out the array, one element at a time.   }
{ ------------------------------------------------------------------- }

procedure Print;

var j : Integer;

begin
    for j := 0 to length - 1 do
    begin
        write( a[j], ' ' );
    end;
    writeln;
end;	
	
	
{ ------------------------------------------------------------------- }	
{  The Quicksort procedure will sort the array.                       }
{ ------------------------------------------------------------------- }

procedure Quicksort( left , right : Integer );

var marker, x, y : Integer;
    
begin      
    
    { output the array }   
	write( ' Implementing quicksort... ' );    
	Print;    

    while ( right - left ) > 0 do
    begin
        
        { set the pivot to be the left element and placeholds x and y to be }
        { one less than and one greater than left and right, respectively   }      
        marker := a[left];
        x := left - 1;
        y := right + 1;
        
         
        
        { infinite loop that will swap out two elements upon successful completion of an iteration }
        while 1 = 1 do
        begin
                       
            { increment x while the element in a[x] is smaller than the marker }
            x := x + 1;
            
            writeln( 'marker is ', marker, ' left is ', left, ' right is ', right );
         writeln( 'x is ', x, ' y is ', y, 'a[x] is ', a[x], ' a[y] is ', a[y] );
            
            while a[x] < marker do 
            begin
                x := x + 1;
            end;
            
            { decrement y while the element in a[y] is larger than the marker }
            y := y - 1;
            while a[y] > marker do 
            begin
                y := y - 1;
            end;
            
            { break out of the while loop of x and y overlap }
            if ( x >= y ) then
                Break;
            
            writeln( 'fff' )
            { swap the data in a[x] and a[y] }
            Swap( x, y );
        end;
    end;
         
      if ( ( y - left + 1 ) < ( right - y ) ) then
      begin
            { recursive call to quicksort the subarray spanning from a[left] through a[y] }
            Quicksort( left, y );
            left := y + 1;
      end
           
      else
      begin
            { recursive call to quicksort the subarray spanning from a[y+1] through a[right] }
            Quicksort( y + 1, right );
            right := y;
      end;
      
      	    
end;


{ ------------------------------------------------------------------- }	
{  The program begins here, which calls the necessary procedures.     }
{ ------------------------------------------------------------------- }

begin

	{ inform the user that the array is a fixed size }
	writeln;
	write( ' Note that the array will be of size ', length, '. Press enter to confirm...' );
	readln;
	writeln;
	
	{ allow user to enter in a value for each array element }
	for i := 0 to length - 1 do
	    begin
	        write( ' Enter the value for array position ', i, ': ' );
	        readln( a[i] );
	    end; 
	
	{ output the unsorted array to the screen }
	writeln;
	write( ' Unsorted Array: ' );
	Print;
	
	{ begin the sorting process }	    
	Quicksort( 0, 9 );   
		
	{ output the array }   
	write( ' Sorted Array: ' );
	Print; 

end.

Cardboard Hammer · Apr 22, 2004

I know little about Pascal, but from the looks of the rest of the code, shouldn't there be a semicolon at the end of the first line in the code snippet below?

Code:

            writeln( 'fff' )
            { swap the data in a[x] and a[y] }
            Swap( x, y );

EDIT: after looking at the original code, that's likely not the real problem...

viserov · Apr 23, 2004

Yeah, I corrected the error after I copied it to the forum, but despite that, when I run the program, it freezes when it gets to the Swap call.

viserov · Apr 23, 2004

If this will help, here's the equivalent C code:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/**
 *
 * All of the functions used in the program are declared as prototypes here.
 *
 **/

void generateArray( int * );
void printArray( int * );
void quicksort( int *, int, int );
void swap( int *, int, int );

/**
 *
 * The size of the array is global so it can be used anywhere in the program.
 *
 **/

int length;


/**
 *
 * Begin the program here.
 *
 **/
 
void main()
{ 
    int *array;
    
    // obtain from the user the array size
    printf( "\n Enter the array size as a positive number greater than zero: " );
    scanf( "%d", &length );
    
    // ask the user for a valid input, if he/she entered in a nonpositive
    while( length <= 0 )
    {
        printf( " You entered a nonpositive number; please try again: " );
        scanf( "%d", &length );
    }
    
    // allocate memory for the array based on user-inputted length
    array = malloc( sizeof(int)* length );
    
    // output informative message to the user
    printf( " The %d elements of this array will be randomly generated.\n\n", length );
    
    // send the array to be generated
    generateArray( array );
    
    // output the array before we start sorting it
    printf( "\n Unsorted Array: " );
    printArray( array );
    
    // begin the quicksorting process    
    quicksort( array, 0, length - 1 );
    
    // output the array after sorting
    printf( "\n Sorted Array: " );
    printArray( array );
    printf( "\n" );
    
    // de-allocate the memory used by the array
    free( array );    
}


/**
 *
 * This function will generate random numbers from 1 - 100 to complete the array.
 *
 **/

void generateArray( int* a )
{
    int i;
    
    // seed the random number generator
    srand( time(0) );
    
    // randomly generate numbers to fill in the array
    for( i = 0; i < length; i++ )
        a[i] = rand() % 100;    
}


/**
 *
 * This function will simply output one element at a time the entire array to the screen.
 *
 **/

void printArray( int* a )
{
    int i;
    for( i = 0; i < length; i++ )
        printf( "%d ", a[i] );
}


/**
 *
 * This function will implement the quicksort algorithm in a recursive process.
 *
 **/

void quicksort( int* a, int left, int right )
{
    int marker;
    int x;
    int y;

    // output this stage of the array to the screen
    printf( "\n Implementing Quicksort... " );
    printArray( a );    
    
    while( right - left > 0 )
    {
        // set the pivot to be the left element and placeholds x and y to be
        // one less than and one greater than left and right, respectively
        marker = a[left];
        x = left - 1;
        y = right + 1;
        
        // infinite loop that will swap out two elements upon successful completion of an iteration
        while( 1 )
        {
            // increment x while the element in a[x] is smaller than the marker
            do ++x; while( a[x] < marker ); 
            
            // decrement y while the element in a[y] is larger than the marker
            do --y; while( a[y] > marker );
            
            // break out of the while loop of x and y overlap
            if( x >= y ) 
                break;
            
            // swap the elements in a[x] and a[y]
            swap( a, x, y ); 
        }
        
        if( y - left + 1 < right - y )
        {
            // recursive call to quicksort the subarray spanning from a[left] through a[y]
            quicksort( a, left, y );
            left = y + 1;
        }
        else
        {
            // recursive call to quicksort the subarray spanning from a[y+1] through a[right]
            quicksort( a, y + 1, right );
            right = y;
        }
    }
}
\

/**
 *
 * This function will swap two elements in an array with the use of a temp variable.
 *
 **/

void swap( int* a, int x, int y )
{
    int temp;
    temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

Cardboard Hammer · Apr 23, 2004

Originally posted by viserov
Yeah, I corrected the error after I copied it to the forum, but despite that, when I run the program, it freezes when it gets to the Swap call.

So, it prints "fff" and then.... nothing?

ameoba · Apr 23, 2004

in the C version, the recursive calls to quicksort() are inside the while( right - left > 0 ) loop. In your version, they're not.

This is why you should try to understand the code you're writing rather than simply trying to translate an example you found online into Pascal.

...and if you're going to copy something, at least pick a better example. No reason to even really have that while(right-left>0) for a quicksort, an if statement would make more sense. Once you partition the list into 2 parts, you should only need to call QS on each half once.

just to be a real smartass, I'm going to show you how to do this with half a page of Prolog:

Code:

partition(_, [], [], []).
partition(X, [Y|Ys], [Y|L], R) :-
	Y < X,
	partition(X, Ys, L, R).
partition(X, [Y|Ys], L, [Y|R]) :-
	Y >= X,
	partition(X, Ys, L R).

qs([],[]).
qs([X|In],Out) :-
	partition(X, InTail, Low, High),
	qs(Low,LowS),
	qs(High, HighS),
	append(LowS, [Pivot|HighS], Out).

Granted, this is really inefficient (the appends rape you), but conceptually very clear. It could be sped up quite a bit but it's best not to speak of incomplete data structures in public

viserov · Apr 23, 2004

Actually, I did not copy any Pascal code. I had to take C code and convert it into Pascal. The C code was written by me, and I was more concerned with the program functioning as opposed to efficiency.

viserov · Apr 23, 2004

Originally posted by Cardboard Hammer
So, it prints "fff" and then.... nothing?

It doesn't print anything anymore, I just put the statement there so I could tell if the code was actually executing at that point, which I found out was. I just forgot to take the writeln statement out.

Cardboard Hammer · Apr 23, 2004

Originally posted by viserov
It doesn't print anything anymore, I just put the statement there so I could tell if the code was actually executing at that point, which I found out was. I just forgot to take the writeln statement out.

Right. That's what I was wondering: whether or not it actually got through that point. You should just be glad I didn't rake your logic over the fire

At this point, I can't really see any reason it would be failing... Do you have access to a debugger that you could use to step through line by line and inspect the state of the variables?

EDIT: And, I take it, it still pitches a fit when the swap is being done inline (as in the code you first posted) instead of in a function dedicated to the purpose?

EDIT 2: Have you tried printing out x and y just before the call to swap to ensure that they're not out of bounds? It doesn't look like they could get that way, but it doesn't hurt to check...

FuzzyDonkey · Apr 24, 2004

Originally posted by viserov
I had to take C code and convert it into Pascal.

Good god, man, why?!?!

ameoba · Apr 24, 2004

you did move the

Code:

if y - left + 1 < right - y  then
     begin
           { recursive call to quicksort the subarray spanning from a[left] through a[y] }
           done := Quicksort( left, y );
           left := y + 1;
     end
          
     else
     begin
           { recursive call to quicksort the subarray spanning from a[y+1] through a[right] }
           done := Quicksort( y + 1, right );
           right := y;

inside the loop, right?

I did that to it and it compiled & ran just fine.

Pascal Quicksorting Help

viserov

n00b

FuzzyDonkey

[H]ard|Gawd

viserov

n00b

viserov

n00b

Cardboard Hammer

2[H]4U

viserov

n00b

viserov

n00b

Cardboard Hammer

2[H]4U

ameoba

Supreme [H]ardness

viserov

n00b

viserov

n00b

Cardboard Hammer

2[H]4U

FuzzyDonkey

[H]ard|Gawd

ameoba

Supreme [H]ardness