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

C++C++Beginner
Практиковаться сейчас

💡 Этот учебник переведен с английского с помощью ИИ. Чтобы просмотреть оригинал, вы можете перейти на английский оригинал

Введение

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


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("C++")) -.-> cpp/BasicsGroup(["Basics"]) cpp(("C++")) -.-> cpp/ControlFlowGroup(["Control Flow"]) cpp(("C++")) -.-> cpp/AdvancedConceptsGroup(["Advanced Concepts"]) cpp(("C++")) -.-> cpp/IOandFileHandlingGroup(["I/O and File Handling"]) cpp/BasicsGroup -.-> cpp/operators("Operators") cpp/BasicsGroup -.-> cpp/arrays("Arrays") cpp/ControlFlowGroup -.-> cpp/for_loop("For Loop") cpp/ControlFlowGroup -.-> cpp/while_loop("While Loop") cpp/AdvancedConceptsGroup -.-> cpp/pointers("Pointers") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/IOandFileHandlingGroup -.-> cpp/user_input("User Input") cpp/IOandFileHandlingGroup -.-> cpp/files("Files") subgraph Lab Skills cpp/operators -.-> lab-96119{{"Сортировка вставками с использованием динамического массива"}} cpp/arrays -.-> lab-96119{{"Сортировка вставками с использованием динамического массива"}} cpp/for_loop -.-> lab-96119{{"Сортировка вставками с использованием динамического массива"}} cpp/while_loop -.-> lab-96119{{"Сортировка вставками с использованием динамического массива"}} cpp/pointers -.-> lab-96119{{"Сортировка вставками с использованием динамического массива"}} cpp/output -.-> lab-96119{{"Сортировка вставками с использованием динамического массива"}} cpp/user_input -.-> lab-96119{{"Сортировка вставками с использованием динамического массива"}} cpp/files -.-> lab-96119{{"Сортировка вставками с использованием динамического массива"}} end

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

Сначала нам нужно создать динамический массив целых чисел с размером, определяемым пользователем, и заполнить его случайными целыми числами от 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++. Мы создали динамический массив с размером, определяемым пользователем, заполнили его случайными целыми числами, реализовали алгоритм сортировки вставками и, наконец, вывели отсортированный массив для пользователя. Мы также узнали, как освободить память, используемую динамическим массивом.