This code shows how to use a minimum Windows Gui program to display the results of a bubble sort of an integer array.
A simple Bubble Sort
// sorting an integer array's values in ascending order
// a Windows GUI program with a button and label
// compiled with C:\Windows\Microsoft.NET\Framework\v2.0.50727\csc.exe
using System;
using System.Windows.Forms; // GUI stuff
namespace BubbleSorterSpace
{
public class BubbleSorter : System.Windows.Forms.Form
{
private System.Windows.Forms.Button sortButton;
private System.Windows.Forms.Label resultLabel;
// required designer variable
private System.ComponentModel.Container components = null;
public BubbleSorter()
{
// required for GUI support
InitializeComponent();
}
// clean up any resources being used
protected override void Dispose( bool disposing )
{
if ( disposing )
{
if (components != null)
{
components.Dispose();
}
}
base.Dispose( disposing );
}
private void InitializeComponent()
{
this.sortButton = new System.Windows.Forms.Button();
this.resultLabel = new System.Windows.Forms.Label();
this.SuspendLayout();
//
// sortButton
//
this.sortButton.Location = new System.Drawing.Point(109, 8);
this.sortButton.Name = "sortButton";
this.sortButton.TabIndex = 0;
this.sortButton.Text = "Sort Data";
this.sortButton.Click += new System.EventHandler(this.sortButton_Click);
//
// resultLabel
//
this.resultLabel.Location = new System.Drawing.Point(8, 40);
this.resultLabel.Name = "resultLabel";
this.resultLabel.Size = new System.Drawing.Size(280, 64);
this.resultLabel.TabIndex = 1;
//
// the Window Form
//
this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);
this.ClientSize = new System.Drawing.Size(292, 109);
this.Controls.AddRange(new System.Windows.Forms.Control[] {
this.resultLabel, this.sortButton});
this.Name = "bubbleSort";
this.Text = "C# bubble sort";
this.ResumeLayout(false);
}
static void Main()
{
Application.Run(new BubbleSorter());
}
private void sortButton_Click( object sender,
System.EventArgs e )
{
int[] ar = { 22, 6, 4, -7, 13, 12, 89, 68, 37, 44, -15 };
resultLabel.Text = "items in original order\n";
for ( int i = 0; i < ar.Length; i++ )
resultLabel.Text += " " + ar[ i ];
// sort items of array ar
BubbleSort( ar );
resultLabel.Text += "\n\nitems in ascending order\n";
for ( int i = 0; i < ar.Length; i++ )
resultLabel.Text += " " + ar[ i ];
}
// sort the items of an array using bubble sort
public void BubbleSort( int[] ar )
{
for ( int pass = 1; pass < ar.Length; pass++ )
for ( int i = 0; i < ar.Length - 1; i++ )
if ( ar[ i ] > ar[ i + 1 ] )
Swap( ar, i );
}
// swap two items of an array
public void Swap( int[] ar, int first )
{
int hold;
hold = ar[ first ];
ar[ first ] = ar[ first + 1 ];
ar[ first + 1 ] = hold;
}
}
}
Lardmeister 461 Posting Virtuoso
You can run these short C# snippets with the free GUI based
SnippetCompiler.exe
from:
http://www.sliver.com/dotnet/SnippetCompiler/
arfat32 0 Newbie Poster
Exellent Effort
hasnainhaider 0 Newbie Poster
Very Very Easy and Efficient approach to explain. Thanks!
kplcjl 17 Junior Poster
hasnain..., I agree it's a very easy approach. However, I say it is a very INefficient approach. In type O notation it is N^2 which is bad. I tried to show an alternate approach that in O notation is still N^2 but would still be twice as fast. There are alternate methods that aren't an easy approach but in O notation is logn. Dani made me lose my last post so I'll send a code only note later. (Have to rewrite it.) I estimated a million int array would take over an hour and 20 minutes on my machine so my alternate solution would take about 40 minutes. A logn process might take less than a minute. 100k array would finish a 100 times faster. So 50 seconds with his version and 25 with my (still bad) version.
kplcjl 17 Junior Poster
/// <summary>
/// Alternate version bubble sort
/// </summary>
/// <param name="ar">int array to be sorted</param>
public static void AltBubbleSort(int[] ar)
{
int endpoint = ar.Length - 1;
for (int i1 = 0; i1 < endpoint; i1++)
for (int i2 = i1 + 1; i2 <= endpoint; i2++)
if (ar[i1] > ar[i2])
Swap(ar, i1, i2);
}
/// <summary>
/// swap two items of an array
/// </summary>
/// <param name="ar">int[] array to work a swap</param>
/// <param name="i1">First of two positions to swap</param>
/// <param name="i2">Second position</param>
private static void Swap(int[] ar, int i1, int i2)
{
int hold = ar[i1];
ar[i1] = ar[i2];
ar[i2] = hold;
}
kplcjl 17 Junior Poster
/// <summary>
/// creates a random array of positive/negitive numbers of the specified size
/// </summary>
/// <param name="sizeArray">Size of the array to generate</param>
/// <returns>The created array</returns>
public static int[] GenRandVals(int sizeArray)
{
if (sizeArray <= 0) throw (new Exception(string.Format("GenRandVals(int sizeArray) called. sizeArray MUST be > 0. Value= {0} sent.", sizeArray)));
int[] vals = new int[sizeArray];
int range = int.MaxValue, diff = range / 2;
Random rand = new Random();
for (int i = 0; i < sizeArray; i++)
vals[i] = rand.Next(range) - diff;
return vals;
}
/// <summary>
/// copies values from one array into another one
/// </summary>
/// <param name="ar">The array to be copied</param>
/// <returns>copied array</returns>
public static int[] CopyArray(int[] ar)
{
int len = ar.Length;
int[] Cpy = new int[len];
for (int i = 0; i < len; i++)
Cpy[i] = ar[i];
return Cpy;
}
static void Main(string[] args)
{
DateTime start = DateTime.Now;
int arraySize = 200000, loc = 0;
int[] testArray1 = GenRandVals(arraySize), testArray2 = CopyArray(testArray1), testArray3 = CopyArray(testArray1);
TimeSpan span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format("Time to generate and copy two arrays: {0} of size: {1}", span.ToString(), arraySize));
start = DateTime.Now;
BubbleSort(testArray1);
span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format("Time to run original BubbleSort: {0}", span.ToString()));
start = DateTime.Now;
AltBubbleSort(testArray2);
span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format("Time to run alternate version of BubbleSort: {0}", span.ToString()));
Console.WriteLine(string.Format("nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: {0}/{1}/{2} Location {3}",
testArray1[loc], testArray2[loc], testArray3[loc],loc));
loc = arraySize - 1;
Console.WriteLine(string.Format("nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: {0}/{1}/{2} Location {3}",
testArray1[loc], testArray2[loc], testArray3[loc], loc));
loc = arraySize / 2;
Console.WriteLine(string.Format("nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: {0}/{1}/{2} Location {3}",
testArray1[loc], testArray2[loc], testArray3[loc], loc));
start = DateTime.Now;
}
kplcjl 17 Junior Poster
Time to generate and copy two arrays: 00:00:00.0060004 of size: 100000
Time to run original BubbleSort: 00:00:30.8487644
Time to run alternate version of BubbleSort: 00:00:22.8873090
nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: -1073710058/-1073710058/-211269798 Location 0
nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: 1073739711/1073739711/-859760482 Location 99999
nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: 2103826/2103826/-203978619 Location 50000
Time to generate and copy two arrays: 00:00:00.0060004 of size: 100000
Time to run original BubbleSort: 00:00:30.7497588
Time to run alternate version of BubbleSort: 00:00:22.7653021
nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: -1073641870/-1073641870/333869880 Location 0
nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: 1073714370/1073714370/298019800 Location 99999
nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: -5930808/-5930808/222613449 Location 50000
Doubling the size of the array should quadruple times:
Time to generate and copy two arrays: 00:00:00.0120007 of size: 200000
Time to run original BubbleSort: 00:02:11.1024987
Time to run alternate version of BubbleSort: 00:01:33.2273323
nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: -1073728914/-1073728914/24513230 Location 0
nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: 1073740987/1073740987/-516876871 Location 199999
nOrig/nAlt/nOrig loc. Values of both versions of BubbleSort with orig: 1911366/1911366/-497207514 Location 100000
kplcjl 17 Junior Poster
I said it was an inefficient sort. It took me a while to figure out the logic because it isn't an easy approach.
I knew it was an efficient sort, but I have to admit to being blown away by how fast it is.
Here are the results for the binary sort method: (After I tweaked out the bugs I wrote into it.)
I just had to move the 200K sort result to the front. (Remember, over two minutes for the original bubble sort):
Time to run binary Sort logic: 00:00:00.0468001
Time to generate and copy two arrays: 00:00:00.0156000 of size: 10000
Time to run original BubbleSort: 00:00:00.3276006
Time to run alternate BubbleSort logic: 00:00:00.2496004
Time to run binary Sort logic: 00:00:00
4987 Values were moved earlier in the array, 5009 were moved later 4 didn't move.
Time to generate and copy two arrays: 00:00:00 of size: 10000
Time to run original BubbleSort: 00:00:00.3432006
Time to run alternate BubbleSort logic: 00:00:00.2340004
Time to run binary Sort logic: 00:00:00.0156000
4966 Values were moved earlier in the array, 5034 were moved later 0 didn't move.
Time to generate and copy two arrays: 00:00:00 of size: 200000
Time to run original BubbleSort: 00:02:20.8994457
Time to run alternate BubbleSort logic: 00:01:37.8277706
Time to run binary Sort logic: 00:00:00.0468001
99997 Values were moved earlier in the array, 100002 were moved later 1 didn't move.
Since I seem to have trouble posting code and text together, the code follows. Warning, the code is NOT an easy read.
kplcjl 17 Junior Poster
/// <summary>
/// Binary sort method with custom modifications. Recursive code splits array hopefully in half
/// and calls each half to sort them.
/// </summary>
/// <param name="ar">int array to be sorted</param>
/// <param name="start">Starting index location in the array to be sorted</param>
/// <param name="end">Ending index location</param>
public static void BinSort(int[] ar, int start, int end)
{
int middle, middlel, middlevalue, hold, left, right, swapl, swapr;
if (start > end)
{
hold = start;
start = end;
end = hold;
}
if (start < 0) start = 0;
if (end >= ar.Length) end = ar.Length - 1;
middle = (start + end) / 2;
left = middle - 1;
right = middle + 1;
if (ar[start] > ar[end]) Swap(ar, start, end);
if (ar[middle] > ar[start] && ar[middle] > ar[end]) Swap(ar, middle, end);
else if (ar[middle] < ar[start] && ar[middle] < ar[end]) Swap(ar, middle, start);
middlel = middle;
middlevalue = ar[middle];
//left moves lower, right moves higher. middlel/middle point to the middle value(s) that won't be sorted when this finishes
//start end don't change from this point forward
bool finished = false;
while (!finished)
{
while (left >= start && ar[left] < middlevalue) left--;
while (right <= end && ar[right] > middlevalue) right++;
if (left >= start && ar[left] == middlevalue) Swap(ar, left--, --middlel);
if (right <= end && ar[right] == middlevalue) Swap(ar, right++, ++middle);
if ((left >= start && ar[left] > middlevalue) && (right <= end && ar[right] < middlevalue))
Swap(ar, left--, right++);
if (left < start)
{
if (right <= end && ar[right] < middlevalue)
{//need to move the value on the right to the left side
Swap(ar, middlel, ++middle);//Move what used to be to right of the middle value to the left
if (right != middle)//after the right is moved to the left both pointers are shifted right
Swap(ar, right, middlel++);
else middlel++;
right++;
}
if (right > end) finished = true;
}
else if (right > end)
{
if (left >= start && ar[left] > middlevalue)
{
Swap(ar, middle, --middlel);
if (left != middlel) Swap(ar, left, middle--);
else middle--;
left--;
}
if (left < start) finished = true;
}
}
if (middlel - start > 1) BinSort(ar, start, --middlel);
else if (ar[middlel] < ar[start]) Swap(ar, middlel, start);
if (end - middle > 1) BinSort(ar, ++middle, end);
else if (ar[middle] > ar[end]) Swap(ar, middle, end);
}
kplcjl 17 Junior Poster
OK, I said that sorting using the method I suggested as an efficient method of sorting that should be logn. I then got the perception it was running at N efficiency. That was my mistake, after reviewing the numbers, I realized it really is working at logn, just that as you increase the numbers, logn begins to look just like N. For instance increasing the size from 100 to 150 million items with N, the time should increase by 1.5 times. With logn, it should increase by 1.533 times, when it actually increased by 1.522 times. The lower numbers should show more dramatic changes, for instance sorting 100 items should take 20 times as long as sorting 10 items. 0 milliseconds times 20 is still 0 milliseconds. The first time I could measure time was at 10K and at 2 milliseconds, it was in no way an accurate measure. Going from 100K to 1M should take 12 times as long and it increased exactly 12 times. This sort method is definitely logn and bubble is definitely N^2. (N^2 quadruples the time when the number doubles. 100K sorts in over 30 seconds and 200K sorts in over 2 minutes with a bubble sort. The binary sort will sort 100M items in over 30 seconds, 150M >46 seconds. I don't have the memory to do 200M.)
Momerath 1,327 Nearly a Senior Poster Featured Poster
Ln 100,000,000 = 18.42068
Ln 150,000,000 = 18.82615
It should have increased 2%, not 1.522 times (52%).
kplcjl 17 Junior Poster
Sorry, you're right, but my numbers weren't off. I said the expected increase should be 1.533 and said actual increase was 1.522. Those are not percentages, those are expected rate of increase vs. actual.
Expected increases are nLn, not straight Ln, So the numbers are 1.5 e718.826 vs 1.0 e718.421
18.82615/18.420681.5 == 1.533017510754217542457716001798 (1.5 e7/1.0 e7 == 1.5) Considering the variance of luck included in the algorithm those are close enough to call them even. Going from 100K to 1M the expected rate should be 12 times higher. The first one took 19 milliseconds, so expected is 228 milliseconds and actual was 228 ms.
kplcjl 17 Junior Poster
PS I didn't notice asterisks "*" were removed. My typing window suddenly went Italic at the second quote, the preview window shows everything including the asterisk in the quote. When I posted, it was gone. You need to imagine asterisks in the above note.
kplcjl 17 Junior Poster
Arrg, paired asterisks denotes Italic so just before it goes in or out of Italic, imagine the asterisk.
Playing around with double ** asterisks. Ahh ** bold in typing, shows in preview.
kplcjl 17 Junior Poster
By the way, Big O notation on the web makes a big deal about the log you should use, which, according to what I've read should be the natural log. Which is total BS. I got completely different log numbers than you did because my log numbers were base 10, but the ratios exactly matched because a logarithm IS a log, which IS a log. Why I used base 10 is because it is extremely easy for me to calculate what the log of 10,000 is(4) or 100,000,000(8) in my head. 150,000,000 in my head isn't so easy, so I used my calculator which can also give me natural logn numbers. IE
8.17609... divide by 8 multiply by 1.5 voila 1.533017... Which gets into precision which is why I kept it to 4 places when the actual numbers only matched to 2 places.
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.