| dbo:abstract
|
- Quickselect (englisch quick, deutsch ‚schnell‘ und to select ‚auswählen‘) ist ein Auswahlverfahren aus der Informatik, um das k-kleinste Element in einer ungeordneten Liste zu finden. Es bezieht sich auf den Quicksort-Sortieralgorithmus. Wie Quicksort wurde es von Tony Hoare entwickelt und ist daher auch als Hoare-Auswahlalgorithmus bekannt. Wie Quicksort ist es in der Praxis effizient und hat einen guten Average Case, jedoch auch eine schlechte Leistung im Worst Case. Quickselect und seine Varianten sind die am häufigsten verwendeten Selektionsalgorithmen in effizienten Implementierungen in der Praxis. Quickselect verwendet den gleichen Gesamtansatz wie Quicksort, wählt ein Element als Pivot und teilt die Daten in zwei Teile, basierend auf dem Pivot, entsprechend kleiner oder größer als der Pivot. Anstatt jedoch, wie bei Quicksort, in beide Seiten zurückzukehren, kehrt die Schnellauswahl nur in eine Seite zurück – die Seite mit dem gesuchten Element. Dies reduziert die durchschnittliche Komplexität von auf , mit einem Worst Case von . Wie bei Quicksort ist die Schnellauswahl im Allgemeinen als In-Place-Algorithmus implementiert, und über die Auswahl des k'ten Elements hinaus sortiert sie die Daten teilweise auch. (de)
- En algorithmique, quickselect est un algorithme de sélection qui retourne le ke plus petit élément dans une liste non ordonnée. Comme l'algorithme de tri quicksort, il a été créé par Tony Hoare et il est donc aussi connu comme l' algorithme de sélection de Hoare. Quickselect utilise la même approche que quicksort, choisissant un élément à la fois, afin de partitionner les éléments selon le pivot. Cependant, au lieu de séparer l'ensemble en deux parties comme dans quicksort, l'algorithme quickselect n'utilise la récursion que sur un côté - le côté contenant l'élément qu'il cherche. Cela réduit la complexité en moyenne O(n log n) de quicksort à la complexité en moyenne O(n) de quickselect. Tout comme quicksort, l'algorithme quickselect est en général implémenté en place, et en plus de sélectionner le ke élément, il trie une partie des données. Comme quicksort, il est efficace en pratique avec un temps moyen de . Quickselect et ses variantes sont des algorithmes souvent utilisés dans le monde réel. (fr)
- In computer science, quickselect is a selection algorithm to find the kth smallest element in an unordered list. It is also known as the kth order statistics . It is related to the quicksort sorting algorithm. Like quicksort, it was developed by Tony Hoare, and thus is also known as Hoare's selection algorithm. Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance. Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations. Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for. This reduces the average complexity from to , with a worst case of . As with quicksort, quickselect is generally implemented as an in-place algorithm, and beyond selecting the kth element, it also partially sorts the data. See selection algorithm for further discussion of the connection with sorting. (en)
- クイックセレクト（英: quickselect）は配列内の k 番目に小さい要素を見つけるための選択アルゴリズム。クイックソートによく似たアルゴリズムで、クイックソートと同じくアントニー・ホーアに発見されたため、 ホーアの選択アルゴリズムとも呼ばれる。 クイックソートと同様に、平均的なパフォーマンスは良好だが、最悪の場合のパフォーマンスは悪くなる。クイックセレクトとその派生アルゴリズムは、効率的な実装として最もよく使われる選択アルゴリズムである。 クイックセレクトは、クイックソートと同じように1つの要素をピボットとして選択し、ピボットに基づいてデータをピボットよりも小さいかに大きいか二分割するのを繰り返す。ただし、クイックソートのように分割した両方の区間に対して再帰するのではなく、クイックセレクトは一方の側、つまり検索している要素のある側にのみ再帰する。これにより、平均計算量が軽減される。平均計算量はクイックソートが なのに対してクイックセレクトは 。最悪計算量はクイックソートと同じく 。 クイックソートと同様に、クイックセレクトは通常、In-placeアルゴリズムとして実装され、 k 番目の要素を選択するだけでなく、データを部分的にソートする。ソートとの関係の詳細については、選択アルゴリズムを参照。 (ja)
- In informatica, quickselect è un algoritmo randomizzato ricorsivo che trova il k-esimo elemento di un array disordinato di grandezza n eseguendo O(n2) confronti nel caso peggiore e O(n) nel caso atteso. Si basa sull'algoritmo Quicksort e sfrutta la metodologia prune and search. L'algoritmo quicksort ha diverse relazioni di ricorrenza, dovute al tipo di problema di minore entità che si viene a creare ogni volta che l'algoritmo viene eseguito. Se ogni chiamata ricorsiva dimezza il problema, si ha: che ha soluzione O(n) in base al teorema master. Se invece si è nel caso peggiore, si ottiene: che ha soluzione O(n2) in base al teorema master. (it)
- 在计算机科学中，快速选择（英語：Quickselect）是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的，因而也被称为霍尔选择算法。 同样地，它在实际应用是一种高效的算法，具有很好的平均时间复杂度，然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。 快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度，从O(n log n)至O(n)，不过最坏情况仍然是O(n2)。 与快速排序一样，快速选择一般是以原地算法的方式实现，除了选出第k小的元素，数据也得到了部分地排序。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8292 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:averageTime
| |
| dbp:bestTime
| |
| dbp:caption
|
- Animated visualization of the quickselect algorithm. Selecting the 22nd smallest value. (en)
|
| dbp:class
| |
| dbp:data
| |
| dbp:name
| |
| dbp:optimal
| |
| dbp:time
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- クイックセレクト（英: quickselect）は配列内の k 番目に小さい要素を見つけるための選択アルゴリズム。クイックソートによく似たアルゴリズムで、クイックソートと同じくアントニー・ホーアに発見されたため、 ホーアの選択アルゴリズムとも呼ばれる。 クイックソートと同様に、平均的なパフォーマンスは良好だが、最悪の場合のパフォーマンスは悪くなる。クイックセレクトとその派生アルゴリズムは、効率的な実装として最もよく使われる選択アルゴリズムである。 クイックセレクトは、クイックソートと同じように1つの要素をピボットとして選択し、ピボットに基づいてデータをピボットよりも小さいかに大きいか二分割するのを繰り返す。ただし、クイックソートのように分割した両方の区間に対して再帰するのではなく、クイックセレクトは一方の側、つまり検索している要素のある側にのみ再帰する。これにより、平均計算量が軽減される。平均計算量はクイックソートが なのに対してクイックセレクトは 。最悪計算量はクイックソートと同じく 。 クイックソートと同様に、クイックセレクトは通常、In-placeアルゴリズムとして実装され、 k 番目の要素を選択するだけでなく、データを部分的にソートする。ソートとの関係の詳細については、選択アルゴリズムを参照。 (ja)
- 在计算机科学中，快速选择（英語：Quickselect）是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的，因而也被称为霍尔选择算法。 同样地，它在实际应用是一种高效的算法，具有很好的平均时间复杂度，然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。 快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度，从O(n log n)至O(n)，不过最坏情况仍然是O(n2)。 与快速排序一样，快速选择一般是以原地算法的方式实现，除了选出第k小的元素，数据也得到了部分地排序。 (zh)
- Quickselect (englisch quick, deutsch ‚schnell‘ und to select ‚auswählen‘) ist ein Auswahlverfahren aus der Informatik, um das k-kleinste Element in einer ungeordneten Liste zu finden. Es bezieht sich auf den Quicksort-Sortieralgorithmus. Wie Quicksort wurde es von Tony Hoare entwickelt und ist daher auch als Hoare-Auswahlalgorithmus bekannt. Wie Quicksort ist es in der Praxis effizient und hat einen guten Average Case, jedoch auch eine schlechte Leistung im Worst Case. Quickselect und seine Varianten sind die am häufigsten verwendeten Selektionsalgorithmen in effizienten Implementierungen in der Praxis. (de)
- En algorithmique, quickselect est un algorithme de sélection qui retourne le ke plus petit élément dans une liste non ordonnée. Comme l'algorithme de tri quicksort, il a été créé par Tony Hoare et il est donc aussi connu comme l' algorithme de sélection de Hoare. Tout comme quicksort, l'algorithme quickselect est en général implémenté en place, et en plus de sélectionner le ke élément, il trie une partie des données. Comme quicksort, il est efficace en pratique avec un temps moyen de . Quickselect et ses variantes sont des algorithmes souvent utilisés dans le monde réel. (fr)
- In computer science, quickselect is a selection algorithm to find the kth smallest element in an unordered list. It is also known as the kth order statistics . It is related to the quicksort sorting algorithm. Like quicksort, it was developed by Tony Hoare, and thus is also known as Hoare's selection algorithm. Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance. Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations. (en)
- In informatica, quickselect è un algoritmo randomizzato ricorsivo che trova il k-esimo elemento di un array disordinato di grandezza n eseguendo O(n2) confronti nel caso peggiore e O(n) nel caso atteso. Si basa sull'algoritmo Quicksort e sfrutta la metodologia prune and search. L'algoritmo quicksort ha diverse relazioni di ricorrenza, dovute al tipo di problema di minore entità che si viene a creare ogni volta che l'algoritmo viene eseguito. Se ogni chiamata ricorsiva dimezza il problema, si ha: che ha soluzione O(n) in base al teorema master. (it)
|
| rdfs:label
|
- Quickselect (de)
- Quickselect (fr)
- Quickselect (it)
- 퀵셀렉트 (ko)
- クイックセレクト (ja)
- Quickselect (en)
- 快速选择 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
