Tässä opetusohjelmassa opit, kuinka lajittelu lasketaan. Löydät myös toimivia esimerkkejä lajittelun laskemisesta C, C ++, Java ja Python.
Laskulajittelu on lajittelualgoritmi, joka lajittelee matriisin elementit laskemalla taulukon kunkin yksittäisen elementin esiintymien määrän. Laskenta tallennetaan apuryhmään ja lajittelu tapahtuu kartoittamalla määrä apuryhmän indeksinä.
Kuinka lajittelun laskeminen toimii?
- Selvitä suurin elementti (anna sen olla
max) annetusta taulukosta.
Annettu taulukko - Alusta matriisi, jonka pituus
max+1on kaikki elementit 0. Tätä taulukkoa käytetään taulukon elementtien määrän tallentamiseen.
Laske taulukko - Säilytä kunkin elementin määrä niiden vastaavassa hakemistossa
counttaulukossa
. Esimerkiksi: jos elementin 3 määrä on 2, 2 tallennetaan laskuriryhmän 3. sijaintiin. Jos elementtiä "5" ei ole taulukossa, 0 tallennetaan 5. sijaintiin.
Jokaisen tallennetun elementin määrä - Tallenna laskuriryhmän elementtien kumulatiivinen summa. Se auttaa sijoittamaan elementit lajiteltujen taulukoiden oikeaan hakemistoon.
Kumulatiivinen määrä - Etsi alkuperäisen taulukon kunkin elementin hakemisto laskentataulukosta. Tämä antaa kumulatiivisen määrän. Aseta elementti indeksille, joka on laskettu alla olevan kuvan mukaisesti.
Lasketaan lajittelu - Kun olet asettanut jokaisen elementin oikeaan asentoonsa, vähennä sen määrää yhdellä.
Laskulajittelualgoritmi
countingSort (matriisi, koko) max <- etsi taulukon suurin elementti alusta laskentataulukko kaikilla nollilla j <- 0 koon mukaan etsi kunkin yksilöllisen elementin kokonaismäärä ja tallenna määrä j: n hakemistoon laskuriryhmässä i <- 1 löytääksesi kumulatiivisen summan enimmäismäärään ja tallentaen sen itse laskentaryhmään j <- koko alas 1: een palauttamaan elementit kunkin palautetun elementin matriisin vähennyslaskelmaksi
Python-, Java- ja C / C ++ -esimerkkejä
Python Java C C ++ # Counting sort in Python programming def countingSort(array): size = len(array) output = (0) * size # Initialize count array count = (0) * 10 # Store the count of each elements in count array for i in range(0, size): count(array(i)) += 1 # Store the cummulative count for i in range(1, 10): count(i) += count(i - 1) # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i>= 0: output(count(array(i)) - 1) = array(i) count(array(i)) -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array(i) = output(i) data = (4, 2, 2, 8, 3, 3, 1) countingSort(data) print("Sorted Array in Ascending Order: ") print(data)
// Counting sort in Java programming import java.util.Arrays; class CountingSort ( void countSort(int array(), int size) ( int() output = new int(size + 1); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); // Initialize count array with all zeros. for (int i = 0; i < max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Driver code public static void main(String args()) ( int() data = ( 4, 2, 2, 8, 3, 3, 1 ); int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Counting sort in C programming #include void countingSort(int array(), int size) ( int output(10); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count(10); // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // 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 array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countingSort(array, n); printArray(array, n); )
// Counting sort in C++ programming #include using namespace std; void countSort(int array(), int size) ( // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output(10); int count(10); int max = array(0); // Find the largest element of the array for (int i = 1; i max) max = array(i); ) // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countSort(array, n); printArray(array, n); )
Monimutkaisuus
Ajan monimutkaisuus:
Pääsilmukoita on pääasiassa neljä. (Suurimman arvon löytäminen voidaan tehdä toiminnon ulkopuolella.)
| for-silmukka | laskennan aika |
|---|---|
| 1 | O (enintään) |
| 2. | O (koko) |
| 3. | O (enintään) |
| 4. päivä | O (koko) |
Kokonais monimutkaisuus = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Pahimman tapauksen monimutkaisuus:
O(n+k) - Parhaan tapauksen monimutkaisuus:
O(n+k) - Keskimääräinen tapauksen monimutkaisuus:
O(n+k)
Kaikissa edellä mainituissa tapauksissa monimutkaisuus on sama, koska riippumatta siitä, miten elementit sijoitetaan matriisiin, algoritmi käy läpi n+kaikoja.
Elementtien välillä ei ole vertailua, joten se on parempi kuin vertailupohjainen lajittelutekniikka. Mutta on huono, jos kokonaisluvut ovat hyvin suuria, koska kyseisen kokoinen taulukko olisi tehtävä.
Avaruuden monimutkaisuus:
Laskulajittelun tilan monimutkaisuus on O(max). Mitä suurempi elementtivalikoima, sitä suurempi on avaruuden monimutkaisuus.
Lajittele sovelluksia
Laskulajittelua käytetään, kun:
- on pienempiä kokonaislukuja, joilla on useita lukuja.
- lineaarinen monimutkaisuus on tarve.
