检索结果-内蒙古大学图书馆

28th IEEE International Parallel & Distributed Processing Symposium Workshops (IPDPSW)

作者： Koike, Atsushi Sadakane, Kunihiko Natl Inst Informat Principles Informat Res Div Tokyo Japan Grad Univ Adv Studies Dept Informat Tokyo Japan

ISBN: (纸本)9781479941162

We propose a novel computational model for GPU. Known parallel computational models such as the PRAM model are not appropriate for evaluating GPU algorithms. Our model, called AGPU, abstracts the essence of current GPU architectures such as global and shared memory, memory coalescing and bank conflicts. We can therefore evaluate asymptotic behavior of GPU algorithms more accurately than known models and we can develop algorithms that are efficient on many real architectures. As a showcase, we first analyze known comparison-based sorting algorithms using the AGPU model and show that they are not I/O optimal, that is, the number of global memory accesses is more than necessary. Then we propose a new algorithm which uses an asymptotically optimal number of global memory accesses and whose time complexity is also nearly optimal.

关键词： GPU GPGPU parallel computational models sorting algorithms

来源：评论

学校读者我要写书评

暂无评论

Synthesis of sorting algorithms using multisets in Theorema

引用

JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING 2021年 119卷

作者： Dramnesc, Isabela Jebelean, Tudor West Univ Timisoara Timisoara Romania Johannes Kepler Univ Linz RISC Linz Austria

Using multisets, we develop novel techniques for mechanizing the proofs of the synthesis conjectures for list-sorting algorithms, and we demonstrate them in the Theorema system. We use the classical principle of extracting the algorithm as a set of rewrite rules based on the witnesses found in the proof of the synthesis conjecture produced from the specification of the desired function (input and output conditions). The proofs are in natural style, using standard rules, but most importantly domain specific inference rules and strategies. In particular the use of multisets allows us to develop powerful strategies for the synthesis of arbitrarily structured recursive algorithms by general Noetherian induction, as well as for the automatic generation of the specifications of all necessary auxiliary functions (insert, merge, split), whose synthesis is performed using the same method. The proof techniques are implemented in the Theorema system and generate 8 sorting algorithms and 19 auxiliary functions. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Automated reasoning Synthesis sorting algorithms Lists Multisets Theorema

来源：评论

学校读者我要写书评

暂无评论

Analysis and Synthesis of sorting algorithms

引用

SIAM Journal on Computing 1972年第4期1卷 290-304页

作者： C. L. Liu

The problem of analyzing and synthesizing sorting algorithms is studied. That is, given a sorting algorithm we want to investigate how it works in a step-by-step manner and consequently to assert that it indeed arranges the objects according to a certain ordering relationship, and conversely, given an ordering relationship according to which a set of objects are to be arranged, we want to determine an algorithm that will yield the desired result.

关键词： sorting algorithms sorting networks

来源：评论

学校读者我要写书评

暂无评论

Examining the energy impact of sorting algorithms on android: an empirical study 19

Examining the energy impact of sorting algorithms on android...

引用

Proceedings of the 16th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services

作者： Andreas Schuler Gabriele Anderst-Kotsis University of Applied Sciences Upper Austria Hagenberg Upper Austria Austria Johannes Kepler University Linz Upper Austria Austria

ISBN: (纸本)9781450372831

With the advent of mobile application development a new software quality concern - energy consumption - was introduced. For mobile software developers knowledge about software and algorithm design choices and their implications on energy consumption is crucial. However, software developers either lack this knowledge or tools to support them in estimating the energy consumption of their applications and therefore are unable to reflect on their design choices. In this empirical study we examine the energy consumption of 12 sorting algorithms and the resulting energy impact when used with different data types. We propose a methodology to obtain energy readings and relate them to application execution traces. Our results show that the choice of data type together with algorithm design can have significant impact on the energy profile of an application.

关键词： sorting algorithms energy consumption mobile application development energy profiling software testing

