Сортировка вставками с использованием динамического массива

Введение

В этом лабе мы научимся реализовывать алгоритм сортировки вставками с использованием динамических массивов на C++. Этот алгоритм является простым алгоритмом сортировки, который работает путём разделения списка на две части: отсортированную и неотсортированную, а затем вставки каждого элемента неотсортированного списка в отсортированный список в правильную позицию.

Создание динамического массива

Сначала нам нужно создать динамический массив целых чисел с размером, определяемым пользователем, и заполнить его случайными целыми числами от 1 до 100.

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int *arr;
    int size, i;

    cout << "Enter the size of the array: ";
    cin >> size;

    // create dynamic array
    arr = new int[size];

    // fill array with random integers between 1 and 100
    for(i=0; i<size; i++) {
        arr[i] = rand() % 100 + 1;
    }

Отображение неотсортированного массива

Далее мы выведем содержимое неотсортированного массива для пользователя.

    // display unsorted array
    cout << "Unsorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

Реализация алгоритма сортировки вставками

Теперь мы реализуем алгоритм сортировки вставками, который отсортирует массив по возрастанию.

    // insertion sort
    int j, temp;
    for(i=1; i<size; i++) {
        temp = arr[i];
        j = i - 1;
        while(j>=0 && arr[j]>temp) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }

Отображение отсортированного массива

Мы выведем содержимое отсортированного массива для пользователя.

    // display sorted array
    cout << "Sorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

Освобождение памяти

Наконец, мы освободим память, используемую динамическим массивом.

    // free memory
    delete [] arr;

    return 0;
}

Компилировать и запустить программу

Сохраните файл под именем "sort.cpp" в директории ~/project.

Компилируйте и запускаете программу в терминале:

$ cd ~/project
$ g++ sort.cpp -o sort
$./sort

Резюме

В этом практическом занятии мы узнали, как реализовать алгоритм сортировки вставками с использованием динамических массивов на C++. Мы создали динамический массив с размером, определяемым пользователем, заполнили его случайными целыми числами, реализовали алгоритм сортировки вставками и, наконец, вывели отсортированный массив для пользователя. Мы также узнали, как освободить память, используемую динамическим массивом.