PHP User Warning: fetch_template() calls should be replaced by the vB_Template class. Template name: bbcode_highlight in ..../includes/functions.php on line 4197
quicksort issue-VBForums
Results 1 to 16 of 16

Thread: quicksort issue

  1. #1

    Thread Starter
    Frenzied Member
    Join Date
    Jan 2009
    Location
    Watch Window(Shift+f9)
    Posts
    1,879

    Question quicksort issue

    hi guys,

    can anyone tell me ? how i will get sorted no of array using quick sort . following is the code what i did . suggestion please .
    Code:
    Option Explicit
    Dim z(5) As Integer
    Private Sub Form_Load()
    Dim x As Integer
    For x = 0 To 4
    z(x) = InputBox("enter a no")
    Next
    Call QuickSort(z, 0, 4)
    While Not (x = 0)
              List1.AddItem (z(x))
              Debug.Print z(x)
        x = x - 1
    Wend
    End Sub
    Public Sub QuickSort(ByRef InputArr() As Integer, left As Integer, right As Integer)
    Dim k As Integer
    If (left < right) Then
      k = pivotFun(InputArr(), left, right)
     Debug.Print k
      Call QuickSort(InputArr(), left, k - 1)
      Call QuickSort(InputArr(), k + 1, right)
    End If
    End Sub
    Public Function pivotFun(ByRef data() As Integer, left As Integer, right As Integer) As Integer
       Dim x As Integer
        Dim temp As Integer
        Dim pivot As Integer
        pivot = data(right)
          For x = left To (right - 1)
            If data(x) <= pivot Then
                temp = data(x)
                data(x) = data(left)
                data(left) = temp
                left = left + 1
            End If
        Next
        data(right) = data(left)
        data(left) = pivot
        pivotFun = left
    End Function
    Last edited by firoz.raj; May 20th, 2018 at 09:40 AM. Reason: format

  2. #2

    Thread Starter
    Frenzied Member
    Join Date
    Jan 2009
    Location
    Watch Window(Shift+f9)
    Posts
    1,879

    Re: quicksort issue

    pivotFun(InputArr(), left, right) always returns 0 . can you person help me please .
    in vb.net it is working fine . following are the code .
    Code:
    Public Shared Sub QuickSortRecursive(ByRef data As Integer(), left As Integer, right As Integer)
    	If left < right Then
    		Dim q As Integer = Partition(data, left, right)
    		QuickSortRecursive(data, left, q - 1)
    		QuickSortRecursive(data, q + 1, right)
    	End If
    End Sub
    
    Private Shared Function Partition(ByRef data As Integer(), left As Integer, right As Integer) As Integer
    	Dim pivot As Integer = data(right)
    	Dim temp As Integer
    	Dim i As Integer = left
    
    	For j As Integer = left To right - 1
    		If data(j) <= pivot Then
    			temp = data(j)
    			data(j) = data(i)
    			data(i) = temp
    			i += 1
    		End If
    	Next
    
    	data(right) = data(i)
    	data(i) = pivot
    
    	Return i
    End Function

  3. #3
    Fanatic Member wqweto's Avatar
    Join Date
    May 2011
    Posts
    683

    Re: quicksort issue

    Help debugging

    In pivotFun:

    This: data(right) = data(x) should become data(right) = data(left)
    This: data(left) = pivit should become data(left) = Pivot

    Suggestion

    Using Option Explicit to require variable declaration will prevent errors like using undeclare pivit variable (instead of Pivot).

    cheers,
    </wqw>

  4. #4

    Thread Starter
    Frenzied Member
    Join Date
    Jan 2009
    Location
    Watch Window(Shift+f9)
    Posts
    1,879

    Question Re: quicksort issue

    Using Option Explicit to require variable declaration will prevent errors like using undeclare pivit variable (instead of Pivot).
    it was already there . can you give comment logically . where and what is missing to sort the numbers



    it seems there is some problem in pivot function . can anyone see please ?
    Code:
    Option Explicit
    Dim z(5) As Integer
    Private Sub Form_Load()
    Dim x As Integer
    For x = 0 To 4
    z(x) = InputBox("enter a no")
    Next
    Call QuickSort(z, 0, 4)
    While Not (x = 0)
              List1.AddItem (z(x))
              Debug.Print z(x)
        x = x - 1
    Wend
    End Sub
    Public Sub QuickSort(ByRef InputArr() As Integer, left As Integer, right As Integer)
    Dim k As Integer
    If (left < right) Then
      k = pivotFun(InputArr(), left, right)
     Debug.Print k
      Call QuickSort(InputArr(), left, k - 1)
      Call QuickSort(InputArr(), k + 1, right)
    End If
    End Sub
    Public Function pivotFun(ByRef data() As Integer, left As Integer, right As Integer) As Integer
       Dim x As Integer
        Dim temp As Integer
        Dim pivot As Integer
        pivot = data(right)
          For x = left To (right - 1)
            If data(x) <= pivot Then
                temp = data(x)
                data(x) = data(left)
                data(left) = temp
                left = left + 1
            End If
        Next
        data(right) = data(left)
        data(left) = pivot
        pivotFun = left
    End Function
    Last edited by firoz.raj; May 20th, 2018 at 09:43 AM.

  5. #5
    Fanatic Member
    Join Date
    Dec 2014
    Posts
    628

    Re: quicksort issue

    you should definitely check the sort thread in here, they have source of many types, including different quicksort.
    your version is buggy and it seems you are doing it wrong. better check that thread, and if you want to make one yourself, you should not let someone else fix it, instead try to do it yourself. you have many examples to follow.

  6. #6

    Thread Starter
    Frenzied Member
    Join Date
    Jan 2009
    Location
    Watch Window(Shift+f9)
    Posts
    1,879

    Re: quicksort issue

    it seems you are doing it wrong
    then why you have post the thread now . unnessary waisting time to just post . telling your version is buggy . never reply to my post .

    you should not let someone else fix it
    no it is incorrect . someone needs to tell if some logical issue . then it means you are actual member to the forum. just google from the net and telling see it . and give me the point . you need to see the posted code . and then you need to give relevant ans .
    Last edited by firoz.raj; May 20th, 2018 at 10:10 AM.

  7. #7
    Fanatic Member wqweto's Avatar
    Join Date
    May 2011
    Posts
    683

    Re: quicksort issue

    Parameters left and right should be explicitly passed ByVal in VB6. In VB.Net passing params ByVal is the default, while in VB6 ByRef is default when not specified.

    Change function declaration from

    Public Function pivotFun(ByRef data() As Integer, left As Integer, right As Integer) As Integer

    to this

    Public Function pivotFun(ByRef data() As Integer, ByVal left As Integer, ByVal right As Integer) As Integer

    Note that you are sorting elements from index 0 to 4 but printing/adding to List1 elements from 1 to 5 (last 5th element is always zero) and doing this in reverse order from element 5 to 1 (for no apparent reason).

    cheers,
    </wqw>

  8. #8

    Thread Starter
    Frenzied Member
    Join Date
    Jan 2009
    Location
    Watch Window(Shift+f9)
    Posts
    1,879

    Re: quicksort issue

    Public Function pivotFun(ByRef data() As Integer, ByVal left As Integer, ByVal right As Integer) As Integer
    it has not helped .


    there is few problem in the following chunk of the code . can you modified in correct manner please .
    Code:
    pivot = data(right)
          For x = left To (right - 1)
            If data(x) <= pivot Then
                temp = data(x)
                data(x) = data(left)
                data(left) = temp
                left = left + 1
            End If
        Next
        data(right) = data(left)
        data(left) = pivot
        pivotFun = left

  9. #9
    VB-aholic & Lovin' It LaVolpe's Avatar
    Join Date
    Oct 2007
    Location
    Beside Waldo
    Posts
    17,441

    Re: quicksort issue

    @firoz. You seem to be taking some of the replies personally.

    baka suggested looking at an already posted quicksort routine within the codebank. In fact, that codebank submission has over a dozen sort algorithms. Why re-invent the wheel trying unsuccessfully translating a .Net version? You may even find solutions to your own problems by looking at the quicksort algorithm in the codebank.
    http://www.vbforums.com/showthread.p...orting-arrays)

    Edited. Is there a reason why you are restricting your functions to Integers vs Longs?
    Last edited by LaVolpe; May 20th, 2018 at 10:32 AM.
    Insomnia is just a byproduct of, "It can't be done"

    Classics Enthusiast? Here's my 1969 Mustang Mach I Fastback. Her sister '67 Coupe has been adopted

    Newbie? Novice? Bored? Spend a few minutes browsing the FAQ section of the forum.
    Read the HitchHiker's Guide to Getting Help on the Forums.
    Here is the list of TAGs you can use to format your posts
    Here are VB6 Help Files online


    {Alpha Image Control} {Memory Leak FAQ} {Unicode Open/Save Dialog} {Resource Image Viewer/Extractor}
    {VB and DPI Tutorial} {Manifest Creator} {UserControl Button Template} {stdPicture Render Usage}

  10. #10
    Fanatic Member wqweto's Avatar
    Join Date
    May 2011
    Posts
    683

    Re: quicksort issue

    Quote Originally Posted by firoz.raj View Post
    it has not helped .


    there is few problem in the following chunk of the code . can you modified in correct manner please .
    I already told you there is no problem in the sorting code now (after ByVal fix) but you are printing elements from final sorted array z in reverse order. Do you understand that?

    You are printing indexes from 5 to 1 but you are sorting indexes from 0 to 4. Do you realize that?

    Element 5 is always 0 and is the first one printed so you get "0, 9, 8, 7, ..." printed. Do you realize that?

    Here is the complete working code, with the printing fixed (forward from index 0 to index 4)
    thinBasic Code:
    1. Option Explicit
    2.  
    3. Dim z(5) As Integer
    4.  
    5. Private Sub Form_Load()
    6. Dim x As Integer
    7. For x = 0 To 4
    8. z(x) = InputBox("enter a no")
    9. Next
    10. Call QuickSort(z, 0, 4)
    11. For x = 0 To 4
    12.         List1.AddItem (z(x))
    13.         Debug.Print z(x)
    14. Next
    15. End Sub
    16.  
    17. Public Sub QuickSort(ByRef InputArr() As Integer, left As Integer, right As Integer)
    18. Dim k As Integer
    19. If (left < right) Then
    20.   k = pivotFun(InputArr(), left, right)
    21.  Debug.Print k
    22.   Call QuickSort(InputArr(), left, k - 1)
    23.   Call QuickSort(InputArr(), k + 1, right)
    24. End If
    25. End Sub
    26.  
    27. Public Function pivotFun(ByRef data() As Integer, ByVal left As Integer, ByVal right As Integer) As Integer
    28.    Dim x As Integer
    29.     Dim temp As Integer
    30.     Dim pivot As Integer
    31.     pivot = data(right)
    32.       For x = left To (right - 1)
    33.         If data(x) <= pivot Then
    34.             temp = data(x)
    35.             data(x) = data(left)
    36.             data(left) = temp
    37.             left = left + 1
    38.         End If
    39.     Next
    40.     data(right) = data(left)
    41.     data(left) = pivot
    42.     pivotFun = left
    43. End Function
    Is this what you want?

    cheers,
    </wqw>

  11. #11
    PowerPoster
    Join Date
    Feb 2012
    Location
    West Virginia
    Posts
    12,375

    Re: quicksort issue

    Given that Left() and Right() are VB functions I would strongly suggest not using those as variable names.

  12. #12

    Thread Starter
    Frenzied Member
    Join Date
    Jan 2009
    Location
    Watch Window(Shift+f9)
    Posts
    1,879

    Re: quicksort issue

    you are printing elements from final sorted array z in reverse order. Do you understand that?
    it does not make sense if after sorting array is data{4,7,5,9,1} and i want to retrieve
    either print
    data(0)
    data(1)
    ---
    ---
    data(4)

    or
    data(4)
    data(3)
    data(2)
    data(1)
    data(0) using while loop it is always the same .

    hi mate, can you suggest please if arr is Data(2,4,7,8,2} pivot fun how value returns or how this chunk of code needs to be more sorter to reduce confusion in the following code
    Code:
    Public Function pivotFun(ByRef data() As Integer, ByVal left As Integer, ByVal right As Integer) As Integer
       Dim x As Integer
        Dim temp As Integer
        Dim pivot As Integer
        pivot = data(right)
          For x = left To (right - 1)
            If data(x) <= pivot Then
                temp = data(x)
                data(x) = data(left)
                data(left) = temp
                left = left + 1
            End If
        Next
        data(right) = data(left)
        data(left) = pivot
        pivotFun = left
    End Function
    Last edited by firoz.raj; Jun 12th, 2018 at 07:30 AM.

  13. #13
    Fanatic Member wqweto's Avatar
    Join Date
    May 2011
    Posts
    683

    Re: quicksort issue

    With this input I get 2, 2, 4, 7, 8 in the ListBox and this looks sorted enough IMO.

    What sort of confusion do you find in the snippet above?

    cheers,
    </wqw>

  14. #14

    Thread Starter
    Frenzied Member
    Join Date
    Jan 2009
    Location
    Watch Window(Shift+f9)
    Posts
    1,879

    Re: quicksort issue

    Code:
    With this input I get 2, 2, 4, 7, 8 in the ListBox and this looks sorted enough IMO.
    
    What sort of confusion do you find in the snippet above?
    can you person make the pivotfun less smaller by some better idea .

  15. #15
    PowerPoster
    Join Date
    Feb 2012
    Location
    West Virginia
    Posts
    12,375

    Re: quicksort issue

    Quote Originally Posted by firoz.raj View Post
    Code:
    With this input I get 2, 2, 4, 7, 8 in the ListBox and this looks sorted enough IMO.
    
    What sort of confusion do you find in the snippet above?
    can you person make the pivotfun less smaller by some better idea .
    Well if you want to make it larger [less smaller] and less confusing then maybe you should add some comments to it

    Or are you meaning to ask something different?

  16. #16
    Fanatic Member wqweto's Avatar
    Join Date
    May 2011
    Posts
    683

    Re: quicksort issue

    It's the pivot value selection that makes a difference in any particular quick-sort implementation. Currenly you have pivot = data(right) which is vulnerable to pathological inputs (e.g. input already sorted) that bring execution time closer to O(N^2) comparisons.

    Good selection of pivot value should reduce comparisons closer to O(N logN) but usually such good pivot selection takes more than O(N logN) to calculate or is once again vulnerable to (other) pathological inputs.

    cheers,
    </wqw>

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width