5

/*
ЛАБОРАТОРНАЯ РАБОТА № 5
ВАРИАНТ 1
ВЫПОЛНИЛ: ДМИТРИЙ МИШУТИН КЭ - 101
*/

#include <stdio.h>
#include <iostream>
#include <time.h>
#include <stdlib.h>

using namespace std;

void my_swap(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}

void bubble_sort(int * arr, int N){ // сортировка пузырьком за O(N^2)
    for(int i = 0; i < N - 1; i++){
        for(int j = 0; j < N - i - 1; j++){
            if(arr[j] > arr[j + 1]){
                my_swap(arr[j], arr[j + 1]);
            }
        }
    }
}

void selection_sort(int * arr, int N){ // сортировка простым выбором за O(N^2)
    for(int i = 0; i < N - 1; i++){
        int index_min = i;
        for(int j = i + 1; j < N; j++){
            if(arr[j] < arr[index_min]){
                index_min = j;
            }
        }
        my_swap(arr[i], arr[index_min]);
    }
}

int main(){
    setlocale(0, "");

    const int N = 10000;
    int * arr1 = (int *) malloc(N * sizeof(int));
    int * arr2 = (int *) malloc(N * sizeof(int));

    srand(time(0));
    for(int i = 0; i < N; i++){
        arr1[i] = rand() % 101;
        arr2[i] = arr1[i];
    }

    int t1 = clock();
    bubble_sort(arr1, N);
    printf("Сортировка пузырьком: %lf секунд\n", (double) (clock() - t1) / CLOCKS_PER_SEC);

    int t2 = clock();
    selection_sort(arr2, N);
    printf("Сортировка пузырьком: %lf секунд\n", (double) (clock() - t2) / CLOCKS_PER_SEC);

    /*for(int i = 0; i < N; i++){
        cout << arr1[i] << " ";
    }
    cout << endl;

    for(int i = 0; i < N; i++){
        cout << arr2[i] << " ";
    }
    cout << endl;*/

    free(arr1);
    free(arr2);

    system("PAUSE");
    return 0;
}