Selection sort

Summary

In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(n2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items 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 (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. The time

Official source

https://en.wikipedia.org/wiki/Selection_sort

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (7)

Related publications

Related people

Related units

Related concepts (13)

Related concepts

Related courses (5)

Related courses

Related lectures (18)

Related lectures

, ,

We present the disambiguation canvas, a technique developed for easy, accurate and fast selection of small objects and objects inside cluttered virtual environments. Disambiguation canvas rely on selection by progressive refinement, it uses a mobile device and consists of two steps. During the first, the user defines a subset of objects by means of the orientation sensors of the device and a volume casting pointing technique. The subsequent step consists of the disambiguation of the desired target among the previously defined subset of objects, and is accomplished using the mobile device touchscreen. By relying on the touchscreen for the last step, the user can disambiguate among hundreds of objects at once. User tests show that our technique performs faster than ray-casting for targets with approximately 0.53 degrees of angular size, and is also much more accurate for all the tested target sizes.

Springer Berlin Heidelberg2013

We present Disambiguation canvas, a technique for selection by progressive refinement using a mobile device and consisting of two steps. During the first, the user defines a subset of objects through the orientation sensors of the device and a volume-casting pointing technique. The subsequent step consists of the disambiguation of the desired target among the previously-defined subset of objects, and is accomplished using the mobile device touchscreen. By relying on the touchscreen for the last step the user can disambiguate among hundreds of objects at once, previous progressive refinement techniques do not scale as well as ours. Disambiguation canvas is mainly developed for easy, accurate and fast selection of small objects, or objects inside cluttered virtual environments. User tests show that our technique performs faster than ray-casting for targets with approximate to 0 : 53 degrees of angular size, and is also much more accurate for all the tested target sizes.

Ieee2013

Heterogeneous Recommendations: What You Might Like To Read After Watching Interstellar

Rachid Guerraoui, Anne-Marie Kermarrec, Tao Lin, Rhicheek Patra

Recommenders, as widely implemented nowadays by major e-commerce players like Netflix or Amazon, use collaborative filtering to suggest the most relevant items to their users. Clearly, the effectiveness of recommenders depends on the data they can exploit, i.e., the feedback of users conveying their preferences, typically based on their past ratings. As of today, most recommenders are homogeneous in the sense that they utilize one specific application at a time. In short, Alice will only get recommended a movie if she has been rating movies. But what if she has been only rating books and would like to get recommendations for a movie? Clearly, the multiplicity of web applications is calling for heterogeneous recommenders that could utilize ratings in one application to provide recommendations in another one. This paper presents X-Map, a heterogeneous recommender. X-Map leverages meta-paths between heterogeneous items over several application domains, based on users who rated across these domains. These meta-paths are then used in X-Map to generate, for every user, a profile (AlterEgo) in a domain where the user might not have rated any item yet. Not surprisingly, leveraging meta-paths poses non-trivial issues of (a) meta-path-based inter-item similarity, in order to enable accurate predictions, (b) scalability, given the amount of computation required, as well as (c) privacy, given the need to aggregate information across multiple applications. We show in this paper how X-Map addresses the above-mentioned issues to achieve accuracy, scalability and differential privacy. In short, X-Map weights the meta-paths based on several factors to compute inter-item similarities, and ensures scalability through a layer-based pruning technique. X-Map guarantees differential privacy using an exponential scheme that leverages the meta-path-based similarities while determining the probability of item selection to construct the AlterEgos. We present an exhaustive experimental evaluation of X-Map using real traces from Amazon. We show that, in terms of accuracy, X-Map outperforms alternative heterogeneous recommenders and, in terms of throughput, X-Map achieves a linear speedup with an increasing number of machines.

Assoc Computing Machinery2017

Heterogeneous Recommendations: What You Might Like To Read After Watching Interstellar

Rachid Guerraoui, Anne-Marie Kermarrec, Tao Lin, Rhicheek Patra

Assoc Computing Machinery2017