SEÇIM SIRALAMASI - DS EĞITIMI

Bu yazımızda Seçim sıralama Algoritmasını ele alacağız. Seçim sıralamasının çalışma prosedürü de basittir. Bu makale, sınavlarında soru olarak seçmeli sıralamayla karşılaşabilecekleri için öğrenciler için çok yararlı ve ilginç olacaktır. Bu nedenle konuyu tartışmak önemlidir.

Seçimli sıralamada her geçişte dizinin sıralanmamış elemanları arasından en küçük değer seçilir ve dizide uygun konumuna eklenir. Aynı zamanda en basit algoritmadır. Yerinde bir karşılaştırma sıralama algoritmasıdır. Bu algoritmada dizi iki parçaya bölünür; birincisi sıralanmış kısım, diğeri ise sıralanmamış kısımdır. Başlangıçta dizinin sıralanan kısmı boştur ve sıralanmayan kısım verilen dizidir. Sıralanan kısım sola, sıralanmayan kısım ise sağa yerleştirilir.

Seçimli sıralamada, sıralanmamış diziden ilk en küçük eleman seçilir ve ilk konuma yerleştirilir. Daha sonra ikinci en küçük eleman seçilir ve ikinci konuma yerleştirilir. İşlem dizi tamamen sıralanıncaya kadar devam eder.

Seçim sıralamasının ortalama ve en kötü durum karmaşıklığı Açık²) , Neresi N öğelerin sayısıdır. Bu nedenle büyük veri setleri için uygun değildir.

Seçimli sıralama genellikle aşağıdaki durumlarda kullanılır:

Küçük bir dizi sıralanacak
Değiştirme maliyeti önemli değil
Tüm unsurların kontrol edilmesi zorunludur

Şimdi seçim sıralama algoritmasını görelim.

Algoritma

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL &gt; arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos

Seçim Sıralama Algoritmasının Çalışması

Şimdi Seçim sıralama Algoritmasının çalışmasına bakalım.

Seçim sıralama algoritmasının çalışmasını anlamak için sıralanmamış bir diziyi ele alalım. Bir örnek üzerinden Seçim sıralamasını anlamak daha kolay olacaktır.

Dizinin elemanları şöyle olsun:

Şimdi, sıralanan dizideki ilk konum için dizinin tamamı sırayla taranacaktır.

Şu anda, 12 ilk konumda saklanır, dizinin tamamı arandıktan sonra şu bulunur: 8 en küçük değerdir.

Onlar şarkıcılar

Yani, 12'yi 8 ile değiştirin. İlk yinelemeden sonra, sıralanan dizinin ilk konumunda 8 görünecektir.

Şu anda 29'un depolandığı ikinci konum için, sıralanmamış dizinin geri kalan öğelerini tekrar sırayla tararız. Taramadan sonra, dizide ikinci konumda görünmesi gereken ikinci en düşük öğenin 12 olduğunu bulduk.

Şimdi 29'u 12 ile değiştirin. İkinci yinelemeden sonra sıralanan dizinin ikinci konumunda 12 görünecektir. Yani iki yinelemeden sonra en küçük iki değer sıralı bir şekilde başa yerleştirilir.

Aynı işlem dizi elemanlarının geri kalanına da uygulanır. Şimdi tüm ayıklama sürecinin resimli bir temsilini gösteriyoruz.

Artık dizi tamamen sıralanmıştır.

Seçim sıralama karmaşıklığı

Şimdi en iyi durum, ortalama durum ve en kötü durum sıralamasında seçimin zaman karmaşıklığını görelim. Ayrıca seçim sıralamasının alan karmaşıklığını da göreceğiz.

1. Zaman Karmaşıklığı

Dava	Zaman Karmaşıklığı
En iyi senaryo	Açık²)
Ortalama Durum	Açık²)
En kötü durumda	Açık²)

Açık²)

2. Uzayın Karmaşıklığı

Uzay Karmaşıklığı	Ç(1)
Stabil	EVET

Seçim sıralamasının uzay karmaşıklığı O(1)'dir. Bunun nedeni, seçim sıralamasında takas için fazladan bir değişkenin gerekli olmasıdır.

Seçim sıralamasının uygulanması

Şimdi farklı programlama dillerinde seçim sıralama programlarını görelim.

Program: C dilinde seçimli sıralamayı uygulayan bir program yazın.

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

Çıktı:

Program: Java'da seçimli sıralamayı uygulayan bir program yazın.

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

Çıktı:

Yukarıdaki kodun yürütülmesinden sonra çıktı şu şekilde olacaktır:

Yani bu makaleyle ilgili. Umarım makale sizin için yararlı ve bilgilendirici olacaktır.

Bu makale sadece algoritma ile sınırlı değildi. Ayrıca Seçim sıralamasının karmaşıklığını, çalışmasını ve farklı programlama dillerinde uygulanmasını da tartıştık.