Game development as an Art

Sato Game Dev

Code Exercises


Sorting - Bubble Sort


Source: Hacker rank

Consider the following version of Bubble Sort: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
for (int i = 0; i < n; i++) {
    // Track number of elements swapped during a single array traversal
    int numberOfSwaps = 0;
    
    for (int j = 0; j < n - 1; j++) {
        // Swap adjacent elements if they are in decreasing order
        if (a[j] > a[j + 1]) {
            swap(a[j], a[j + 1]);
            numberOfSwaps++;
        }
    }
    
    // If no elements were swapped during a traversal, array is sorted
    if (numberOfSwaps == 0) {
        break;
    }
}

Task

Given an array, a, of size n distinct elements, sort the array in ascending order using the Bubble Sort algorithm above. Once sorted, print the following 3 lines:
1.Array is sorted in numSwaps swaps.
where numSwaps is the number of swaps that took place.
2.First Element: firstElement
where firstElement is the first element in the sorted array.
3.Last Element: lastElement
where lastElement is the last element in the sorted array.
Hint: To complete this challenge, you will need to add a variable that keeps a running tally of all swaps that occur during execution.

Input Format

The first line contains an integer, n, denoting the number of elements in array a.
The second line contains n space-separated integers describing the respective values of a0, a1, ..., an-1.

Constraints

2 <= n <= 600
1 <= ai <= 2 x 10^6, where 0 <= i < n.

Output Format

Print the following three lines of output:
1.Array is sorted in numSwaps swaps.
where numSwaps is the number of swaps that took place.
2.First Element: firstElement
where firstElement is the first element in the sorted array.
3.Last Element: lastElement
where lastElement is the last element in the sorted array.

Sample Input 0

3
1 2 3

Sample Output 0

Array is sorted in 0 swaps.
First Element: 1
Last Element: 3

Explanation 0

The array is already sorted, so 0 swaps take place and we print the necessary 3 lines of output shown above.

Sample Input 1

3
3 2 1

Sample Output 1

Array is sorted in 3 swaps.
First Element: 1
Last Element: 3

Explanation 1

The array a=[3,2,1] is not sorted, so we perform the following 3 swaps:
1.[3,2,1] -> [2,3,1]
2.[2,3,1] -> [2,1,3]
3.[2,1,3] -> [1,2,3]
At this point the array is sorted and we print the necessary 3 lines of output shown above.

My solution:
C#:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sorting
{
    class Program
    {

        static void swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }

        static void bubleSort(int[] a)
        {
            int n = a.Length;
            int totalNumSwaps = 0;

            for (int i = 0; i < n; i++)
            {
                // Track number of elements swapped during a single array traversal
                int numberOfSwaps = 0;

                for (int j = 0; j < n - 1; j++)
                {
                    // Swap adjacent elements if they are in decreasing order
                    if (a[j] > a[j + 1])
                    {
                        swap(ref a[j], ref a[j + 1]);
                        numberOfSwaps++;
                        totalNumSwaps++;
                    }
                }

                // If no elements were swapped during a traversal, array is sorted
                if (numberOfSwaps == 0)
                {
                    break;
                }
            }
            Console.WriteLine("Array is sorted in " + totalNumSwaps + " swaps.");
            Console.WriteLine("First Element: {0}", a[0]);
            Console.WriteLine("Last Element: " + a[a.Length - 1]);
        }

        static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine());
            string[] a_temp = Console.ReadLine().Split(' ');
            int[] a = Array.ConvertAll(a_temp, Int32.Parse);
            // Write Your Code Here
            bubleSort(a);
            Console.ReadKey();
        }
    }
}