The linked list is a data structure in which the data are stored linearly in a memory location but it is a non-contiguous memory allocation. The elements in a linked list are connected with pointers. A structure is defined to create the linked list. Here the sorting is done on a singly linked list using the bubble sort technique.
To seeing Bubble Sort please follow:
https://mycareerwise.com/programming/category/sorting/bubble-sort
INPUT: the elements of a list.
OUTPUT: The sorted list
PROCESS:
Step 1: [defining the function ‘createlist()’]
Read n [number of elements]
For i=0 to n-1 repeat
Read x [the element to be inserted]
Set p<-new node()
data[p]<-x
next[p]<-null
if head=null then
Set head<-p
Else
Set next[ptr]=p
[End of ‘if’]
Set ptr<-p
[End of ‘for’ loop]
[End of function ‘createlist()’]
Step 2: [defining the function ‘displaylist()’]
Set ptr<-head
While ptr≠null repeat
Print data[ptr]
Set ptr<-next[ptr]
[End of ‘while’ loop]
[End of function ‘displaylist()’]
Step 3: [defining the function ‘sort()’]
Step 3.1: Set ptr1<-null
Step 3.2: if head = null then
return
Step 3.3: Set flag <- 0
Set ptr <- head
while next[ptr]≠ptr1 repeat
if data[ptr] >data[next[ptr]] then
swap ptr,next[ptr]
Set flag<-1
[End of ‘if’]
Set ptr<-next[ptr]
[End of ‘while’ loop]
Set ptr1<-ptr
While(flag=true) repeat step 3.3
Print The sorted list by calling display_list function
[End of function ‘sort()’]
TIME COMPLEXITY:
For more details about the complexity of bubble sort please follow:
https://mycareerwise.com/programming/category/sorting/bubble-sort
Related
Contributed by