método de selección

El ordenamiento por selección mejora el ordenamiento burbuja haciendo un sólo intercambio por cada pasada a través de la lista. Para hacer esto, un ordenamiento por selección busca el valor mayor a medida que hace una pasada y, después de completar la pasada, lo pone en la ubicación correcta. Al igual que con un ordenamiento burbuja, después de la primera pasada, el ítem mayor está en la ubicación correcta. Después de la segunda pasada, el siguiente mayor está en su ubicación. Este proceso continúa y requiere n−1 pasadas para ordenar los n ítems, ya que el ítem final debe estar en su lugar después de la (n−1)-ésima pasada.

La Figura 3 muestra todo el proceso de ordenamiento. En cada paso, el ítem mayor restante se selecciona y luego se pone en su ubicación correcta. La primera pasada ubica el 93, la segunda pasada ubica el 77, la tercera ubica el 55, y así sucesivamente. 

ejemplo

 using namespace std; 

void insertionSort(int arr[], int size) {

 for (int i = 1; i < size; ++i) {

 int key = arr[i];

 int j = i - 1;

 while (j >= 0 && arr[j] > key) { 

 arr[j + 1] = arr[j];

 j = j - 1; 

 } 

 arr[j + 1] = key; 

 }

 } 

void printArray(int arr[], int size) {

 for (int i = 0; i < size; ++i) {

 cout << arr[i] << " ";

 }

 cout << endl;

 }

 int main() {

 int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42}; 

 int size = sizeof(arr) / sizeof(arr[0]);

 cout << "Lista original: "; 

 printArray(arr, size);

 insertionSort(arr, size);

 cout << "Lista ordenada: ";

 printArray(arr, size);

 return 0;

 }