Masyvo rūšiavimas didėjančia tvarka reiškia elementų išdėstymą nuo mažiausio iki didžiausio elemento. Šiame straipsnyje mes išmoksime rūšiuoti masyvą didėjimo tvarka C programavimo kalba.
Yra daug būdų, kaip masyvą galima rūšiuoti didėjančia tvarka. Kad būtų paprasčiau, šiame straipsnyje naudosime pasirinkimo rūšiavimą.
Algoritmas
Pasirinkimo rūšiavimas yra paprastas rūšiavimo algoritmas, kuris pakartotinai suranda minimalų elementą iš nerūšiuotos masyvo dalies ir deda jį rūšiuojamos masyvo dalies pradžioje, kol bus surūšiuotas visas masyvas.
- Masyvą galima rūšiuoti didėjimo tvarka, pakartotinai surandant minimalų elementą (atsižvelgiant į didėjančią tvarką) iš nerūšiuotos dalies ir dedant jį į pradžią.
- Algoritmas tam tikrame masyve palaiko dvi pogrupes.
- Pogrupis, kuris jau surūšiuotas.
- Likęs pogrupis, kuris nerūšiuotas.
- Kiekvienoje atrankos rūšiavimo iteracijoje minimalus elementas (atsižvelgiant į didėjančią tvarką) iš nerūšiuoto poskirčio yra parenkamas ir perkeliamas į surūšiuotą pogrupį.
Žiūrėkite visą straipsnį apie Pasirinkimas Rūšiuoti daugiau detalių!
Masyvo rūšiavimo programa C
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; }> |
tokias svetaines kaip bedpage
>
>Išvestis
Original array: 0 23 14 12 9 Sorted array in Ascending order: 0 9 12 14 23>
Sudėtingumo analizė
- Laiko sudėtingumas: O(N2) Pagalbinė erdvė: O(1)