using System;

using System.Diagnostics;

public class Program

{

    public static void Main()

    {

        int max = 5000;

        int[] array = GenerateArray(max);

        Stopwatch stopWatch = new Stopwatch();

        stopWatch.Start();    

        BubbleSort(array);

        stopWatch.Stop();

        TimeSpan ts = stopWatch.Elapsed;

        Console.WriteLine("RunTime " + ts.Milliseconds + " Milliseconds");

        //PrintArray(array);

    }

    public static int[] GenerateArray(int length){

        int[] array = new int[length];

        Random rand = new Random();

        for(int i=0;i<length;i++){

            array[i] = rand.Next(length);

        }   

        return array;

    }

    public static int[] GenerateOrderedArray(int length){

        int[] array = new int[length];

        for(int i=0;i<length;i++){

            array[i] = i;

        }   

        return array;

    }

    public static int[] GenerateReverseOrderedArray(int length){

        int[] array = new int[length];

        for(int i=length-1; i>=0; i--){

            array[i] = i;

        }   

        return array;

    }

    public static void BubbleSort(int[] array){

    for (int e = array.Length-1; e >0; e--) {  

      for (int j = 0; j < e; j++) {

          if (array[j] > array[j + 1]) {

            Swap(array, j, j+1);

          }

       }

     }

    }

    public static void BubbleSort2(int[] array){

    for (int e = array.Length-1; e >0; e--) {  

        bool swapped = false;

      for (int j = 0; j < e; j++) {

          if (array[j] > array[j + 1]) {

            Swap(array, j, j+1);

            swapped = true;  

          }

       }

        if(!swapped) break;

     }

    }

    public static void Swap(int[] array, int i, int j){

        int tmp = array[j];

        array[j] = array[i];

        array[i] = tmp;

    }

    public static void PrintArray(int[] array){

        for (int j = 0; j < array.Length; j++) {

          Console.WriteLine(array[j]+" ");

        }

    }

}