In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic. This includes the cases of finding the minimum, maximum, and median elements. There are O(n) (worst-case linear time) selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the nearest neighbor and shortest path problems. Many selection algorithms are derived by generalizing a sorting algorithm, and conversely some sorting algorithms can be derived as repeated application of selection.

Property Value
dbo:abstract
  • In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic. This includes the cases of finding the minimum, maximum, and median elements. There are O(n) (worst-case linear time) selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the nearest neighbor and shortest path problems. Many selection algorithms are derived by generalizing a sorting algorithm, and conversely some sorting algorithms can be derived as repeated application of selection. The simplest case of a selection algorithm is finding the minimum (or maximum) element by iterating through the list, keeping track of the running minimum – the minimum so far – (or maximum) and can be seen as related to the selection sort. Conversely, the hardest case of a selection algorithm is finding the median, and this necessarily takes n/2 storage. In fact, a specialized median-selection algorithm can be used to build a general selection algorithm, as in median of medians. The best-known selection algorithm is quickselect, which is related to quicksort; like quicksort, it has (asymptotically) optimal average performance, but poor worst-case performance, though it can be modified to give optimal worst-case performance as well. (en)
  • 25بك المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)25بك هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر ما عدا الذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. (أكتوبر 2012)25بك هذه المقالة ليس بها أي وصلات لمقالاتٍ أخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (ديسمبر 2013) خوارزمية الاختيار او selection algorithm هي لايجاد مكان عدد بالترتيب حسب التصنيف وتعد هذه الخوارزمية واحدة من أشهر الخوارزميات لانه يمكن تطبيقها بزمن خطي ولاستخداماتها المتعددة في علوم الحاسوب والطريقة التي تتم بها عن طريق الاستدعاء الذاتي او recursion (ar)
  • En ciencias de la computación, un algoritmo de selección es un algoritmo para encontrar el k-ésimo menor número en una lista o vector; a este número se le llama estadístico de orden k. Este incluye los casos de encontrar el mínimo, máximo, y la mediana. Existen algoritmos de selección O(n) (lineal en el peor caso), y algoritmos sublineales son posibles para datos estructurados; en el caso extremos, O(1) para un vector de elementos ordenados. La selección es un subproblema de otros problemas más complejos, como el problema de la búsqueda del vecino más cercano y problema del camino más corto. Muchos algoritmos de selección son derivados por generalización de algún algoritmo de ordenación, y recíprocamente algunos algoritmos de ordenación pueden derivarse de repetidas aplicaciones de selección. El caso más simple de un algoritmo de selección es encontrar el mínimo (o máximo) elemento por iteración a través de la lista, manteniendo un registro del mínimo (o máximo) en cada paso de la iteración, y puede verse relacionado al selection sort. Por el contrario, el caso más complejo de un algoritmo de selección es encontrar la mediana, y este necesariamente necesita n/2 memoria. De hecho, un algoritmo de selección especializado para la mediana puede ser usado para realizar un algoritmo de selección general, como en median of medians. El algoritmo de selección más conocido es quickselect, el cual está relacionado al quicksort; como el quicksort, tiene (asintóticamente) rendimiento óptimo en la media de los casos, pero mal rendimiento en el peor caso, no obstante puede ser modificado para dar rendimiento óptimo en el peor caso también. (es)
  • En algorithmique, un algorithme de sélection est une méthode ayant pour but de trouver le k-ième plus petit élément d'un ensemble d'objets (étant donné un ordre et un entier k). La question de la sélection est un problème essentiel en algorithmique, notamment dans la recherche du maximum, du minimum et de la médiane. Plusieurs algorithmes ont été proposés et plusieurs contextes ont été étudiés : algorithmes en ligne, complexité amortie, complexité en moyenne, ensemble d'objet particuliers etc. Le problème de la sélection est très lié aux algorithmes de tri : l'un des algorithmes classiques, Quickselect, utilise d'ailleurs le même principe que l'algorithme de tri Quicksort. (fr)
  • 選択アルゴリズム(英: selection algorithm)とは、数列から k 番目に小さい(あるいは k 番目に大きい)数を探すアルゴリズムである。最小値、最大値、中央値を探すアルゴリズムは選択アルゴリズムの特殊なものと言える。これらを「順序統計量」とも呼ぶ。比較的単純な最小値、最大値、k 番目に小さい値を求めるアルゴリズムとしては、平均で線形時間のものが知られている。k 番目に小さい値や一度に複数の順序統計量を最悪でも線形時間で探すことも可能である。選択は最近傍探索問題や最短経路問題のようなもっと複雑な問題の部分問題である。 (ja)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 552786 (xsd:integer)
dbo:wikiPageRevisionID
  • 731468771 (xsd:integer)
dct:subject
http://purl.org/linguistics/gold/hypernym
rdf:type
rdfs:comment
  • 選択アルゴリズム(英: selection algorithm)とは、数列から k 番目に小さい(あるいは k 番目に大きい)数を探すアルゴリズムである。最小値、最大値、中央値を探すアルゴリズムは選択アルゴリズムの特殊なものと言える。これらを「順序統計量」とも呼ぶ。比較的単純な最小値、最大値、k 番目に小さい値を求めるアルゴリズムとしては、平均で線形時間のものが知られている。k 番目に小さい値や一度に複数の順序統計量を最悪でも線形時間で探すことも可能である。選択は最近傍探索問題や最短経路問題のようなもっと複雑な問題の部分問題である。 (ja)
  • In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic. This includes the cases of finding the minimum, maximum, and median elements. There are O(n) (worst-case linear time) selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the nearest neighbor and shortest path problems. Many selection algorithms are derived by generalizing a sorting algorithm, and conversely some sorting algorithms can be derived as repeated application of selection. (en)
  • 25بك المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)25بك هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر ما عدا الذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. (أكتوبر 2012)25بك هذه المقالة ليس بها أي وصلات لمقالاتٍ أخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (ديسمبر 2013) (ar)
  • En ciencias de la computación, un algoritmo de selección es un algoritmo para encontrar el k-ésimo menor número en una lista o vector; a este número se le llama estadístico de orden k. Este incluye los casos de encontrar el mínimo, máximo, y la mediana. Existen algoritmos de selección O(n) (lineal en el peor caso), y algoritmos sublineales son posibles para datos estructurados; en el caso extremos, O(1) para un vector de elementos ordenados. La selección es un subproblema de otros problemas más complejos, como el problema de la búsqueda del vecino más cercano y problema del camino más corto. Muchos algoritmos de selección son derivados por generalización de algún algoritmo de ordenación, y recíprocamente algunos algoritmos de ordenación pueden derivarse de repetidas aplicaciones de selecci (es)
  • En algorithmique, un algorithme de sélection est une méthode ayant pour but de trouver le k-ième plus petit élément d'un ensemble d'objets (étant donné un ordre et un entier k). La question de la sélection est un problème essentiel en algorithmique, notamment dans la recherche du maximum, du minimum et de la médiane. Plusieurs algorithmes ont été proposés et plusieurs contextes ont été étudiés : algorithmes en ligne, complexité amortie, complexité en moyenne, ensemble d'objet particuliers etc. (fr)
rdfs:label
  • خوارزمية الاختيار (ar)
  • Selection algorithm (en)
  • Algoritmo de Selección (es)
  • Algorithme de sélection (fr)
  • 選択アルゴリズム (ja)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbp:class of
is rdfs:seeAlso of
is foaf:primaryTopic of