Implementa un algoritmo de ordenamiento por burbuja para un arreglo de enteros.

Dado un arreglo de enteros A y su tamaño n, devuelve el arreglo ordenado.

Ejemplo de prueba:

[1,2,3,5,2,3],6

Rseultado esperado:

[1,2,2,3,3,5]

El método de burbuja compara elementos adyacentes y mueve los mayores hacia la posición final.

Implemnetación:

class BubbleSort {
public:
    int* bubbleSort(int* A, int n) {
        // código de implementación
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                if(A[i]>A[j]){
                    swap(A[i],A[j]);
                }
            } 
        }
        return A;
    }
};

Otra variante:

class BubbleSort {
public:
    int* bubbleSort(int* A, int n) {
        // código de implementación
        for(int i=0; i<n; i++){
            for(int j=n-1; j>i; j--){
                if(A[j]<A[j-1]){
                    int tmp = A[j];
                    A[j]=A[j-1];
                    A[j-1]=tmp;
                }
            }
        }
        return A;
    }
};

Versión alternativa del algoritmo de selección:

class SelectionSort {
public:
    int* selectionSort(int* A, int n) {
        // código de implementación
        for(int i=0; i<n-1; i++){
            int minIndex=i;
            for(int j=i+1; j<n; j++){
                if(A[j]<A[minIndex]){
                    minIndex=j;
                }
            }
            if(minIndex!=i){
                int temp=A[i];
                A[i]=A[minIndex];
                A[minIndex]=temp;
            }         
        }
        return A;
    }
};

Implementación de ordenamiento por inserción:

class InsertionSort {
public:
    int* insertionSort(int* A, int n) {
        // código de implementación
        for(int i=1; i<n; i++){
            for(int j=i-1; j>=0; j--){  
                if(A[j+1]<A[j]){
                    swap(A[j+1],A[j]);
                }
            }
        }
        return A;
    }
};

Allgoritmo de ordenamiento merge sort basado en recursión:

class MergeSort {
public:
    int* mergeSort(int* A, int n) {
        // código de implementación
        if( n==1){
            return A;
        }
        __mergeSort(A,0,n-1);
        return A;
    }
    //[l,r]
    void __mergeSort(int* A,int l,int r){
        if(l>=r){
            return;
        }
        int mid = (l+r)/2;
        __mergeSort(A,l,mid);
        __mergeSort(A,mid+1,r);
        __merge(A,l,mid,r);
    }
    // combina [l ,mid] y [mid,r]
    void __merge(int* A, int l,int mid,int r){
        int aux[r-l+1];  
        for (int i=l; i<=r; i++){
            aux[i-l] = A[i];
        }
        
        int i=l; int j = mid + 1;
        for(int k =l; k<=r; k++ ){
            if(i>mid){
                A[k]=aux[j-l];  
                j++;
            }else if(j>r){
                A[k] = aux[i-l];
                i++;
            }
            else if(aux[i-l]<aux[j-l]){
                A[k]= aux[i-l];
                i++;
            }else{
                A[k]= aux[j-l];
                j++;
            }
        }
    }
};

Ordenamiento rápido (Quick Sort):

// particiona el subarreglo arr[l...r]
// devuelve índice p tal que arr[l...p-1] < arr[p] y arr[p+1...r] > arr[p]
template <typename T>
int __partition(T arr[], int l, int r){

    T v = arr[l];

    int j = l; 
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }

    swap( arr[l] , arr[j]);

    return j;
}

// ordena el subarreglo arr[l...r]
template <typename T>
void __quickSort(T arr[], int l, int r){

    if( l >= r )
        return;

    int p = __partition(arr, l, r);
    __quickSort(arr, l, p-1 );
    __quickSort(arr, p+1, r);
}

template <typename T>
void quickSort(T arr[], int n){

    __quickSort(arr, 0, n-1);
}