Sorting Algorithm

[Robir]

I need to sort a list of integers (with associated text values) in ascending
order.
The input would look like this:

25 Jim
75 Ellen
15 Bob
497 Steve
23 Doris

The output needs to look like this
1 Bob
2 Doris
3 Jim
4 Ellen
5 Steve

So, three things need to happen to the input in order to create the desired
output:
(1) the integers need to be sorted in ascending order.
(2) the integers need to be re-numbered so there are no "gaps" between
values (e.g., input 15/Bob becomes output 1/Bob)
(3) the new output integer values need to remain associated with their
original input text.

The largest input integer value is 9999. The lowest input value is 1 (any
input value < 1 must be ignored).

Suggestions for accomplishing this will be greatly appreciated.

Robir

 

[Marina]

Where is this data coming from? If a database, you can do the sort right in
your query. Then select your data into a datatable, and manually, using a
for loop, renumber everything.

If it's already in a datatable, you can create a dataview with the
appropriate sort. Then, accessing the data through the dataview, renumber
everything. The original datatable will still have the rows in the original
order, but the dataview will always provide a sorted view.

 

[Vanessa]

Here is a sort routine

using System;
using System.Collections;

namespace Sort
{
public class Sort
{
public static int[ ] integers(int [ ] arg1)
{
int I2 = arg1.Length, I3 = I2;
int temp1;
while ((I2 = I2 / 2) != 0)
{
int I4 = I3 - I2, I5 = 0;
do
{
int I6 = I5;
do
{
int I7 = I6 + I2;
if (arg1[I6] > arg1[I7])
break;
temp1 = arg1[I6];arg1[I6]=arg1[I7];arg1[I7]=temp1;
I6 = I6 - I2;
}
while (I6 > 1);
I5 = I5 + 1;
}
while (I5 < I4);
}
return arg1;
}
}
}

 

[Robir]

Great idea - but the data is not coming in from a database. Rather, I'm
pulling it out of the Form collection of an ASPX page on PostBack to the Web
server. That is, I'm looping through the controls in the Form collection to
get the values. The values are supplied by the user as they indicate the
order in which they want things to be sorted. The users enter their integer
sorting preferences in a number of textboxes (the number of which is
determined at runtime - with textboxes being rendered via a DataList. During
the looping through the Form collection, I can of course, be adding DataRow
objects to a DataTable - but that seems like a lot of overhead being that I
won't be submitting the DataSet to a Database. What I will be doing with the
sorted integer/string pairs is sending them in to a SQL Server database as
parameters to a stored procedure. The critical part is to remove the "gaps"
and any ties among the integers prior to updating the database.

Just looking for a less memory-intensive method than with a DataSet.

Robir

 

[Ignacio Machin \( .NET/ C# MVP \)]

Hi Robir,

Beside Marina's and Vanessa's comments this is something you can do:
1- Create a class or struct with two members:

class Data{
int number;
string val;
public string Value{ get{return val;} set{ val=value;} }
public int Number{ get{return number;} set{ number=value;} }
public Data(int, string )...
}

2- create an ArrayList with instances of the created classes

foreach( object o in request ...)
arraylist.Add( new Data( ... ) );

3- Use the class I provide below to sort it based on the Number property:
ClassSorter sorter = new ClassSorter( "Value" , SortByType.Property,
SortDirection.Ascending);

araylist.Sort( sorter);

4- Simply substitute the values
int index=0;
foreach(Data data in arraylist
data.Number = index++;

Finally this is the class I use to sort a list of any type using reflection,
if you have any doubt about it just let me know

//***************** This is the class to sort any kind of collection using
reflection ************//

public class ClassSorter: IComparer
{
protected string sortBy;
protected SortByType sortByType;
protected SortDirection sortDirection;


#region Constructors
public ClassSorter(string sortBy, SortByType sortByType, SortDirection
sortDirection)
{
this.sortBy = sortBy;
this.sortByType = sortByType;
this.sortDirection = sortDirection;
}
#endregion

int Compare( object x, object y, string comparer)
{
if ( comparer.IndexOf( ".") != -1 )
{
//split the string
string[] parts = comparer.Split( new char[]{ '.'} );
return Compare( x.GetType().GetProperty( parts[0]).GetValue(x, null) ,
y.GetType().GetProperty( parts[0]).GetValue(y, null) , parts[1]
);
}
else
{
IComparable icx, icy;
icx =
(IComparable)x.GetType().GetProperty( comparer).GetValue(x, null);
icy =
(IComparable)y.GetType().GetProperty( comparer).GetValue(y, null);

if ( x.GetType().GetProperty(comparer).PropertyType ==
typeof(System.String) )
{
icx = (IComparable) icx.ToString().ToUpper();
icy = (IComparable) icy.ToString().ToUpper();
}

if(this.sortDirection == SortDirection.Descending)
return icy.CompareTo(icx);
else
return icx.CompareTo(icy);
}

}

public int Compare(object x, object y)
{
return Compare( x, y, sortBy);
}

}

public enum SortByType
{
Method = 0,
Property = 1
}

public enum SortDirection
{
Ascending = 0,
Descending = 1
}


//***************** end of code ****************************/


Hope this help,

 

[Nicholas Paldino [.NET/C# MVP]]

Robir,

I would create a structure/class that holds the order, as well as the
value in it. If you go with a structure, I would implement the IComparer
interface (to reduce boxings) and implement that on a separate class. If
you go with a class, then I would implement the IComparable interface on the
class itself. The comparison routine would compare the number that the user
entered.

Finally, once you have an array of these items, I would pass it (as well
as the implementation of the IComparer interface, if there is one), to the
static Sort method on the Array class.

Hope this helps.

 

[Robir]

Thanks everyone - especially for the sample code; it will save me a huge
amount of time.

Robir