# How to short an array by recursion

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 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. 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. 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
``````

``````    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

'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)
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. No Do Loop or For Loop is in use in the shorting process.

The entire project codification is as follows.
Thanks.

``````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

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

If Not String.IsNullOrWhiteSpace(NumTextBox.Text) Then

'Adding numerical value to the ListBox

'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)
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``````

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

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,595

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

ddanbe commented: I NEVER GOTO +15
kplcjl 17

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

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.

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.