Bubble Sort on Doubly Linked List
Given a doubly-linked list, then using the bubble sorting algorithm, we have to sort the unsorted given doubly-linked list.
We have to use one of the sorting algorithms, Bubble sort, to sort the doubly linked list.
Eg: Input: 5<->1<->4<->3<->2<->9<->8
- In the Linked List, we have given an unsorted element.
- We have to arrange the elements in ascending order with the help of a sorting algorithm.
- Here we are using a bubble sorting algorithm to reach the output for the problem statement.
Approach for Solving
We are using the same approach for what we use for Array data structure; we are going to keep track of adjacent elements; if it's found to be less than the present element then we have to swap both the elements. We will repeat the above approach until we arrange all the elements in the form of ascending order.
For better understanding just take an example for detailed knowledge for working code.
- Firstly, we are creating the linked list by calling the addNode function bypassing the data into it.
- Secondly, after completion of the Doubly Linked List.
- Thirdly, we call the print_DLL function to show the created Doubly Linked List.
- Fourthly, we call the bubble function for sorting the given Linked List.
- If head==null, then we have nothing to do, just return directly.
- If head!=null, we have to run a do-while loop until we have encountered the value of f==0 in the while check, which indicates that we have sorted all the elements.
- In the do-while loop, we declare two nodes ptr1 and ptr2, ptr1 assigned with head node, then ptr2 assigned as null, under do-while we have to iterate all the Linked List with conditional statements.
- Here ptr1 is used to transverse the linked list, and ptr2 is used to keep track until we move.
- In the condition statement if we find ptr1.data>ptr1.next.data, then we have to swap the element.
- At last, we have to call the print_DLL function to print the sorted, Doubly linked list.
- For the first we initialized f=0 and ptr1=head=1 and ptr2=null and ptr1.next=1!=null then we find ptr1.data>ptr1.next.data , then we swap the element, and also update the value of f=1, then shift ptr1.
- 1<->5<->4<->3<->2<->9<->8 '
- In the next step , we repeat step -1 ,ptr1=5 and ptr2=null , 5!=null ,then ptr1.data>ptr1.next.data then we swap , f=1 and shift ptr1.
- In the next step , we repeat step -1 , ptr1=5 and ptr2=null , 5!=null ,then ptr1.data>ptr1.next.data then we swap ,f=1 and shift ptr1.
- Now we have ptr1.data<ptr1.next.data, we shift ptr1
- Now we have ptr1=9 and pt2=null , f=1 , now ptr1.data>ptr1.next.data , then we shift the element.
- Now we have ptr1=9 and ptr1.next==ptr2.data==null , then we change ptr2=9 for the next iteration.
- This step-1 to 6 goes on repeat mode till we reach the value of f==0.
- We perform n-1+n-2+n-3+.......+3+2+1 total iteration to perform the bubble sort.
Note: - The main idea behind the value of f is that in bubble sort we have total n-1 passes for sorting the element, we are changing the value of f to 0 at the start as everything is sorted, but when we encounter some disorder, then we change it to 1. When at the end of n-1 the value of f remains to 0 after complete transversal then, in the last check while(f!=0) termination condition found where the value of f comes to 0, we go out of do-while and just done with our task for bubble sorting application over the doubly linked list.
Taking about the Time Complexity of the code is O(N^2) because for the first time we are performing n-1 iteration, in next we have n-2 iteration, we have n-3 iteration, we proceed (n-1)+(n-2)+(n-3)+....+3+2+1, total iteration, we have (n-1)*(n-1+1)/2 =(n-1)*n/2=n^2 times we have to iterate, where n is the number of nodes in the Linked List.
Now about Space Complexity, we are not using any other space other than constant time-space. We are doing operations on the same linked list. We are just using a constant variable of O(1) times for swapping elements. The Space Complexity is O(1).
Frequently Asked Question
- What is the Time Complexity and Space Complexity?
Time Complexity is O(N^2), and Space Complexity is O(1).
- What is Sorting?
Order data in an increasing or decreasing fashion according to some linear relationship among the data items.
- What is Bubble Sorting?
Bubble Sort is the most straightforward sorting algorithm that works by repeatedly swapping the adjacent elements.
- What is the Time and Space Complexity of the Bubble sort?
Best Time Complexity O(n), Average Time Complexity O(n^2), Worst Time Complexity O(n^2), Space Complexity O(1).
- When does Bubble sort have Time Complexity of O(n) and Space Complexity O(1)?
When the list is already sorted, we have a Time Complexity of O(n) on performing Bubble sort.
In this blog, we discuss the sorting algorithm; in the doubly linked list data structure, we understand the concept using the code and the Dry-Run. We came up with Bubble Sort complexity in different cases as Best Time Complexity O(n), Average Time Complexity O(n^2), Worst Time Complexity O(n^2), Space Complexity O(1). We discuss the Time and Space Complexity of sorting the doubly linked list as O(N^2) and O(1), respectively.