Bu eğitimde, seçim sıralamanın nasıl çalıştığını öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da seçme sıralamanın çalışma örneklerini bulacaksınız.
Seçim sıralaması, her yinelemede sıralanmamış bir listeden en küçük öğeyi seçen ve bu öğeyi sıralanmamış listenin başına yerleştiren bir algoritmadır.
Seçim Sıralaması Nasıl Çalışır?
- İlk öğeyi olarak ayarlayın
minimum.
Minimum olarak ilk öğeyi seçin minimumİkinci element ile karşılaştırın . İkinci öğe daha küçükseminimum, ikinci öğeyi olarak atayınminimum. Üçüncü unsurla
karşılaştırınminimum. Yine, üçüncü öğe daha küçükse,minimumüçüncü öğeye atama aksi takdirde hiçbir şey yapmaz. Süreç son elemana kadar devam eder.
Kalan elemanlarla minimumu karşılaştırın- Her yinelemeden sonra
minimum, sıralanmamış listenin önüne yerleştirilir.
İlkini minimumla değiştirin - Her yineleme için, dizinleme ilk sıralanmamış öğeden başlar. Tüm öğeler doğru konumlarına yerleştirilene kadar 1-3 arasındaki adımlar tekrarlanır.
İlk yineleme 
İkinci yineleme 
Üçüncü yineleme 
Dördüncü yineleme
Seçim Sıralama Algoritması
selectionSort (dizi, boyut) tekrar (boyut - 1) kez, ilk sıralanmamış öğeyi, sıralanmamış öğelerin her biri için minimum olarak ayarlayın <geçerliMinimum ayar öğesi, ilk sıralanmamış konum sonu seçimi ile yeni minimum takas minimum öğesi olarak
Python, Java ve C / C ++ Örnekleri
Python Java C C ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
Karmaşıklık
| Döngü | Karşılaştırma Sayısı |
|---|---|
| 1 inci | (n-1) |
| 2. | (n-2) |
| 3 üncü | (n-3) |
| … | … |
| son | 1 |
Karşılaştırma sayısı: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2neredeyse eşittir .n2
Karmaşıklık =O(n2)
Ayrıca, karmaşıklığı basitçe döngü sayısını gözlemleyerek analiz edebiliriz. 2 döngü vardır, dolayısıyla karmaşıklıktır .n*n = n2
Zaman Karmaşıklıkları:
- En Kötü Durum Karmaşıklığı: Artan düzende sıralamak istiyorsak ve dizi azalan sıradaysa, en kötü durum ortaya çıkar.
O(n2) - En İyi Durum Karmaşıklığı: Dizi zaten sıralandığında ortaya çıkar
O(n2) - Ortalama Durum Karmaşıklığı: Dizinin öğeleri karışık sırada olduğunda (ne artan ne de azalan) ortaya çıkar.
O(n2)
Seçim sıralamasının zaman karmaşıklığı her durumda aynıdır. Her adımda minimum elementi bulmalı ve doğru yere koymalısınız. Dizinin sonuna ulaşılıncaya kadar minimum eleman bilinmemektedir.
Uzay Karmaşıklığı:
Uzay karmaşıklığı, O(1)fazladan bir değişkenin tempkullanılmasıdır.
Seçim Sıralama Uygulamaları
Seçim sıralaması şu durumlarda kullanılır:
- küçük bir liste sıralanacak
- takas maliyeti önemli değil
- tüm unsurların kontrol edilmesi zorunludur
- Bir belleğe yazma maliyeti, flash bellekte olduğu gibi önemlidir (yazma / takas sayısı , balon sıralamasıyla
O(n)karşılaştırıldığında )O(n2)
