Bubble Sort C# giving an extra value

Question

I've tried to make a bubble sort algorithm but when I output the values sorted in order it gives me an extra value at the beginning and this value isn't in my array but I can't work out how to fix this.

For example when I run the program and my array is : 8, 3, 68, 74, 67, 82, 82, 18, 48, 53

The sorted values show: 60, 3, 8, 18, 48, 53, 67, 68, 74 ,82, 82

public static void Main(string[] args)
{
    int n = 10; //10 values in array
    Random r = new Random();

    int[] a; //array
    int temp;
    int i;
    a = new int[n + 1];
    a[0] = 1; //starts at 0

    for (i = 0; i <= n; i++) // set the array up
        a[i] = r.Next(1, 100); // + random numbers 

    for (i = 1; i <= n; i++)
        Console.WriteLine(a[i] + " "); // outputs the numbers of array

    Console.WriteLine();
    Console.ReadLine();

    for (i = 1; i <= n; i++)
    {
        for (int k = 1; k < a.Length - 1; k++) // n - 1 passes
        {
            if (a[k] > a[k + 1])
            {
                temp = a[k + 1]; //stores temporarily
                a[k + 1] = a[k];
                a[k] = temp;
            }
        }
    }

    Console.WriteLine("Array is sorted: ");
    foreach (int number in a) Console.Write(number + " ");
    Console.Read();
}

Answer 1

Here's what's happening:

1. You're initializing your array with 11 elements when you do this:

   int n = 10;  
   int[] a = new int[n + 1];  // n + 1 is 11, so this creates an 11-element array
   

2. Then when you populate the array, you loop from 0 to 10, populating all 11 indexes:

   for (i = 0; i <= n; i++)
   a[i] = r.Next(1, 100);`
   

3. When you sort the array, however, you ignore the first element (at index 0) because your loops always start with 1, for example:

   for (i = 1; i <= n; i++)
   {
       for (int k = 1; k < a.Length - 1; k++)
       {
           // Sort the elements here
       }
   }
   

4. But then at the very end, you output ALL the elements, so you get to see the first number that you were skipping during the sort:

   foreach (int number in a) Console.Write(number + " ");
   

---

To fix this, normally when looping through an array we start at index 0 and we loop while our index variable is less than the array length:

for (i = 0; i < a.Length; i++)

This will always ensure you iterate over each item in the array.