Bu eğitimde, radix sıralamanın nasıl çalıştığını öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da radix sıralamanın çalışma örneklerini bulacaksınız.
Sayı tabanı sıralaması, ilk olarak aynı basamak değerinin ayrı basamaklarını gruplayarak öğeleri sıralayan bir sıralama tekniğidir . Ardından öğeleri artan / azalan sıralarına göre sıralayın.
Diyelim ki 8 elemanlı bir dizimiz var. İlk olarak, öğeleri birim yerinin değerine göre sıralayacağız. Ardından, öğeleri onuncu yerin değerine göre sıralayacağız. Bu süreç son önemli yere kadar devam eder.
İlk dizi olsun (121, 432, 564, 23, 1, 45, 788). Aşağıdaki şekilde gösterildiği gibi radix sıralamasına göre sıralanır.
Radix Sıralamanın Çalışması
Lütfen bu makaleyi okumadan önce sayma sıralamasını gözden geçirin çünkü sayma sıralaması, radix sıralamasında bir ara sıralama olarak kullanılır.
Radix Sıralaması Nasıl Çalışır?
- Dizideki en büyük elemanı bulun, yani maks. Izin vermek
Xbasamak sayısı olsunmax.Xhesaplanır çünkü tüm unsurların tüm önemli yerlerinden geçmemiz gerekir.
Bu dizide(121, 432, 564, 23, 1, 45, 788)en büyük sayı 788'e sahibiz. 3 hanesi var. Bu nedenle döngü yüzlerce haneye (3 defa) kadar çıkmalıdır. - Şimdi her önemli yeri tek tek gözden geçirin.
Her önemli yerde rakamları sıralamak için herhangi bir kararlı sıralama tekniğini kullanın. Bunun için sayma sıralaması kullandık.
Öğeleri birim basamak basamaklarına (X=0) göre sıralayın .
Öğeleri birim yerine göre sıralamak için sayma sıralamasını kullanma - Şimdi, elemanları onlar basamağındaki rakamlara göre sıralayın.
Öğeleri onlar basamağına göre sıralayın - Son olarak, öğeleri yüzlerce basamaktaki rakamlara göre sıralayın.
Öğeleri yüzlerce yere göre sıralayın
Radix Sıralama Algoritması
radixSort (array) d <- en büyük elemandaki maksimum basamak sayısı, i <- 0 ila d için 0-9 boyutunda d kova oluşturur, sayıları kullanarak öğeleri iinci basamak basamaklarına göre sıralarSort countingSort (array, d) max <- find dth basamak elemanları arasındaki en büyük eleman, sayım dizisini j <- 0 için tümü sıfır ile başlatır, elemanların dth sırasındaki her bir benzersiz basamağın toplam sayısını bulur ve i <- 1 ila max bulmak için jth dizindeki sayımı saklar. kümülatif toplam ve bunu say dizisinde saklayın j <- boyut 1'e kadar öğeleri diziye geri yükleyin, geri yüklenen her öğenin sayısını 1 azaltın
Python, Java ve C / C ++ Örnekleri
Python Java C C ++ # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data)
// Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // 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 array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
// Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
Karmaşıklık
Taban sıralaması karşılaştırmalı olmayan bir algoritma olduğundan, karşılaştırmalı sıralama algoritmalarına göre avantajları vardır.
Sayma sıralamasını ara kararlı sıralama olarak kullanan taban sıralaması için zaman karmaşıklığıdır O(d(n+k)).
Burada dsayı döngüsü ve O(n+k)sayma sıralamanın zaman karmaşıklığı.
Dolayısıyla, taban sıralaması, O(nlog n)karşılaştırmalı sıralama algoritmalarından daha iyi olan doğrusal zaman karmaşıklığına sahiptir .
Çok büyük rakamlı sayıları veya 32-bit ve 64-bit sayılar gibi diğer tabanların sayısını alırsak, doğrusal zamanda işleyebilir ancak ara sıralama büyük yer kaplar.
Bu, radix sıralama alanını verimsiz kılar. Yazılım kitaplıklarında bu türün kullanılmamasının nedeni budur.
Radix Sıralama Uygulamaları
Radix sıralama,
- Bir sonek dizisi oluştururken DC3 algoritması (Kärkkäinen-Sanders-Burkhardt).
- büyük aralıklarda sayıların olduğu yerler.
