1. Introduction
he intelligent and most intuitive way to do this is to analyze the items in the array or list with each other and adapt them according to their relative order, moving an element forward or backward in the list depending on whether items next to it are greater or smaller. This is called a comparison sort.
Bubble sort algorithm [13], which is a simple sorting algorithm, 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.
We considered three elements and move one element towards left or right and while moving this element other element moved one or two position towards opposite direction.
The main drawback of the proposed algorithm is that if smallest element is at last location then it requires n/2 iterations to move to first location. To overcome this draw back we proposed a modification to the sorting algorithm, in this for each iteration in first half the largest in the first half moved to first location of second half and in the second half, iteration start from the last element and in this iteration smallest in second half moved to the last location of first half of the elements. This procedure is repeated for n/2 times to arrange the elements in sorted order.
2. II.
3. Proposed Modification
In each iteration in first half the largest in the first half moved to first location of second half and in the second half iteration start from the last element and in this second half iteration smallest in second half moved to the last location of first half of the elements. In successive iterations the smallest element moved to first half may be moved towards left if it is smaller than other elements in the first half same is true for the element moved to second half of the element. This procedure is repeated to arrange the elements in sorted order. For example consider set of elements 9 4 6 7 8 3 9 5 2 Novel sorting algorithm Author : SSAIST, Surampalem, India. E-mail : [email protected]
4. Algorithm
Input: List of elements a[0..n-1] where n is number of elements.
Step 1: swap=0
Step 2: repeat step 3 to 6 for j=0 to n/2 where step size=1
Step 3: repeat step 4 for i=1 to n/2 where step size=2
Step 4: compare elements a
[i-1],a[i] a[i+1]. If theyare not in order arrange them order. Set swap=1;
Step 5: repeat step 6 for k=n-1 to n/2 where step size=-2
Step 6: compare elements a[k-1], a[k] and a[k+1]. If they are not in order arrange them in order. Set swap=1;
Step 7: If swap=0 then given elements are in order break the outer loop else set swap=0.
5. a) Algorithm Analysis
The time for most sorting algorithms depends on the amount of data or size of the problem. [4] Worst Case
The outer loop repeats for n/2 times.
In first pass of outer loop, the first inner loop repeats for (n/4) times and performs 3n/4 comparison operations and second inner loop repeats for (n/4) times and perform 3n/4 comparisons. The number of assignments performed depends on the order of elements. The maximum number of assignments performed is 2n. In the second pass (n/2) in third pass (n/2)?? Inner loop repeats n/2+n/2+ ??..n/2 terms. =n 2 /4 Therefore the worst time complexity is O(n 2 ) IV.
6. Results
he time complexity of this algorithm in in worst case O(n 2 ) same as bubble sort but their actual run time differ. For better understanding the actual performance we conducted some experiments.
The run times are measured on a PC, (AMD athlaon 220xd) processor and1G.B. RAM under Microsoft XP operating system. These algorithms are compiled using the sun java platform complier and run under the java interpreter. The run time shown is CPU execution time measured using object of Date class. The class Date available in java util package. The elements are generated using nextInt method of Random class. The same set of elements is used for algorithms.
7. Conclusion
We have proposed modification to a novel sorting algorithm to sort given elements. The Proposed method uses three elements at a time to compare based on the result it arranges the elements. The proposed algorithm is easy to understand and easy to implement. We also proposed a modification of considering iterations to increase the speed of execution. The proposed algorithm has similarity like bubble sort that is in every phase one element moved to its correct location.
| 013 |
| 2 |
| Year |
| 22 |
| Volume XIII Issue XI Version I |
| D D D D D D D D ) C |
| ( |
| Global Journal of Computer Science and Technology |