Lab7/Part2/21.cpp - master - Oppq/Labs

Lab7/Part2/21.cpp
304 строки6 KB
Oppq
final upd
28 апр 2026, 20:22
28 апр 2026, 20:220b78dc6
// Задание 1 - Линейный поиск. (из методички)

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
int main() 
{
    int N;
    cin>>N;
    
    vector<int> arr(N); // изменено, сразу в массив
    
    for (int i(0); i<N; i++)
    {
        cin>> arr[i];  // изменено
    }
    
    int X;
    cin >> X;
    int Count=0;    
    for (int i(0); i<N; i++)
    {
     if (arr[i] == X) Count++;
    }    
    cout << Count;    
    return 0;
}


// Задание 2 - Бинарный поиск - Есть ошибка, пока идея

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int N, K;
    cin >> N >> K;

    vector<int> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    for (int h = 0; h < K; h++)
        {
            int x; 
            cin >> x;
            int left = 0;
            int right = N - 1;
            bool found = false;

            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (arr[mid] == x)
                {
                    found = true;
                    break; // break был вызван глобально во всём цикле while
                }
                if (arr[mid] < x)
                    left = mid + 1;
                else { right = mid - 1; }
            }

            if (found)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    return 0;
}

// Задание 3 - Пузырьковая сортировка и кол-во обменов (взято на практике, доработано через функцию)

#include <iostream>
#include <vector>
using namespace std;

int bubbleSortWithCount(vector<int>& arr) 
{
    int n = arr.size();
    int swapCount = 0;  // счётчик обменов
    
    for (int i = 0; i < n - 1; i++) 
    {
        for (int j = 0; j < n - 1 - i; j++) 
        {
            if (arr[j] > arr[j + 1]) 
            {
                swap(arr[j], arr[j + 1]);
                swapCount++;
            }
        }
    }
    
    return swapCount;
}


int main()
{
    int N;
    cin >> N;
    vector<int> arr1(N);
    for(int i = 0; i < N; i ++)
    {
    cin >> arr1[i];
    }
    
    int swaps = bubbleSortWithCount(arr1);
    cout << swaps << endl;
    return 0;
}

// Задание 4 - Сортировка вставками (тоже бралось на практике, доработано)

#include <iostream>
#include <vector>
#include <iostream>
#include <vector>
using namespace std;

void iS(vector<int>& arr) {
    int n = arr.size();
    
    for (int j = 1; j < n; j++) {
        int tmp = arr[j];
        int i = j - 1;
        
        while (i >= 0 && tmp < arr[i]) {
            arr[i + 1] = arr[i];
            i--;
        }
        
        arr[i + 1] = tmp;
    }
}

int main() {
    int N;
    cin >> N;
    if (N >= 1000) return 1;
    
    vector<int> arr1(N);
    
    for(int i = 0; i < N; i++)
    {
    cin >> arr1[i];
    }
    
    
    iS(arr1);
    
    for (int x : arr1) {
        cout << x << " ";
    }
    
    return 0;
}

// Задание 5 - Cам алгоритм быстрой сортировки, не по заданию.

#include <iostream>
#include <vector>
using namespace std;

void quickSort(vector<int>& arr, int first, int last)
{
    if (first >= last) return;
    int pivot = arr[(first + last) / 2];
    int f = first;
    int l = last;
    
    while (f <= l) 
    {
        while (arr[f] < pivot) f++;
        while (arr[l] > pivot) l--;
        
        if (f <= l) {
            swap(arr[f], arr[l]);
            f++;
            l--;
        }
    }
    
    if (first < l) quickSort(arr, first, l);
    if (f < last) quickSort(arr, f, last);

}
int main() 
{
   int N;
   cin >> N;
   vector<int> arr1(N);
   for(int i = 0; i < N; i++)
   {
       cin >> arr1[i];
   }
   return 0;
}

// Задание 6 - Сортировка слиянием, идея по примеру из мудла

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& a, int l, int m, int r) 
{
    vector<int> left(a.begin() + l, a.begin() + m + 1);
    vector<int> right(a.begin() + m + 1, a.begin() + r + 1);
    
    int i = 0, j = 0, k = l;
    
    while (i < left.size() && j < right.size()) 
    {
        if (left[i] <= right[j]) {a[k++] = left[i++];}
        else {a[k++] = right[j++];}
    }
    
    while (i < left.size()) {a[k++] = left[i++];}
    while (j < right.size()) {a[k++] = right[j++];}
}

void mergeSort(vector<int>& a, int l, int r) 
{
    if (l >= r) return;
    
    int m = (l + r) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) 
        {cin >> a[i];}
    
    mergeSort(a, 0, n - 1);
    
    for (int x : a) {cout << x << " ";}
    
    return 0;
}

// Задание 7 - Пирамидальная сортировка

#include <iostream>
#include <vector>
using namespace std;

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) {largest = left;}
    if (right < n && arr[right] > arr[largest]) {largest = right;}
    
    if (largest != i) 
    {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) 
{
    int n = arr.size();
    
    for (int i = n / 2 - 1; i >= 0; i--)
        {
        heapify(arr, n, i);
        }
    
    for (int i = n - 1; i >= 0; i--) 
    {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() 
{
    int n;
    cin >> n;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    heapSort(arr);
    
    for (int x : arr)
        cout << x << " ";
    
    return 0;
}