खोज…
टिप्पणियों
कंप्यूटर विज्ञान में, एक चयन प्रकार एक छँटाई एल्गोरिथ्म है, विशेष रूप से एक इन-प्लेस तुलना प्रकार। इसमें O (n 2 ) समय की जटिलता है, जो इसे बड़ी सूचियों पर अक्षम बनाता है, और आमतौर पर समान सम्मिलन के प्रकार से भी बदतर प्रदर्शन करता है। चयन प्रकार इसकी सादगी के लिए जाना जाता है, और इसमें कुछ स्थितियों में अधिक जटिल एल्गोरिदम पर प्रदर्शन लाभ हैं, विशेष रूप से जहां सहायक मेमोरी सीमित है।
नीचे दी गई छवि दिखाती है कि चयन प्रकार कैसे काम करता है-
छद्म कोड के नीचे एक कार्यक्रम (किसी भी भाषा में) बनाने या चयन प्रकार को समझने में मदद करता है।
procedure selection sort
list : array of items
n : size of list
for i = 1 to n - 1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
लाभ:
- यह समझना बहुत आसान है
- यह एक छोटी सूची पर अच्छा प्रदर्शन करता है
- मूल सूची को रखने के लिए जो आवश्यक है उससे परे कोई अतिरिक्त अस्थायी भंडारण की आवश्यकता नहीं है
छवि संदर्भ: RMIT विश्वविद्यालय
चयन सॉर्ट (पायथन)
चयन प्रकार कैसे काम करता है यह दिखाने के लिए एनीमेशन
नीचे का उदाहरण पायथन में चयन प्रकार को दर्शाता है
def sort_selection(my_list):
for pos_upper in xrange( len(my_list)-1, 0, -1):
max_pos = 0
for i in xrange(1, pos_upper + 1):
if(my_list[i] > my_list[max_pos]):
max_pos = i
print "resetting max_pos = " + str(max_pos)
my_list[pos_upper], my_list[max_pos] = my_list[max_pos], my_list[pos_upper]
print "pos_upper: " + str(pos_upper) + " max_pos: " + str(max_pos) + " my_list: " + str(my_list)
return my_list
if __name__ == "__main__":
my_list = [54,26,93,17,77,31,44,55,20]
print "my_list: " + str(my_list)
print sort_selection(my_list)
कार्यक्रम का आउटपुट:
my_list: [54, 26, 93, 17, 77, 31, 44, 55, 20]
resetting max_pos = 2
pos_upper: 8 max_pos: 2 my_list: [54, 26, 20, 17, 77, 31, 44, 55, 93]
resetting max_pos = 4
pos_upper: 7 max_pos: 4 my_list: [54, 26, 20, 17, 55, 31, 44, 77, 93]
resetting max_pos = 4
pos_upper: 6 max_pos: 4 my_list: [54, 26, 20, 17, 44, 31, 55, 77, 93]
pos_upper: 5 max_pos: 0 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
resetting max_pos = 4
pos_upper: 4 max_pos: 4 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
pos_upper: 3 max_pos: 0 my_list: [17, 26, 20, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 2 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 1 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
छवि संदर्भ: समुद्री डाकू शिक्षार्थी
चयन सॉर्ट (जावा)
चयन प्रकार कैसे काम करता है यह दिखाने के लिए एनीमेशन
नीचे उदाहरण आरोही क्रम में चयन प्रकार दिखाता है:
public class MySelectionSort {
public static int[] doSelectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return arr;
}
मैंने चयन प्रकार के आउटपुट को दिखाने के लिए एक नमूना main() विधि लिखी है:
public static void main(String a[]){
int[] arr1 = {10,34,2,56,7,67,88,42};
int[] arr2 = doSelectionSort(arr1);
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}
कार्यक्रम का आउटपुट:
2, 7, 10, 34, 42, 56, 67, 88
उदाहरण नीचे अवरोही क्रम में चयन प्रकार दिखाता है:
public static void doDescendingSelectionSort ( int [ ] num )
{
int i, j, first, temp;
for ( i = num.length - 1; i > 0; i - - )
{
first = 0; //initialize to subscript of first element
for(j = 1; j <= i; j ++) //locate smallest element between positions 1 and i.
{
if( num[ j ] < num[ first ] )
first = j;
}
temp = num[ first ]; //swap smallest found with element in position i.
num[ first ] = num[ i ];
num[ i ] = temp;
}
}
चित्र संदर्भ: विकिपीडिया