How to short an array by recursion

9 Years Ago Santanu.Das 0 520 Views

This conception I get from a post on CodeProject by Heriberto Lugo. But that was for only 10 numbers. Then I had an idea to use it in vb. There are many shorting process like Bubble Short, Linear Short etc. But exceptionally it does not use loops as others do. It does it by recursion.
If we take an array of 10 elements and store a value from 10 to 1 in each Array Element. It should be like
a09127110acb607fa3464fb2a9df79ab

Let us try to go through the rotation.
Consider for the first element, the stored value is 10. It runs 9 comparison processes. Likely, for the value 9 it runs 8 and so on and for the value 2 it runs only 1 process. Every time the process starts from the array element 0.

494c810d194f277325d7e532c15d1795

Finally we get

How it works.
I create a Sub Procedure “TryToShort”, which is a recursive sub.
The comparison process is as usual. Check the condition if the value of an element is greater than the next element value then swap the values between them after that do same for next.
But when it goes to the end stop and go to the next rotation from the first element of the array. Every time it starts from first element of the array. But in the middle of the process, if it looks that the next element value is less or equal to its value then it stops and the process starts for the next element value. And finally it produces to us a shorted array.
But the question arises here how many times the process would be and also the rotation.
The number of process depends on the number of rotation. Not every rotation has performed equal numbers of processes.
Rotation no is one short from the number of array elements.
Suppose, R is the number of rotation then
R = NumArray.GetUpperBound(0) - 1
We get the rotation number but what is the number of process for every rotation. It differs on each rotation by 1 from the previous.
Number of process is the number of array element minus rotation number, if you take the numbers serially in descending order. Like from 10 to 1 (in example).
Suppose, P is the number of process then
P = NumArray.GetUpperBound(0) – Rotation number
But, if you take the numbers randomly, the calculation is the same. Because when it looks that the next element value is less or equal to it’s the process stops and goes to the next element to perform the process for the next element. After last process in last rotation the sub stops working and produces a shorted array.
But how does the sub stop and how does it assume that it is the last process of last rotation.
I did it by a small control flow into the sub.
Here element number is in consideration, from where we could calculate the rotation number. And after last rotation we could stop the sub.
Here I take a Static variable to store the rotation number.
The codes are

        Static round As Integer = 0     'A static variable to hold the number of
        'rotation from lowwer bound of array to upperbound of array

        If i >= num.GetUpperBound(0) Then
            i = 0

            round += 1

            'If rotation reaches to the upper bound of Array then exit from sub
            If round >= num.GetUpperBound(0) Then
                Exit Sub
            End If
        End If

When “i”, the element number reaches to the last element, reset the value of ‘i” to 0 to start the process from the first..
i=0
and increment 1 to the rotation number.
Here “round” is the variable for counting the rotation.
So.
round += 1
When “round” reaches to the upper bound of the array then exit from sub.

            If round >= num.GetUpperBound(0) Then
                Exit Sub
            End If

Now, when do we call the sub recursively?
In the comparison process after each comparison and swapping the values between them we call the sub recursively to perform the next comparison.
The comparison process is

        If num(i) > num(i + 1) Then
            temp = num(i)
            num(i) = num(i + 1)
            num(i + 1) = temp

            'After every swaping call the procedure
            Me.TryToShort(num, i + 1)

        Else
            'If the value of an array element is
            'less or equel to the next array element
            'call the procedure

            Me.TryToShort(num, i + 1)
        End If

Here, temp is a variable to store the element value temporarily.

Project design :
Here I take a form with two listboxes, one textbox and four buttons. The design is the following.
d66445aea01a405353692d7c775ff94e

NumTetxBox – to write the numbers
AddToListButton – to add the numbers to the listbox as like the order in the array.
NumListBox – to show the numbers, which entered first time.
ShortListBox – to show the shorted array elements.
ShortShowButton – to call the shorting sub..
ClearAllButton – to clear all values
CloseButton – to close the form.

The procedures and events.

Declaring Variables :

    Dim numArray(0) As Integer 'Declaring an array to hold the numbers and short them in request
    Dim numinc As Integer = 0       'To trac the increment of array  element

Initializing Controls, Variables :

    Private Sub TryToInitialize()
        'Try to clear all data from all controls and
        'Redimentioning the Array

        NumTextBox.Text = ""
        NumListBox.Items.Clear()
        ShortListBox.Items.Clear()

        numinc = 0
        ReDim numArray(numinc)


    End Sub

Form_Load event : to initialize first time

    Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load

        Me.TryToInitialize()

    End Sub

