(12-> 35->2->67) => (12->2->35->67) now 35>2 so we will swap the adjacent nodes and move our pointer at third node which is again 35. ( 12->35->2->67) => (12->35->2->67) as our pointer is pointing at 12(bolder part) and after comparing it with next node value we can see that 35>12 so we will not do anything just simply move our pointer point towards next node i.e, 35. Now we have to sort this list we have inserted the node values and now we start traversing the given list. If the current node value is smaller or equal to next node value we will move our pointer further and point it towards the next node but if the current node value is bigger as compared to the next node value then we will swap the nodes with each other and make our pointer point towards the next node or that node which is swapped recently and keep on performing these passes until we will get the sorted list.
Given a linked list and we have to sort it using bubble sort method.Let's see what will be the steps involved or you can say passes in this technique to sort a given linked list.Īpproach:First we have to form a linked list by inserting the values one by one and after insertion first we will point a head pointer towards the first node and keep on checking whether the current node data where the pointer is currently present is smaller,bigger or equal to the next node value. Now let's talk about how this technique works in linked list. ( 1 3 5 6 8 ) –> ( 1 3 5 6 8 ) Bubble Sort on Linked List The algorithm needs one whole pass without any swap to know it is sorted. Now, the array is already sorted, but our algorithm does not know if it is completed. ( 1 5 3 6 8 ) –> ( 1 5 3 6 8 ), Now, since these elements are already in order (8 > 6), algorithm does not swap them. ( 6 1 5 3 8 ) –> ( 1 6 5 3 8 ), Here, algorithm compares the first two elements, and swaps since 6 > 1. Let's throw some light on Bubble sort that what is bubble sorting technique and how it works.It is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.You will clearly understand how it works after seeing this below mentioned example.
Prerequisite: Linked List, Bubble Sort Introduction to Linked ListĪ linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.It consists of nodes where each node contains a data field and a reference(link) to the next node in the list. In this article, we have presented the approach to implement Bubble Sort on Singly Linked List and Doubly Linked List along with implementations in C and C++.
0 kommentar(er)
