algorithm
चयन छांटना
खोज…
चयन सॉर्ट बेसिक जानकारी
चयन सॉर्ट एक छँटाई एल्गोरिथ्म है, विशेष रूप से एक इन-प्लेस तुलना सॉर्ट। इसमें O (n2) समय की जटिलता है, जो इसे बड़ी सूचियों पर अक्षम बनाता है, और आमतौर पर समान सम्मिलन के प्रकार से भी बदतर प्रदर्शन करता है। चयन प्रकार इसकी सादगी के लिए जाना जाता है, और इसमें कुछ स्थितियों में अधिक जटिल एल्गोरिदम पर प्रदर्शन लाभ हैं, विशेष रूप से जहां सहायक मेमोरी सीमित है।
एल्गोरिथ्म इनपुट सूची को दो भागों में विभाजित करता है: पहले से ही सॉर्ट किए गए आइटमों की सूची, जो सूची के सामने (बाएं) पर बाएं से दाएं तक बनाई गई है, और शेष वस्तुओं की सबलिस्ट को छांटा जाना है जो बाकी हिस्सों पर कब्जा कर लेते हैं सूची। प्रारंभ में, सॉर्ट की गई सबलिस्ट खाली है और अनसेंडेड सबलिस्ट पूरी इनपुट सूची है। एल्गोरिथ्म सबसे छोटे (या सबसे बड़े, सॉर्टिंग ऑर्डर पर निर्भर करता है) तत्व को अनसुनी किए गए सबलिस्ट में तत्व के आधार पर प्राप्त करता है, इसे बाईं ओर के अनसोल्ड एलिमेंट (इसे सॉर्ट किए गए ऑर्डर में डालते हुए) से एक्सचेंज करता है, और सबलिस्ट को एक तत्व को दाईं ओर ले जाता है। ।
चयन प्रकार के लिए छद्म कोड:
function select(list[1..n], k)
for i from 1 to k
minIndex = i
minValue = list[i]
for j from i+1 to n
if list[j] < minValue
minIndex = j
minValue = list[j]
swap list[i] and list[minIndex]
return list[k]
चयन प्रकार का दृश्य:
चयन प्रकार का उदाहरण:
सहायक स्थान: O(n)
समय जटिलता: O(n^2)
C # में चयन प्रकार का कार्यान्वयन
चयन चयन एल्गोरिदम को लागू करने के लिए मैंने C # भाषा का उपयोग किया।
public class SelectionSort
{
private static void SortSelection(int[] input, int n)
{
for (int i = 0; i < n - 1; i++)
{
var minId = i;
int j;
for (j = i + 1; j < n; j++)
{
if (input[j] < input[minId]) minId = j;
}
var temp = input[minId];
input[minId] = input[i];
input[i] = temp;
}
}
public static int[] Main(int[] input)
{
SortSelection(input, input.Length);
return input;
}
}
अमृत कार्यान्वयन
defmodule Selection do
def sort(list) when is_list(list) do
do_selection(list, [])
end
def do_selection([head|[]], acc) do
acc ++ [head]
end
def do_selection(list, acc) do
min = min(list)
do_selection(:lists.delete(min, list), acc ++ [min])
end
defp min([first|[second|[]]]) do
smaller(first, second)
end
defp min([first|[second|tail]]) do
min([smaller(first, second)|tail])
end
defp smaller(e1, e2) do
if e1 <= e2 do
e1
else
e2
end
end
end
Selection.sort([100,4,10,6,9,3])
|> IO.inspect