来源：评论

学校读者我要写书评

暂无评论

Introspective sorting and selection algorithms

引用

SOFTWARE-PRACTICE & EXPERIENCE 1997年第8期27卷 983-993页

作者： Musser, DR Computer Science Department Rensselaer Polytechnic Institute Troy NY 12180 U.S.A.

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Theta(N log N), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Theta(N-2). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much - one might as well use heapsort, which has a Theta(N log N) worst-case time bound, but is on the average 2-5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i-th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the 'stopper' yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Theta(N log N) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum-Floyd-Pratt-Rivest-Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C++ Standard Template Library. (C) 1997 by John Wiley & Sons, Ltd.

关键词： quicksort heapsort sorting algorithms introspective algorithms hybrid algorithms generic algorithms STL

来源：评论

学校读者我要写书评

暂无评论

Teaching and Learning Computer Science sorting algorithms With Mobile Devices: A Case Study

引用

COMPUTER APPLICATIONS IN ENGINEERING EDUCATION 2013年第S1期21卷 E41-E50页

作者： Boticki, Ivica Barisic, Ante Martin, Sergio Drljevic, Neven Univ Zagreb Fac Elect Engn & Comp Dept Appl Comp Zagreb 41000 Croatia UNED Spanish Univ Distance Educ Dept Elect & Comp Engn Madrid Spain

In this article, we present a semester-long study on using smartphone devices in computing engineering education. We developed Sortko, an Android-based smartphone application for learning sorting algorithms, an important undergraduate computer science topic. The application consists of four main componentsthe module for interactive sorting, the scaffolding module, the motivational module, and the graphical user interface module, each with a distinct role of helping students in learning sorting algorithms. Our research methodology included data collection with administered two surveys, collected exam results and recorded application usage data. Analysis of the collected data shows our approach is an effective way of learning sorting algorithms. (c) 2012 Wiley Periodicals, Inc. Comput Appl Eng Educ 21:E41-E50, 2013

关键词： mobile learning engineering education sorting algorithms

来源：评论

学校读者我要写书评

暂无评论

Learning sorting algorithms through visualization construction

引用

COMPUTER SCIENCE EDUCATION 2016年第1期26卷 27-43页

作者： Cetin, Ibrahim Andrews-Larson, Christine Abant Izzet Baysal Univ Secondary Sci & Math Educ Bolu Turkey Florida State Univ Sch Teacher Educ Tallahassee FL 32306 USA

Recent increased interest in computational thinking poses an important question to researchers: What are the best ways to teach fundamental computing concepts to students? Visualization is suggested as one way of supporting student learning. This mixed-method study aimed to (i) examine the effect of instruction in which students constructed visualizations on students' programming achievement and students' attitudes toward computer programming, and (ii) explore how this kind of instruction supports students' learning according to their self-reported experiences in the course. The study was conducted with 58 pre-service teachers who were enrolled in their second programming class. They expect to teach information technology and computing-related courses at the primary and secondary levels. An embedded experimental model was utilized as a research design. Students in the experimental group were given instruction that required students to construct visualizations related to sorting, whereas students in the control group viewed pre-made visualizations. After the instructional intervention, eight students from each group were selected for semi-structured interviews. The results showed that the intervention based on visualization construction resulted in significantly better acquisition of sorting concepts. However, there was no significant difference between the groups with respect to students' attitudes toward computer programming. Qualitative data analysis indicated that students in the experimental group constructed necessary abstractions through their engagement in visualization construction activities. The authors of this study argue that the students' active engagement in the visualization construction activities explains only one side of students' success. The other side can be explained through the instructional approach, constructionism in this case, used to design instruction. The conclusions and implications of this study can be used by researchers and instruct

关键词： Visualization computational thinking engagement taxonomy sorting algorithms constructionism

来源：评论

学校读者我要写书评

暂无评论