NumTextBox_KeyPress event : (This event is to restrict the input except digits, backspace and enter keys.)

    Private Sub NumTextBox_KeyPress(sender As Object, e As System.Windows.Forms.KeyPressEventArgs) Handles NumTextBox.KeyPress
        'Creating here a restriction for input
        'into the TextBox except Digits, backspace and enter/return keys
        Select Case e.KeyChar
            Case "0" To "9"                         'write digits 0-9 
            Case Chr(8)                             'remove digits by pressing backspace key
            Case Chr(13) : AddToListButton.PerformClick()   'Press Enter key to Perform the Button1 Click Event
            Case Else : e.Handled = True            'Restrict others key input
        End Select
    End Sub

AddToListButton_Click event : to add numbers to the listbox and array

    Private Sub AddToListButton_Click(sender As System.Object, e As System.EventArgs) Handles AddToListButton.Click

        If Not String.IsNullOrWhiteSpace(NumTextBox.Text) Then

            'Adding numerical value to the ListBox 
            NumListBox.Items.Add(NumTextBox.Text)

            'redimentioning the array by incrementing an element
            'and also try to preserve the previous stored values
            ReDim Preserve numArray(numinc)

            'Try to store value into the newly created Array element
            numArray(numinc) = CInt(Val(NumTextBox.Text))


            numinc += 1

        End If


        'After adding to list clear the text
        'and set focus to the textbox
        NumTextBox.Text = ""
        NumTextBox.Focus()
    End Sub

ShortShowButton_Click event : Short and show shorted element values

    Private Sub ShortShowButton_Click(sender As System.Object, e As System.EventArgs) Handles ShortShowButton.Click
        'Call the sub procedure to short the Array
        Me.TryToShort(numArray, 0)

        'TryToShort.TryToShort(numArray, 0)
        'Add and show the shorted numbers
        For n As Integer = 0 To numArray.GetUpperBound(0)
            ShortListBox.Items.Add(numArray(n))
        Next
    End Sub

ClearAllButton_Click event :

    Private Sub ClearAllButton_Click(sender As System.Object, e As System.EventArgs) Handles ClearAllButton.Click
        'Clear all previous data
        Me.TryToInitialize()
    End Sub

CloseButton_Click event :

    Private Sub CloseButton_Click(sender As System.Object, e As System.EventArgs) Handles CloseButton.Click
        'Close the form
        Me.Close()
        Me.Dispose()

    End Sub

TryToShort sub procedure : to short the array elements

    Private Sub TryToShort(ByVal num() As Integer, ByVal i As Integer)
        'Declare a temporary integer variable
        Dim temp As Integer


        Static round As Integer = 0     'A static variable to hold the number of
        'rotation from lowwer bound of array to upperbound of array

        If i >= num.GetUpperBound(0) Then
            i = 0

            round += 1

            'If rotation reaches to the upper bound of Array then exit from sub
            If round >= num.GetUpperBound(0) Then
                Exit Sub
            End If
        End If


        'Method to swaping the values from one 
        'array element to next
        If num(i) > num(i + 1) Then
            temp = num(i)
            num(i) = num(i + 1)
            num(i + 1) = temp

            'After every swaping call the procedure
            Me.TryToShort(num, i + 1)

        Else
            'If the value of an array element is
            'less or equel to the next array element
            'call the procedure

            Me.TryToShort(num, i + 1)
        End If

    End Sub

In this Sub Procedure we take two parameters one for the array and other for the element number. And when we call the sub to short the array we pass the Main Array , where we stored the values, entirely as argument value.
After completion of shorting process we get the result as follows.
7c8fad117a9e9eea0fae42602c84a30a

No Do Loop or For Loop is in use in the shorting process.

The entire project codification is as follows.
Thanks.

vb.net

Imports System

