Paras vastaus
Kuplalajittelu
Bubble Sort on yksinkertaisin lajittelualgoritmi, joka toimii vaihtamalla toistuvasti vierekkäisiä elementtejä, jos ne ovat väärässä järjestyksessä.
Esimerkki: Ensimmäinen syöttö: ( 5 1 4 2 8) -> ( 1 5 4 2 8), Tässä algoritmi vertaa kahta ensimmäistä elementtiä ja vaihtaa välillä 5> 1. (1 5 4 2 8) -> (1 4 5 2 8), Vaihda 5 jälkeen > 4 (1 4 5 2 8) -> (1 4 2 5 8), Vaihda vuodesta 5> 2 (1 4 2 5 8 ) -> (1 4 2 5 8 ), koska nämä elementit ovat jo kunnossa (8> 5), algoritmi ei vaihda niitä.
Toinen passi: ( 1 4 2 5 8) -> ( 1 4 2 5 8) (1 4 2 5 8) -> (1 2 4 5 8), Vaihda vuodesta 4> 2 (1 2 4 5 8) -> (1 2 4 5 8) (1 2 4 5 8 ) -> (1 2 4 5 8 ) Nyt taulukko on jo lajiteltu, b Algoritmimme ei tiedä onko se valmis. Algoritmi tarvitsee yhden kokonaisen passin ilman mitään -vaihtoa tietääkseen, että se on lajiteltu.
Kolmas pääsy: ( 1 2 4 5 8) -> ( 1 2 4 5 8) (1 2 4 5 8) -> (1 2 4 5 8) (1 2 4 5 8) -> (1 2 4 5 8) (1 2 4 5 8 ) -> (1 2 4 5 8 )
Esimerkki
// C program for implementation of Bubble sort
#include
void *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("\%d ", arr[i]);
printf("n");
}
// Driver program to test above functions
int main()
{
int arr[] = {66, 4, 25, 1, 22, 81, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Kiitos.
Vastaus
Minulle helpoin lajittelualgoritmi on valintalajittelu, hyvin yksinkertainen ja ymmärrettävä.Kun suoritat valintalajittelualgoritmin, aiot verrata kaikkia arvoja ensimmäiseen elementtiin, kun löydetty arvo on pienempi kuin ensimmäinen elementti, muutat alimman arvon sisältävää elementtiä, ja se jatkuu näin.
Annan sinulle esimerkin.
Array => [15,3,22,1,4,14]
min = 15.
- vertaa 15: een, min = 15
- vertaa 3: een, min = 3
- vertaa 22: een, min = 3
- vertaa 1, min = 1
- vertaa 4, min = 1
- vertaa 14, min = 1
Nyt olet löytänyt elementin min (first\_index). Sinun täytyy korvata ensimmäinen elementti ja min-elementin paikat ja jatkaa sitten, kunnes saavut viimeisen elementin.
Esimerkki C-koodi:
#include
void printArray(int arr[], int n) {
//use this function to print array
for (int i = 0; i < n; i++)
printf("\%d, ", arr[i]);
}
void sortArray(int arr[], int n) {
int min\_index = 0;
int temp = 0;
for (int i = 0; i < n; i++) {
min\_index = i;
for (int j = i; j < n; j++) {
//compare min index"s element with new j"s element
//if you want descending sort you can change the binary
//operator > to < .
if (arr[min\_index] > arr[j]) min\_index = j;
}
//change min index"s element and i. element
temp = arr[min\_index];
arr[min\_index] = arr[i];
arr[i] = temp;
}
printArray(arr,n);
}
int arr[] = { 100,5,11,1,22,31,4,2,3 }; //initialize array
printArray(arr,9); //print unsorted array
sortArray(arr,9); //sort array then print it
return 0;
}