Sorting in Data Structure

Sorting : The process of arranging data or items in a specific order, typically in ascending or descending sequence

Bubble Sort : It is a comparison-based algorithm in which each pair of adjacent elements is compared, and the elements are swapped if they are in the wrong order. The largest elements "bubble up" to the end of the list with each pass.

Working of Bubble sort 

1. Step 1: Perform n-1 comparisons. The largest element moves to the last position (A[n]).

2. Step 2: Perform n-2 comparisons. The second largest moves to A[n-1].

3. Step 3: Perform n-3 comparisons. The third largest moves to A[n-2].

4. Continue this process...

5. Step n-1: Compare A[1] and A[2]. Now the list is sorted in increasing order.

 Algorithm of bubble sort

[Bubble Sort] BUBBLE [DATA, N]

Here DATA is an array with N elements. This algorithm sorts the elements in DATA. 
1. Repeat steps 2 and 3 for K = 1 to N-1
2. Set PTR := 1 [?pass pointer PTR.] 
3. Repeat while PTR <= N-K. [Executes pass.] 
    (a) IF DATA [PTR] > DATA [PTR + 1], then:
         Interchange DATA [PTR] and DATA [PTR + 1] 
         [End of IF structure] 
    (b) Set PTR := PTR + 1 
         [End of inner loop] 
         [End of step 1 outer loop]
4. Exit

Complexity of algorithm  
f (n) = (n-1) + (n-2) +...... + 2 + 1
        = `(n(n - 1))/2`
        = `n^2/2 + 0  (n)`
        = 0 (n²)
The time required to execute the bubble sort algorithm is proportional to n² where n is the number of input items.