Public Class Form1


    Dim numArray(0) As Integer 'Declaring an array to hold the numbers and short them in request
    Dim numinc As Integer = 0       'To trac the increment of array  element

    Private Sub TryToInitialize()
        'Try to clear all data from all controls and
        'Redimentioning the Array

        NumTextBox.Text = ""
        NumListBox.Items.Clear()
        ShortListBox.Items.Clear()
        numinc = 0
        ReDim numArray(numinc)


    End Sub

    Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load

        Me.TryToInitialize()

    End Sub

    Private Sub NumTextBox_KeyPress(sender As Object, e As System.Windows.Forms.KeyPressEventArgs) Handles NumTextBox.KeyPress
        'Creating here a restriction for input
        'into the TextBox except Digits, backspace and enter/return keys
        Select Case e.KeyChar
            Case "0" To "9"                         'write digits 0-9 
            Case Chr(8)                             'remove digits by pressing backspace key
            Case Chr(13) : AddToListButton.PerformClick()   'Press Enter key to Perform the Button1 Click Event
            Case Else : e.Handled = True            'Restrict others key input
        End Select
    End Sub

    Private Sub AddToListButton_Click(sender As System.Object, e As System.EventArgs) Handles AddToListButton.Click

        If Not String.IsNullOrWhiteSpace(NumTextBox.Text) Then

            'Adding numerical value to the ListBox 
            NumListBox.Items.Add(NumTextBox.Text)

            'redimentioning the array by incrementing an element
            'and also try to preserve the previous stored values
            ReDim Preserve numArray(numinc)

            'Try to store value into the newly created Array element
            numArray(numinc) = CInt(Val(NumTextBox.Text))


            numinc += 1

        End If


        'After adding to list clear the text
        'and set focus to the textbox
        NumTextBox.Text = ""
        NumTextBox.Focus()
    End Sub

    Private Sub ShortShowButton_Click(sender As System.Object, e As System.EventArgs) Handles ShortShowButton.Click
        'Call the sub procedure to short the Array
        Me.TryToShort(numArray, 0)

        'TryToShort.TryToShort(numArray, 0)
        'Add and show the shorted numbers
        For n As Integer = 0 To numArray.GetUpperBound(0)
            ShortListBox.Items.Add(numArray(n))
        Next
    End Sub

    Private Sub ClearAllButton_Click(sender As System.Object, e As System.EventArgs) Handles ClearAllButton.Click
        'Clear all previous data
        Me.TryToInitialize()
    End Sub

    Private Sub CloseButton_Click(sender As System.Object, e As System.EventArgs) Handles CloseButton.Click
        'Close the form
        Me.Close()
        Me.Dispose()

    End Sub


    Private Sub TryToShort(ByVal num() As Integer, ByVal i As Integer)
        'Declare a temporary integer variable
        Dim temp As Integer


        Static round As Integer = 0     'A static variable to hold the number of
        'rotation from lowwer bound of array to upperbound of array

        If i >= num.GetUpperBound(0) Then
            i = 0

            round += 1

            'If rotation reaches to the upper bound of Array then exit from sub
            If round >= num.GetUpperBound(0) Then
                Exit Sub
            End If
        End If


        'Method to swaping the values from one 
        'array element to next
        If num(i) > num(i + 1) Then
            temp = num(i)
            num(i) = num(i + 1)
            num(i + 1) = temp

            'After every swaping call the procedure
            Me.TryToShort(num, i + 1)

        Else
            'If the value of an array element is
            'less or equel to the next array element
            'call the procedure

            Me.TryToShort(num, i + 1)
        End If

    End Sub

    
End Class

J.C. SolvoTerra 109 Eat, Sleep, Code, Repeat

9 Years Ago

I'm really confused by this, by Short do you mean sort, and if you mean sort, can't you just do this

Dim iVals As Integer() = {1, 9, 3, 10, 6, 2, 8, 5, 7, 4}
Array.Sort(iVals)

If you wanted to reverse the sort order

Public Class ReverseComparer : Implements IComparer
    Function Compare(x As Object, y As Object) As Integer _
            Implements IComparer.Compare
        Return New CaseInsensitiveComparer().Compare(y, x)
    End Function
End Class

'Button Click Event

Dim RC As New ReverseComparer

Dim iVals As Integer() = {1, 9, 3, 6, 2, 10, 15}
Array.Sort(iVals, RC)

Display the results

For Each Val As Integer In iVals
    Console.WriteLine(Val)
Next

Santanu.Das 125 Santanu Das

9 Years Ago

I am really very sorry J. C. for my misspelling of the word “Sort”. I am also grateful to you to draw the attention about mistake.
Thank you so much J.C.
At the preface I already wrote that there are too many methods and process to sort an array. You can like and use any one of them. Here, seeing the post in CodeProject, I got an conception and an idea came with me , Why not can I use this conception in vb? I did it as a practice job. And after completion I tried to share this conception with my every DaniWeb friends. This is nothing to grow a conception about sorting an array and also recursion.

Without recursion, it can be done by the use of ‘GoTo’ Statement. I did it, where I declared the Array as Double Type. The snippet is following.

    Private Sub TryToShort(ByVal num() As Double)

        Dim temp As Double
        Dim round As Double = 0.0#
        Dim i As Double = 0

