Forum > Beginners

QuickSort Problem

(1/3) > >>

JLWest:
I copied this QuickSort Procedure posted by GetMan. I have tried to use it in a program but either my implementation is bad or the code is bad. My guess its me.
It doesn't  sort and adds a to the array.  zip demo attached.

Thanks

--- Code: Text  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} --- of Integer; var  Form1: TForm1;  SouthHand  : SouthHandArray;              pascal]procedure TForm1.QuickSort(var AI: array of Integer; ALo, AHi: Integer); var  Lo, Hi, Pivot, T: Integer; begin  Lo := ALo;  Hi := AHi;  Pivot := AI[(Lo + Hi) div 2];  repeat    while AI[Lo] < Pivot do      Inc(Lo) ;    while AI[Hi] > Pivot do      Dec(Hi) ;    if Lo <= Hi then    begin      T := AI[Lo];      AI[Lo] := AI[Hi];      AI[Hi] := T;      Inc(Lo) ;      Dec(Hi) ;    end;  until Lo > Hi;  if Hi > ALo then    QuickSort(AI, ALo, Hi) ;  if Lo < AHi then    QuickSort(AI, Lo, AHi) ;end;                                                          

dseligo:
Your array SouthHandArray is '1' based and parameter AI in QuickSort method is zero based.

You can change AI parameter to SouthHandArray or you could change SouthHandArray definition to:

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---  SouthHandArray = Array[0..12] of Integer;
And all fixed indexes decrease by 1.

JLWest:
I understand what you are saying, however I don't know how to fix the problem.

I need the array to be 1..13 not 0 based The array represents a of bridge.

I call QuickSort      QuickSort(var SouthHand,1,13);

So how would I fix QuickSort?

Thanks

Handoko:
Bug fixed. I checked the code, GetMem's code has no bug and it supports non-zero-based array. But you cannot simply copy/paste to use it, some adaptations are needed.


--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---unit Unit1; {$mode objfpc}{$H+} interface uses  Classes, SysUtils, Forms, Controls, Graphics, Dialogs,  ExtCtrls, StdCtrls,Buttons,ComCtrls,  Menus, Types, LCLType, ActnList; type   SouthHandArray = Array[1..13] of Integer;   { TForm1 }   TForm1 = class(TForm)   btnGo: TButton;   ListBox1: TListBox;   ListBox2: TListBox;    procedure btnGoClick(Sender: TObject);    procedure FormCreate(Sender: TObject);    procedure QuickSort(var AI: SouthHandArray; ALo, AHi: Integer);    procedure ShowSouthHand;   private   public   end; var  Form1: TForm1;  SouthHand  : SouthHandArray;implementation {$R *.lfm} { TForm1 } procedure TForm1.FormCreate(Sender: TObject);begin Form1.Height:=1050; Form1.Width:=1552; ListBox1.Width := 80;end; procedure TForm1.btnGoClick(Sender: TObject);begin Listbox1.Clear; SouthHand[1]:=27; SouthHand[2]:=17; SouthHand[3]:=7; SouthHand[4]:=52; SouthHand[5]:=5; SouthHand[6]:=49; SouthHand[7]:=33; SouthHand[8]:=29; SouthHand[9]:=21; SouthHand[10]:=14; SouthHand[11]:=38; SouthHand[12]:=3; SouthHand[13]:=23; QuickSort(SouthHand, 1, 13) ; ShowSouthHand; end; procedure TForm1.QuickSort(var AI: SouthHandArray; ALo, AHi: Integer); var  Lo, Hi, Pivot, T: Integer; begin  Lo := ALo;  Hi := AHi;  Pivot := AI[(Lo + Hi) div 2];  repeat    while AI[Lo] < Pivot do      Inc(Lo) ;    while AI[Hi] > Pivot do      Dec(Hi) ;    if Lo <= Hi then    begin      T := AI[Lo];      AI[Lo] := AI[Hi];      AI[Hi] := T;      Inc(Lo) ;      Dec(Hi) ;    end;  until Lo > Hi;  if Hi > ALo then    QuickSort(AI, ALo, Hi) ;  if Lo < AHi then    QuickSort(AI, Lo, AHi) ;end;  procedure TForm1.ShowSouthHand; begin Listbox1.Clear; Listbox1.Items.add(IntToStr(SouthHand[1])); Listbox1.Items.add(IntToStr(SouthHand[2])); Listbox1.Items.add(IntToStr(SouthHand[3])); Listbox1.Items.add(IntToStr(SouthHand[4])); Listbox1.Items.add(IntToStr(SouthHand[5])); Listbox1.Items.add(IntToStr(SouthHand[6])); Listbox1.Items.add(IntToStr(SouthHand[7])); Listbox1.Items.add(IntToStr(SouthHand[8])); Listbox1.Items.add(IntToStr(SouthHand[9])); Listbox1.Items.add(IntToStr(SouthHand[10])); Listbox1.Items.add(IntToStr(SouthHand[11])); Listbox1.Items.add(IntToStr(SouthHand[12])); Listbox1.Items.add(IntToStr(SouthHand[13])); end; end.
The code above is the fixed version. I only made modifications on:
- Line #24
- Line #70
- Line #46 (not important, only cosmetic issue on my system)

Lazarus/Pascal is strict but it is not strict enough to prevent you to supply wrong data type for the parameter. In this case, dynamic array vs static lenght array. And that was the cause of the issue.

Edit:

Actually the problem was you're trying to provide non-zero-based array as an open array. Open array always count from 0 but your array (SouthHandArray) start from 1.

The code above solve the problem by using exact data type on the parameter. Alternatively, you can fix the problem simply changing the line #65 in the code above to QuickSort(SouthHand, 0, 12);  , but keeping the open array in the line #24 & #70.

JLWest:
Thanks Handoko

It late here, I'll try it in the morning.

Navigation

[0] Message Index

[#] Next page