Since again p is greater than q, the values will be swapped again and p will again become p.ref. Since at this point of time, p is not equal to end, the loop will continue and now p will become 8 and q will become 1. At this point of time the linked list will look like this: 7,8,1,6,9 Since p is greater than q, the values will be swapped and p will become p.ref. In the first iteration, p will be set to 8, and q will be set to 7.
The purpose of the bubble sort is that during each iteration, the largest value should be pushed to the end, hence at the end of all iterations, the list will automatically be sorted.īefore the loop executes, the value of end is set to None. We'll see what will happen during each iteration. Let's implement our algorithm to sort the list. Let's understand this process with the help of an example. This process continues until the linked list is sorted. Finally, the end will be assigned the value of p. Then the values of p and q will be compared if p is greater than q the values of both the variables will be swapped and then p will point to p.ref, which is the next node. Inside the inner while loop, the value of q will be set to p.link which is actually the node next to q. Inside the outer while loop, the value of p will be set to self.start_node which is the first node. The inner while loop executes until p becomes equal to the end variable. The outer while loop executes until the value of variable end is equal to the self.start_node. To implement bubble sort, we need two while loops. It is important to remember that to sort the list with n elements using bubble sort, you need n-1 iterations. The variable p will be initialized with the start node, while end will be set to None. To sort a linked list by exchanging data, we need to declare three variables p, q, and end. We will use the bubble sort algorithm to first sort the linked list by changing the data, and then we will see how we can use bubble sort to change the links in order to sort the linked list. In this section, we will see how both these approaches work. There are two ways to sort a linked list using bubble sort:
Sort linked list how to#
In this article, we will continue from where we left in the last article and will see how to sort a linked list using bubble and merge sort, and how to merge two sorted linked lists.īefore we continue, it is imperative to mention that you should create Node and LinkedList classes that we created in the last article. Finally, we saw how to reverse a linked list.
We also studied some of the most commonly used linked list method such as traversal, insertion, deletion, searching, and counting an element. We saw what the linked list is along with its advantages and disadvantages. In the last article, we started our discussion about the linked list.
0 kommentar(er)
