Matriisin lajittelu nousevaan järjestykseen tarkoittaa elementtien järjestämistä pienimmästä elementistä suurimpaan elementtiin. Tässä artikkelissa opimme lajittelemaan taulukon nousevaan järjestykseen C-ohjelmointikielellä.
On monia tapoja, joilla taulukko voidaan lajitella nousevaan järjestykseen. Yksinkertaisuuden vuoksi käytämme tässä artikkelissa valintalajittelua.
Algoritmi
Valintalajittelu on yksinkertainen lajittelualgoritmi, joka löytää toistuvasti minimielementin taulukon lajittelemattomasta osasta ja sijoittaa sen taulukon lajitellun osan alkuun, kunnes koko taulukko on lajiteltu.
- Taulukko voidaan lajitella nousevaan järjestykseen etsimällä toistuvasti (nousevassa järjestyksessä) minimielementti lajittelemattomasta osasta ja sijoittamalla sen alkuun.
- Algoritmi ylläpitää kahta alitaulukkoa tietyssä taulukossa.
- Alaryhmä, joka on jo lajiteltu.
- Jäljellä oleva alaryhmä, joka on lajittelematon.
- Jokaisessa valintalajittelun iteraatiossa vähimmäiselementti (nousevassa järjestyksessä) poimitaan lajittelemattomasta alitaulukosta ja siirretään lajiteltuun alitaulukkoon.
Katso koko artikkeli aiheesta Valinta Lajittele Lisätietoja!
Joukkolajitteluohjelma C:ssä
C
// C program to sort the array in an> // ascending order using selection sort> #include> > void> swap(>int>* xp,>int>* yp)> {> >int> temp = *xp;> >*xp = *yp;> >*yp = temp;> }> > // Function to perform Selection Sort> void> selectionSort(>int> arr[],>int> n)> {> >int> i, j, min_idx;> > >// One by one move boundary of> >// unsorted subarray> >for> (i = 0; i // Find the minimum element in // unsorted array min_idx = i; for (j = i + 1; j if (arr[j] min_idx = j; // Swap the found minimum element // with the first element swap(&arr[min_idx], &arr[i]); } } // Function to print an array void printArray(int arr[], int size) { int i; for (i = 0; i printf('%d ', arr[i]); printf('
'); } // Driver code int main() { int arr[] = { 0, 23, 14, 12, 9 }; int n = sizeof(arr) / sizeof(arr[0]); printf('Original array:
'); printArray(arr, n); selectionSort(arr, n); printf('
Sorted array in Ascending order:
'); printArray(arr, n); return 0; }> |
>
>Lähtö
Original array: 0 23 14 12 9 Sorted array in Ascending order: 0 9 12 14 23>
Monimutkaisuusanalyysi
- Aika monimutkaisuus: O(N2) Aputila: O(1)