To perform bubble sort, we follow below steps:
Step 1: Check if data on the 2 adjacent nodes are in ascending order or not. If not, swap the data of the 2 adjacent nodes.
Step 2: At the end of pass 1, the largest element will be at the end of the list. In 2nd pass 2nd largest element will be at its position.
Step 3: We terminate the loop, when all the elements are started.
Solution in C++
#include<iostream> #include<vector> #include<string> using namespace std; struct Node { int data; Node *next; Node(int x) { data = x; next = NULL; } }; void print_list(Node *head) { Node *start = head; while(start) { cout<<start->data<<" -> "; start = start->next; } cout<<"\n\n"; } void my_swap (Node *node_1, Node *node_2) { int temp = node_1->data; node_1->data = node_2 -> data; node_2 -> data = temp; } void bubble_sort(Node *head) { int swapped; Node *lPtr; // left pointer will always point to the start of the list Node *rPrt = NULL; // right pointer will always point to the end of the list do { swapped = 0; lPtr = head; while(lPtr->next != rPrt) { if (lPtr->data > lPtr->next->data) { my_swap(lPtr, lPtr->next); swapped = 1; } lPtr = lPtr->next; } //as the largest element is at the end of the list, assign that to rPtr as there is no need to //check already sorted list rPrt = lPtr; }while(swapped); } int main() { Node *head = new Node(2); head -> next = new Node(1); head -> next -> next = new Node(4); head -> next -> next -> next = new Node(3); head -> next -> next -> next -> next = new Node(6); head -> next -> next -> next -> next -> next = new Node(5); cout<<"The original list = "<<endl; print_list(head); bubble_sort(head); cout<<"The Sorted list = "<<endl; print_list(head); return 0; }
Output:
The original list = 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> The Sorted list = 1 -> 2 -> 3 -> 4 -> 5 -> 6 ->
GABRIEL JOSE PAULINO LEMOS
what i have to change for the output being descending order?