Language used : java
Implemented the doubly linked list with array using prev, next and key array.
Populated the array with some values, and performed bubble sort .
Here instead of swapping the values of the key, we have swapped the position in next and previous array.
Finally display these array with forward slash representing NULL character.
Eg:
Doubly linked list After sorting
Previous Value Next
/ 1 2
3 2 7
2 4 1
7 5 4
1 7 6
4 8 5
6 9 0
5 10 /
And for second one, program takes the input for the number of elements required and picks that many random number based on java built in Random method. And perform all the 3 sort(merge sort, insertion sort and quick sort) for the same array. Finally after sorting it shows the time taken for performing the sort and the number of swaps performed.
Eg:
Enter the number of elements required in array:
20
Before Sorting Array :
864 30 758 338 521 42 847 287 34 19 687 267 885 391 293 744 561 697 390 46
After Merge Sort:
19 30 34 42 46 267 287 293 338 390 391 521 561 687 697 744 758 847 864 885
Time taken (in nanoSeconds) = 26773
Number of swaps performed = 84
After Insertion Sort :
19 30 34 42 46 267 287 293 338 390 391 521 561 687 697 744 758 847 864 885
Time taken (in nanoSeconds) = 30343
Number of swaps performed = 96