Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, it is too slow for practical use, even compared to insertion sort. - Wikipedia
procedure bubbleSort(A : list of sortable items)
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap(A[i-1], A[i])
swapped = true
end if
end for
until not swapped
end procedureThe algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. - Wikipedia
procedure selectionSort(A : list of sortable items)
min = 0
for i = 0 to n-1 exclusive do
min = i
for j = i+1 to n exclusive do
if A[j] < A[min] then
min = j
end if
end for
if min != i then
swap(A[i], A[min])
end if
end for
end procedureInsertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. - Wikipedia
procedure insertionSort(A : list of sortable items)
n = length(A)
for i = 1 to n exclusive do
j = i
repeat
swap(A[j], A[j-1])
j = j - 1
until j < 0 or A[j-1] < A[j]
end for
end procedureCreate two lists, L1 and L2. L1 and L2 need not have the same number of nodes. You can assume that L1 and L2 will always contain distinct values. Further, no value in L1 will occur in L2 and vice versa. Your program should link L1 and L2 such that the resulting list contains nodes whose values alternate between L1 and L2. If L1 has more nodes than L2 or vice versa, the remaining nodes from the bigger list should simply be left intact. Your program should disconnect and reconnect nodes in L1 and L2 to produce the list, L. The resulting list will always start with the first node in L1.
List 1?
> 1 2 3 4 5 6 7
List 2?
> 100 200 300
1 100 2 200 3 300 4 5 6 7List 1?
> 100 200 300
List 2?
> 1 2 3 4 5 6 7
100 1 200 2 300 3 4 5 6 7Create a list L, with distinct input values. You can assume that L will always contain distinct values. Your program has to create two lists, L1 and L2 from L. L1 will be the list that consists of all the odd numbered nodes from L and L2 will be the list with all the even numbered nodes from L. You have to disconnect and reconnect nodes in L to produce the two lists, L1 and L2.Output L1 and L2.
List?
> 100 200 300 400 500 600 700 800
L1: 100 300 500 700
L2: 200 400 600 800A doubly linked list is a linked list where each node has two references the first reference stores the reference of the next node and the second reference stores the reference of the previous node. Start with your linked lists files that implement a singly linked list and re-write them to implement a doubly linked lists.