ShortElement:

        If i >= num.GetUpperBound(0) Then
            i = 0
            round += 1
            If round >= num.GetUpperBound(0) Then
                Exit Sub
            End If
        End If

        If num(i) > num(i + 1) Then
            temp = num(i)
            num(i) = num(i + 1)
            num(i + 1) = temp
            i += 1
            GoTo ShortElement
        Else
            i += 1
            GoTo ShortElement
        End If

    End Sub

Here, I try to show, how does 'GoTo' statement work.

Reverend Jim 4,780 Hi, I'm Jim, one of DaniWeb's moderators.

9 Years Ago

There are very few cases where a GOTO is acceptable. This is not one of them.

ddanbe commented: I NEVER GOTO +15

kplcjl 17 Junior Poster

9 Years Ago

JC: There are articles galore about sorting routines because people are interested in how they work. My gripe is that the authors pick the bubble sort because it is the easiest one to code. That is an N^2 routine. This is a shortened loop because it uses ((N+1) X N)/2 loops so it basically executes half as many loops. It is still N^2 because if you double the size, you quadruple the time it takes which is the characteristic of N^2. I agree with you that if you want to sort, Array.Sort() is the way to go. I wrote an article http://www.codeproject.com/Articles/632556/Another-article-about-big-O-notation that has a routine that just about matches Array.Sort() in expected performance, but the built-in one consistently takes about 2/3 the time my routine does. So for practical reasons never use my routine to sort. 150 million items takes about 49 seconds for my routine to sort. The bubble sort takes about 3 minutes to sort 150 thousand items. The predicted time for bubble sorting 150 million items is 3 million minutes because it is 1000 times bigger, so it would take a million times as long. (There are 1,440 minutes in a day, so over 280 years, using actual times it was still over 270 years)
The complaint about the GOTO statements is valid, read up on articles that explain why the use of GOTO statements are bad. I learned coding in the spaggetii code era, it took me a while to figure that (goto==bad) out too.

David_50 13 Junior Poster in Training

9 Years Ago

I wrote a strings merge sort as a way to optimize cache hits: Consider a container of N objects to contain N sorted strings of objects of length one, which you build as you read input. Read two and insert into the first two elements of an array of containers. Merge the first 2 and save a sorted object container of 2 items at array position 0. Read the next two to positions 1 and 2, merge them into 1, and now merge 0 and 1 into 0. Use the binary counter bits of the count of items read to decide whether to merge after a read, and how many merges. Every count with the low order bits zero says merge for each low order bit, for instance twice at count 4, three times at count 8.

Because the sort uses the smallest possible, most recently used sets first, it has a high hit rate on the fastest caches first, then on the lower cache, the RAM DRAM rows and pages before using the VM = disk.

The only drawback I found is that it is more efficient to merge at disk speed more than 2 streams at once. To do this, normally you need a tournament tree of top items off each stream to identify which to take next. I want to create a pipeline tree of N threads to merge strings, like for 16 at once, 8 first level merges feeding 4 second level, 2 third level and one final = 15 merge processes. Thus 16 strings are read at once and merged before being stored.

However, life in the real world is tricky. What if the file final count is an odd number? You might be merging 20 items into 2 billion in two streams beacuse of the item count. I believe that old sorts counted the input items or first pass strings, and arranged the merge sequence so the final merge was always N to 1, by having odd lots early, so for 12345678 items, 16 ways, the prior pass needs to be 771604+, 48225+, 3014+, 188+, 11+ items per string. I can see a lot of fiddly bits in code to know how to build shorter strings of sorted items after the first pass. That's why we use theirs, not writing our own.

Alos in real life, sometimes the input flows at you slowly, so it would be nice to be preparing a sorted output as you wait for the final item, so once you get input EOF, you can immediately start writing output. Sorting by putting the data into a tree in VM has this potential low latency, even though placing the last item in a huge sorted set seems expensive. At least with a tree sort, the lower branches of the tree are in cache or RAM. However, the page churn is a bit worse with items in the set being modified somewhat randomly.

You might profit by using some sort of invariant, sparse-tolerant tree. For instance, a node of the tree might be 256 pointers in an array, to digest one byte of key. If the pointer is null, hang our item there. If it is occupied by an item, put a node pointer there that carries the new and old item. If it is a node, use the next byte to address that array. Alternate nodes could say 4 (N) bytes must equal "axcy" (fixed string), to span dull parts of the key. Or have a short array and a key string to the byte values supported, or a range array where N values start with 'M', great for digits. Since the tree is sparse and invariant, it can accept new items with low tree churn. I call it the C-tree for 'character' tree. It meshes well with the programming data types and CPUs.

Edited 9 Years Ago by David_50

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.