CODEWITHSUNDEEP
c#sorting
Xdrone
Xdrone

Reputation: 801

Bubble sort using while loop. Last sort not present in the output

I am attempting to create a bubble sort using while. I have posted my class below. Why in the sort the last int of 9 is not displayed.

namespace BubbleSort {
    class Program
    {
        static void Main(string[] args)
        {
            int[] i = {9, 2, 7, 6, 1, 3, 5, 4, 8};
            int va = 0, vb = 0;

            //loop through all numbers in the array.
            while (va < i.Length)
            {
                //loop through all numbers in the array trailing the first loop by 1.
                while (vb < i.Length)
                {
                    //compare the two values.
                    if (i[vb] < i[va]) {
                        Console.WriteLine(vb);
                    }                    
                    vb++; //increment
                }                 
                va++; //increment
            }
            Console.ReadLine();
        }
    }
}

Is this approach correct?

Upvotes: 1

Views: 18424

Answers (5)

Bob Vale
Bob Vale

Reputation: 18474

No thats not a bubble sort, additionally you are outputting the index of the array and not the value. See Wikipedia fo an explaination

You want something more like:

   int[] i = {9, 2, 7, 6, 1, 3, 5, 4, 8};
   int va = 0;

   bool swapped = true;

   while (swapped) {

     swapped=false;
     va = 0;
  //loop through all numbers in the array.
   while (va < i.Length -1)
   {
          //compare the two values.
           if (i[va] > i[va+1]) {

               int swap = i[va];
               i[va] = i[va+1];
               i[va+1] = swap;
               swapped=true;
           }

       //increment
       va++;  
   }
}

Then i will be sorted.

Btw this is sub optimal, you can use the nth pass optimisation and for loops for a better algorithm

A more optimised version with a for loop could be

int[] i = {9, 2, 7, 6, 1, 3, 5, 4, 8};

int n = i.Length -1;
bool swapped = true;

for (int n = i.Length - 1; swapped && n > 0; n--) {
  swapped = false;
  for (int va=0; va < n; va++) {
      if (i[va] > i[va+1]) {
           int swap = i[va];
           i[va] = i[va+1];
           i[va+1] = swap;
           swapped=true;
      }
   }
}

Upvotes: 3

Janne Matikainen
Janne Matikainen

Reputation: 5121

public static void BubbleSort(int[] arr)
{
    for (int i = 0 ; i < arr.Length; i++)
    {
        for (int j = i + 1 ;  j< arr.Length; j++)
        {
            if (arr[i] > arr[j])
            {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }

    Console.WriteLine(String.Join(", ", arr));
}

Upvotes: 0

Dan Puzey
Dan Puzey

Reputation: 34218

In short, no. You're not actually sorting anything. Here's what happens in your code:

  • You set va and vb to zero and enter your two while loops
  • The first iteration of the inner loop compares i[0] to each value in the array
  • i[vb] < i[va] returns false for when vb == 0 (because 9 is not less than 9) so displays nothing
  • vb is incremented
  • the remainder of the inner loop completes. Since every other value in the array is less than 9, they all output a value, but the value you output is actually vb NOT a value from the array. Your loop goes from 0 to 8 and you skip the first value because it's the highest in the array - therefore you output numbers 1 to 8 in the inner loop.
  • the inner loop completes with vb set to 9
  • your outer loop increments va and repeats
  • vb is still set to 9 and so the inner loop is entirely skipped
  • the above two steps repeat until va reaches 9, at which point the code completes.

If you use a different array as your input, you'll see that you get a totally different result. For example, if you remove the 9 from the front of the array, you only get 3 as an output (because only i[3] is less than the first value of 2). If you pad your array with three zero values, you'll actually get 9, 10 and 11 in the output, because you are outputting the counter/index value instead of the actual sorted value.

Upvotes: 2

oerkelens
oerkelens

Reputation: 5161

This is not bubble sort indeed. Bubble sort uses several passes, changing the positions of items in the list to be sorted. You just go through your list and pick out the smallets value at every loop.

To answer your question:

i[vb] < i[va]

i[0] is 9. It is never smaller than any of your other entries, so it never gets printed.

EDIT

Dang, yes. The index is being printed. Interestingly, i do not see vb being reset at any time to 0?? Well, let's say i am confused as to why anyone would think this is a sorting algorithm :)

Upvotes: 0

Yv&#225;n Ecarri
Yv&#225;n Ecarri

Reputation: 1738

No, its not.

1) Violation of the "S" principle: a class that implements bobble sort should not write to console.

http://es.wikipedia.org/wiki/SOLID_(object-oriented_design)

2) Your nested while loop only prints some numbers, it does not sort anything at all.

http://en.wikipedia.org/wiki/Bubble_sort

Upvotes: 1

Related Questions