bubble sort in real applications
212599212
Minimizing Execution Time of Bubble Sort Algorithm
Sorting is an important data structure which finds its place in many real life applications. A number of sorting algorithms are in existence till date. In this paper the we have tried to improve upon execution time of the Bubble Sort algorithm by implementing the algorithm using a new algorithm .An extensive analysis has been done by us on the new algorithm and the algorithm has been compared with the traditional method of Bubble Sort. Observations have been obtained on comparing this new approach with the existing approaches of Bubble Sort. The new algorithm was tested on random data of various ranges from small to large. It has been observed that the new approach has given efficient results in terms of execution time. Hence we have reached to the conclusion through the experimental observations that the new algorithm given in this paper is better than the traditional Bubble Sort.
Ms Jyoti Mundra
18911323
Run Time Bubble Sort An Enhancement of Bubble Sort
In many real applications, sorting plays an important role as it makes easy to handle the data by arranging it in ascending or descending order, according to requirements. Bubble sort is most common sorting algorithm, but not efficient for many applications. There are number of other sorting algorithms and still, research is going for new sorting algorithms to improve the complexities of existing algorithms whether it is space complexity or it is time complexity. This paper introduces a new algorithm named RTBS (Run Time Bubble Sort) This sorting technique is very simple to implement. It is helpful to reduce the elapsed time when to sort the data. RTBS is compared with original bubble sort algorithm. This sorting technique is tested for average case, best case and the worst case. KeywordsSorting algorithm, Bubble sort.
Harish Rohil Man Sha
203598451
Implementing Bubble Sort Using a New Approach
Sorting is an important data structure which finds its place in many real life applications. A number of sorting algorithms are in existence till date and ample of research is still going on to make an extensive analysis of the existing algorithms to reduce their time complexity up to the extent possible. Research is also going on for finding the algorithms which are fast enough than the existing ones. In this paper the authors have tried to improve upon the Bubble Sort technique by implementing the algorithm using a new approach of implementation .An extensive analysis has been done by the authors on the new approach and the approach has been compared with the traditional method of Bubble Sort| along with its popular variation Bi Directional Sort| Interesting observations have been obtained on comparing this new approach with the existing approaches of Bubble Sort. The approach was tested for Average Case analysis, Best Case analysis and Worst case analysis. It has been observed that the new approach has given wonderful results on Average Case and Worst Case analysis. Hence the authors have reached to the conclusion through the experimental observations that the new approach as suggested in this paper is better than the traditional Bubble Sort and its Bi Directional variation.
Vibhakar Mansotra Kr Sourabh
17694342
UPC SPIN A Framework for the Model Checking of UPC Programs
This paper presents a software framework for the model check ing of the inter thread synchronization functionalities of Un ified Parallel C (UPC) programs. The proposed framework includes a fron tend compiler that generates finite models of UPC programs in t he modeling language of the SPIN model checker. The model gener ation is based on a set of abstraction rules that transform th e UPC synchronization primitives to semantically equivalent c ode snippets in SPIN's modeling language. The back end includes SPI N that verifies the generated model. If the model checking succ eeds, then the UPC program is correct with respect to properties of interest such as data race freedom and/or deadlock freedom. Oth erwise, the back end provides feedback as sequences of UPC instructions that lead to a data race or a deadlock from initial states called counterexamples Using the UPC SPIN framework, we have detected design flaws in several real world UPC applications, including a program simulating heat flow in metal rods, parallel bub ble sort, parallel data collection, and an integer permutation program. More importantly, for the first time (to the best of our knowle dg we have mechanically verified data race freedom and deadloc kfreedom in a UPC implementation of the Conjugate Gradient (C G) kernel of the NAS Parallel Benchmarks (NPB) We believe that UPC SPIN provides a valuable tool for developers towards in creasing their confidence in the computational results generated by UPC applications.
Ali Ebnenasir
60267440
RANK BASED OPTIMIZED SORTING NETWORK ARCHITECTURE FOR HARDWARE IMPLEMENTATION OF ROF
In this paper an optimized architecture for implementation of ROF is presented. The architecture is based on sorting network architecture algorithm optimized for each rank and consists of significantly fewer comparators than the existing architectures that are based on bubble sort and quick sort (Cardells Tormo and Molinet, 2006) The reduction in comparators is obtained by sorting the columns of the window only once, and then merging the elements based on the range of the ranks the column sorted elements would occupy. The design of architecture is further optimized using the concepts of parallelism and pipelining to store the sorted columns of one window for processing the next successive overlapping windows (Gonzalez and Woods, 2000 and Archana et al. 2005).The architecture is pipelined which processes one pixel per clock cycle, thus to process an image of size 256 x 256 it requires 0.65ms when a clock of 100MHz is used and hence is suitable for real time applications.
S M Meena K Linganagouda
62687911
Current dynamics based macro model for power simulation in a complex VLIW DSP processor
A methodology and a macro modelling approach are presented for analysing low level current dynamics at the instruction and program level for a complex VLIW DSP processor core. An instruction level macro model, whose input parameters can be extracted from the DSP core's assembly level program, is introduced for power modelling. For the first time, dynamic power models of algorithms are introduced and verified with real power measurements of a DSP processor core in a VLSI chip. Results from both cryptographic and bubble sort applications show that dynamic power can be modelled with an average error in energy estimation ranging from 0.3% to 9.7% The instruction level macro model of power also supports different clock frequencies and compressed algorithmic traces, important for security aware compilers. In general, the research is important for analysing and modelling the impact of software on power, the design of embedded cryptographic VLSI systems that are safe from power attacks, and for reliable design by detecting the peak current values generated by the software application.
Radu Muresan Catherine H Gebotys
13602733
Bubble Entropy: An Entropy Almost Free of Parameters
Objective: A critical point in any definition of entropy is the selection of the parameters employed to obtain an estimate in practice. We propose a new definition of entropy aiming to reduce the significance of this selection. Methods: We call the new definition Bubble Entropy. Bubble Entropy is based on permutation entropy, where the vectors in the embedding space are ranked. We use the bubble sort algorithm for the ordering procedure and count instead the number of swaps performed for each vector. Doing so, we create a more coarse grained distribution and then compute the entropy of this distribution. Results: Experimental results with both real and synthetic HRV signals showed that bubble entropy presents remarkable stability and exhibits increased descriptive and discriminating power compared to all other definitions, including the most popular ones. Conclusion: The definition proposed is almost free of parameters. The most common ones are the scale factor r and the embedding dimension m In our definition, the scale factor is totally eliminated and the importance of m is significantly reduced. The proposed method presents increased stability and discriminating power. Significance: After the extensive use of some entropy measures in physiological signals, typical values for their parameters have been suggested, or at least, widely used. However, the parameters are still there, application and dataset dependent, influencing the computed value and affecting the descriptive power. Reducing their significance or eliminating them alleviates the problem, decoupling the method from the data and the application, and eliminating subjective factors.
IEEE Transactions on Biomedical Engineering
George Manis Md Aktaruzzaman Roberto Sassi
219843995
Implementing real time image processing algorithm on FPGA
FPGA is popular for real time image process attributed to its flexibility and parallelism. In this paper, a parallel fast median filtering algorithm is implemented by FPGA. The times of comparison can be reduced by half compared to the bubble sort method. To keep more border information of image, an efficient implement of border management is proposed in detail. Meanwhile, a speed up method presented is more effective in the real time application. The proposed method shows good performance in eliminating noise. The low resource consuming and the low latency is meaningful for real time image processing application.
International Conference on Digital Image Processing
Jin Xu Jian Geng Xinfeng Yan Hongkai Wang Huang Xia
62688753
A nine input 1.25 mW, 34 ns CMOS analog median filter for image processing in real time
In this paper an analog voltage mode median filter, which operates on a 3 x 3 kernel is presented. The filter is implemented in a 0.35 mm CMOS technology. The proposed solution is based on voltage comparators and a bubble sort configuration. As a result, a fast (34 ns) time response with low power consumption (1.25 mW for 3.3 V) is achieved. The key advantage of the configuration is relatively high accuracy of signal processing, which allows the calculation of the median of signals with the difference in amplitude as small as 10 mV. This feature allows the application of the filter to vision systems with up to 7 bit equivalent resolution. The analytical and statistical analysis of the filter resolution, and analysis of its speed limitations are presented and compared to measurement results. Based on the achieved results, a set of guidelines for the filter design and optimisation is presented.
Waldemar Jendernalik Grzegorz Blakiewicz Jacek Jakusz Stanislaw Szczepanski
24301221
Enhanced Model and Real Time Simulation Architecture for Modular Multilevel Converter
This paper presents i) an equivalent model of the half bridge modular multilevel converter (HB MMC) which is suitable for real time applications, ii) a hybrid central processing unit/field programmable gate array (CPU/FPGA) based architecture for real time simulation of electromagnetic transients of systems which include HB MMC, and iii) a novel arrangement for sorting results referred to as the "sub module (SM) rank list" which tackles the bottleneck for parallel implementation of the MMC arm model solver on the FPGA. The Adam Bashforth (AB) method is used for numerical integration of the HB SM capacitor model. The second order AB method provides a constant admittance matrix of the HB MMC and, thus, reduces computational burden while offering the same accuracy as that of the widely used Trapezoidal method. The CPU/FPGA based architecture is optimized to obtain maximum parallelism of the HB MMC model implementation, adopting a standard, single precision, floating point computational engine. The proposed sorting arrangement is independent of the utilized sorting algorithm and its application to the odd even bubble sorting scheme is presented in this paper. The proposed architecture offers a simulation time step of 825 ns while including the sorting module as the SM capacitor voltage balancing control unit. This enables accurate analysis of MMC controls based on either software in the loop or hardware in the loop approaches. Performance and accuracy of the MMC model and the hybrid CPU/FPGA based architecture are evaluated based on a set of case studies on a 401 level HB MMC based HVDC station and verified based on offline simulation results in the PSCAD/EMTDC environment.
IEEE Transactions on Power Delivery
Mojtaba Ashourloo Ramin Mirzahosseini Reza Iravani