Teaching sorting and Searching algorithms through Simulation-based Learning Objects in an Introductory Programming Course

引用

Procedia - Social and Behavioral Sciences 2014年 116卷 2962-2966页

作者： Georgi Tuparov Daniela Tuparova Vladimir Jordanov South-Western University “Neofit Rilski” 66 Ivan Michailov Str. 2700 Blagoevgrad Bulgaria Institute of Mathematics and Informatics Bulgarian Academy of Science Acad. Georgi Bonchev Str. Block 8 1113 Sofia Bulgaria

In this paper we present our experience in the development and use of interactive simulation-based Learning Objects (LOs) in an introductory course of programming. The focus of our research is on the teaching of one of the important topics in introductory courses of programming - sorting algorithms and their programming implementation. The characteristics of the LOs developed and the scenarios used for their deployment are described. The results from the pilot study, discussed in the paper, demonstrate an increase of student interest and a level of understanding of the learning content.

关键词： teaching programming sorting algorithms computer based simulation vizualisation learning objects

来源：评论

学校读者我要写书评

暂无评论

Introspective sorting and Selection algorithms

引用

Software: Practice and Experience 1999年第8期27卷

作者： DAVID R. MUSSER Computer Science Department Rensselaer Polytechnic Institute Troy NY 12180 U.S.A.

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Θ( N log N ), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Θ( N 2 ). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much – one might as well use heapsort, which has a Θ( N log N ) worst-case time bound, but is on the average 2–5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i -th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the ‘stopper’ yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Θ( N log N ) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum–Floyd–Pratt–Rivest–Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C+:+ Standard Template Library. ©1997 by John Wiley & Sons, Ltd.

关键词： quicksort heapsort sorting algorithms introspective algorithms hybrid algorithms generic algorithms STL

来源：评论

学校读者我要写书评

暂无评论

Cluster Sort: A Novel Hybrid Approach to Efficient In-Place sorting Using Data Clustering

引用

IEEE ACCESS 2025年 13卷 74359-74374页

作者： Subramaniam, Mohit Tripathi, Tanya Chandraumakantham, Omkumar Vellore Inst Technol Sch Comp Sci & Engn Chennai 600127 Tamil Nadu India

This research work introduces a clustering-based in-place sorting algorithm, cluster sort. It is designed in such a way that it improves sorting efficiency by using data locality. It works in two phases: first, data elements are clustered based on the similarity in the values and then each of these clusters is sorted independently using comb or shell sort. This is a hybrid approach, and it helps minimize multiple comparisons within the clusters, which in turn improves performance, especially in large datasets with specific distributions. The traditional algorithms were selected due to their well-known efficiency and widespread use in sorting large datasets. This experiment of ours includes ordered, reverse-ordered, Gaussian, repeated values, same values, and uniform distributions. The results acquired from this experiment show that Cluster Sort (comb) outperforms Cluster Sort (shell) by 88% in ordered datasets and is 92.32% faster than Merge Sort. For reverse-ordered datasets, Cluster Sort (Comb) is 70.79% faster than Bucket Sort and 90.69% faster than Cluster Sort (Shell). In Gaussian distributions, Cluster Sort (Shell) improves by 25.88% over Bucket Sort and 74.41% over Merge Sort. In repeated-value datasets, although Quick Sort is faster, Cluster Sort (Shell) surpasses Bucket Sort by 13.64%. For uniform distributions, Cluster Sort (Shell) is 30.28% faster than Bucket Sort and 75% faster than Merge Sort. The reduction in unwanted comparisons through clustering is essentially what made Cluster Sort significantly outperform traditional algorithms in these datasets with inherent patterns, making Cluster Sort a coherent choice for practical applications.

关键词： Clustering algorithms sorting Heuristic algorithms Partitioning algorithms Memory management Merging Complexity theory Random access memory Machine learning algorithms Time complexity Merge sort sorting algorithms shell sort bucket sort heap sort comb sort clustering

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：