Мастерство в сортировке выбором на C++

Введение

В этом лабе вы научитесь выполнять сортировку выбором для сортировки неотсортированного динамического массива на 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(("C++")) -.-> cpp/SyntaxandStyleGroup(["Syntax and Style"]) cpp/BasicsGroup -.-> cpp/operators("Operators") cpp/BasicsGroup -.-> cpp/arrays("Arrays") cpp/ControlFlowGroup -.-> cpp/for_loop("For Loop") cpp/AdvancedConceptsGroup -.-> cpp/pointers("Pointers") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/IOandFileHandlingGroup -.-> cpp/user_input("User Input") cpp/IOandFileHandlingGroup -.-> cpp/files("Files") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("Code Formatting") subgraph Lab Skills cpp/operators -.-> lab-96170{{"Сортировка выбором динамического массива на C++"}} cpp/arrays -.-> lab-96170{{"Сортировка выбором динамического массива на C++"}} cpp/for_loop -.-> lab-96170{{"Сортировка выбором динамического массива на C++"}} cpp/pointers -.-> lab-96170{{"Сортировка выбором динамического массива на C++"}} cpp/output -.-> lab-96170{{"Сортировка выбором динамического массива на C++"}} cpp/user_input -.-> lab-96170{{"Сортировка выбором динамического массива на C++"}} cpp/files -.-> lab-96170{{"Сортировка выбором динамического массива на C++"}} cpp/code_formatting -.-> lab-96170{{"Сортировка выбором динамического массива на C++"}} end

Создайте новый файл на C++

Сначала создайте новый файл на C++, названный main.cpp, в директории ~/project.

touch ~/project/main.cpp

Реализуйте алгоритм сортировки выбором

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

#include <iostream>
using namespace std;

// функция для обмена позиций двух элементов
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// функция для выполнения алгоритма сортировки выбором
void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // Для сортировки по убыванию измените > на < в этой строке.
      // Выбирайте минимальный элемент на каждой итерации.
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // поместите min в правильную позицию
    swap(&array[min_idx], &array[step]);
  }
}

В этом блоке кода мы определяем функцию swap() для обмена позиций двух элементов в массиве и функцию selectionSort() для выполнения алгоритма сортировки выбором на массиве.

Введите массив

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

// driver code
int main() {
  int size;
  cout<<"Enter the size of the array: ";
  cin>>size; //input the size of array
  int* data = new int[size]; //Dynamically declare array

  // Input the elements of the array one by one
  for(int i = 0; i < size; i++) {
    cout<<"Enter element "<<i+1<<" : ";
    cin>>data[i];
  }

Выполните сортировку выбором

Теперь, когда у нас есть неотсортированный массив, мы можем выполнить алгоритм сортировки выбором на нем с использованием функции selectionSort(), которую мы определили ранее. Вот, как это сделать:

  // Perform selection sort
  selectionSort(data, size);

Выведите отсортированный массив

Наконец, мы выведем отсортированный массив в консоль с использованием цикла в функции printArray(). Вот, как это сделать:

  // Output the sorted array
  cout << "\nSorted array: ";
  for (int i = 0; i < size; i++)
    cout << data[i] << " ";

  // Free memory used by the dynamic array
  delete[] data;
  return 0;
}

Скомпилируйте и запустите код

Для компиляции и запуска кода откройте терминал и перейдите в папку, где хранится ваш файл main.cpp. Затем выполните следующие команды:

g++ main.cpp -o main
./main

Отсортированный массив должен быть отображен в консоли.

Резюме

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