Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

Simple implementation: Jon Bentley shows a three-line C/C++ version that is five lines when optimized.
Efficient for (quite) small data sets, much like other quadratic (i.e., O(n2)) sorting algorithms
More efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort
Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position
Stable; i.e., does not change the relative order of elements with equal keys
In-place; i.e., only requires a constant amount O(1) of additional memory space

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 (13)

Related publications

Related people (1)

Related people

Related units

Related concepts (17)

Related concepts

Related courses (9)

Related courses

Related lectures (41)

Related lectures

Insertion techniques for job shop scheduling

EPFL2001

Discrete Holomorphicity and Ising Model Operator Formalism

Clément Hongler, Ali Zahabi

We explore the connection between the transfer matrix formalism and discrete complex analysis approach to the two dimensional Ising model. We construct a discrete analytic continuation matrix, analyze its spectrum and establish a direct connection with the critical Ising transfer matrix. We show that the lattice fermion operators of the transfer matrix formalism satisfy, as operators, discrete holomorphicity, and we show that their correlation functions are Ising parafermionic observables. We extend these correspondences also to outside the critical point. We show that critical Ising correlations can be computed with operators on discrete Cauchy data spaces, which encode the geometry and operator insertions in a manner analogous to the quantum states in the transfer matrix formalism.

2014

In-depth analysis of hyaline fibromatosis syndrome frameshift mutations at the same site reveal the necessity of personalized therapy

Matteo Dal Peraro, Thomas Lemmin, Suzanne Salvi, Françoise Gisou van der Goot Grunberg, Shixu Yan

Hyaline fibromatosis syndrome is an autosomal recessive disease caused by mutations in ANTXR2, a gene involved in extracellular matrix homeostasis. Sixty percent of patients carry frameshift mutations at a mutational hotspot in exon 13. We show in patient cells that these mutations lead to low ANTXR2 mRNA and undetectable protein levels. Ectopic expression of the proteins encoded by the mutated genes reveals that a two base insertion leads to the synthesis of a protein that is rapidly targeted to the ER-associated degradation pathway due to the modified structure of the cytosolic tail, which instead of being hydrophilic and highly disordered as in wild type ANTXR2, is folded and exposes hydrophobic patches. In contrast, one base insertion leads to a truncated protein that properly localizes to the plasma membrane and retains partial function. We next show that targeting the nonsense mediated mRNA decay pathway in patient cells leads to a rescue of ANTXR2 protein in patients carrying one base insertion but not in those carrying two base insertions. This study highlights the importance of in-depth analysis of the molecular consequences of specific patient mutations, which even when they occur at the same site can have drastically different consequences.

Wiley-Blackwell2013

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

CS-322: Introduction to database systems

This course provides a deep understanding of the concepts behind data management systems. It covers fundamental data management topics such as system architecture, data models, query processing and optimization, database design, storage organization, and transaction management.

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascendin

Quicksort

Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is still a commonly used algorithm for

Merge sort

In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means