Bubble sort algorithm

33
63



See complete series on sorting algorithms here:

This series is in progress, we will be adding lessons into this series every week.
In this lesson, we have described Bubble sort algorithm and analyzed its time complexity.
Series on Time Complexity:

Subscribe to our channel to get updates on new lessons.

You may also like us on Facebook:

Nguồn:https://quydinh.com/

33 COMMENTS

  1. I get that this is very old now but surely the time expression is cn^2-2cn+c rather than cn^2-2cn+1. Anyway, was helpful thanks.

  2. I want solutions for below given problem, kindly help:

    1- Why are we interested in worst case analysis?

    2- What do you understand by rate of growth or order of growth? Why it is important in analysis of an algorithm?

    3- For following set of functions, indicate whether f = O(g), f = Ω(g), or both.

    1) f(n) = n − 10, g(n) = n + 10

    2) f(n) = 10n^2, g(n) = 3n^3 + n^2

    4- For f(n) = n^2 + 2n^3 − 100nlogn + 10, provide the simplest possible function g(n) such that f(n) = Θ(g(n)).

    5- Show that n log n is O(n^2) but that n^2 is not O(nlogn).

    6- Prove or disprove the following: √n = O(logn)

    7- Use a recursion tree to determine a good asymptotic upper bound on the following recurrences.

    1) T(n) = 2T(n − 1) + 1

    2) T(n) = 4T(n/2) + cn

    8- Consider the recursive binary search algorithm for finding a number in a sorted array.

    (a) Give recurrence for the worst-case running times of binary search algorithm.

    (b) Use a recursion tree to determine a good asymptotic bound for the recurrence tree.

    9- The ternary search algorithm locates an element in a list of increasing integers by successively splitting the list into three sub lists of equal (or as close to equal as possible) size, and restricting the search to the appropriate piece.

    (a) Give recurrence for the worst-case running time of the algorithm.

    (b) Use a recursion tree to determine a good asymptotic bound for the recurrence tree.

    10- Provide recurrence relation and a tight asymptotic bound for the following code.

    long power ( long x , long n )

    if ( n == 0 )

    return 1;

    else

    return x * power ( x , n−1);

  3. I Enjoy Coding Sorting Algorithms, It maes me smart and dumb at the same time… hehehe… I've encounter this Javascript library that use sorting algorithms for sorting complex objects and array… it helps me a lot on my projects
    https://www.npmjs.com/package/ainsort

  4. Sir, in best case analysis, the inner for loop runs (n-1 ) time and outer pass loop runs only 1 time. But you said inner loop runs once?

  5. I am new to programing..
    this is the code i wrote based on your algorithm
    var arr=[11,5,4,12,1,3,2,8,6,7,9,10]

    let k=arr.length-1

    function sort(){

    for(var i=0;i<arr.length;i++){

    var count=0

    for(var j=0;j<k;j++){

    count=count+1

    // console.log(arr[j])

    if(arr[j]>arr[count]){

    let b=arr[count]

    arr[count]=arr[j]

    arr[j]=b

    }

    if(j===k-1){

    k=k-1

    }

    }

    }

    console.log(arr)

    }

    sort()
    this is JavaScript ha ha
    just check this code is the code for bubble sort algorithm

  6. Thank you for your video. It is helpful. Please improve – the best case mark omega Ω(n) character not big O(n). On 9:38 video time.

  7. I think outer loop shouldn't start with one because if k won't be starting at zero then the inner loop will go only n-k-1 i.e if k = 1 it'll go up to n-2 times if there's a small variable at the end of the array then it won't be able to reach the end to compare as it'll end one before the last one. For example this below code :
    // bubble – sort

    class BubSort{

    void sorting(int A[],int n){

    for(int k = 1 ; k < n – 1 ; k + + ) {

    boolean flag = false;

    for (int i = 0 ; i < n – k – 1 ; i + + ) {

    if (A [ i ] > A [ i + 1 ] ) {

    int temp = A [ i + 1 ] ;

    A [ i + 1 ] = A [ i ] ;

    A [ i ] = temp;

    flag = true;

    }

    }

    if (flag == false) break;

    }

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

    System.out.println(A [ i ] ) ;
    }

    }

    public static void main(String…ssg){

    int A[] = {42,23,54,76,23,6,34,8,4,2,3,1};

    BubSort b1 = new BubSort();

    b1.sorting(A,A.length);

    }

    }
    output – 2 3 4 6 8 23 23 34 42 54 76 1

  8. If im not wrong sir, I believe you are trying to call an external swap() function in this code, and in that case a default call by value does not work, I think you should pass the values by reference, for the actual array to be sorted within the main() function. Hence it should be swap(&a[I],&a[I+1]).

  9. Bubble Sort
    1.Comparision Based Algo
    2.Time Complexity
    Best=O(n)
    Average=O(n^2)
    Worst=O(n^2)
    3.In-Place Algo
    4.Stable
    5.Non Recursive Algo
    6.Offline Algo

LEAVE A REPLY

Please enter your comment!
Please enter your name here