Forum > Beginners
QuickSort Problem
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