Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Notoriously
69 / 69 / 35
Регистрация: 06.07.2016
Сообщений: 414
1

Рекурсивная сортировка вставкой

23.10.2017, 14:03. Просмотров 142. Ответов 0
Метки нет (Все метки)

Кормен в одном из упражнений просит написать сортировку вставкой с использованием рекурсии.
Требуется именно то что написано ниже или я неправильно понимаю его затею?
Текст задания под спойлером.
Кликните здесь для просмотра всего текста
Сортировку вставкой можно представить в виде рекурсивной последовательности. Чтобы отсортировать массив A[1..N] сначала нужно рекурсивно отсортировать массив A[1..N-1], после чего в этот отсортированный массив помещается элемент A[N].
Реализовать данный алгоритм.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
 
void printArray(const int *array, const size_t capacity);
void insertionSort(int *array, const size_t capacity);
void insertLast(int *array, const size_t last);
int main()
{
    int array[] = {-77,9919,-61661,81818,-9001,1881,1818,1,1,10,0,0,-12,-12,-888,-7171717,1818181,9710,81818,-899,-0,-11122,81818,191919,2727};
    size_t length{sizeof(array) / sizeof(*array)};
    printArray(array, length);
    insertionSort(array, length);
    printArray(array, length);
}
 
void printArray(const int *array, const size_t capacity)
{
    for(size_t index{0}; index < capacity; index++)
         {
            std::cout<<array[index]<<'\t';
         }
         std :: cout << std :: endl;
}
 
void insertionSort(int *array, const size_t capacity)
{
   if(capacity)
       {
        insertionSort(array, capacity-1);
        insertLast(array, capacity-1);
       }        
}
 
void insertLast(int *array, const size_t last)
{
         int  key{array[last]};
     int precedingIndex{last-1};
        while(precedingIndex >= 0 && key < array[precedingIndex])
            {
                array[precedingIndex+1] = array[precedingIndex];
                precedingIndex--;
            }
      array[precedingIndex+1]  = key;       
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.10.2017, 14:03
Ответы с готовыми решениями:

Сортировка вставкой
Всем привет. Задали задание написать код сортировки вставкой. Писал код по...

Сортировка вставкой
1)Дан массив состоящий из n элементов (n&lt;=100) Отсортировать методом вставки и...

Сортировка вставкой
Есть такое задание: Исходный набор данных представляет собой последовательность...

Сортировка вставкой
В файле input.txt содержатся сведения о группе студентов в формате:номер...

Сортировка вставкой
(желательно ближе к си) Определить массив из 50 вещественных чисел: x =...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.10.2017, 14:03

Сортировка вставкой
while(mc!=m) {nov=n; for(is=0;is&lt;n;is++){ for (i=nov;i&lt;n;i++){if...

Сортировка массива вставкой
Доброго времени суток. У меня вот такая задача: Вариант 13; Задание на...

Сортировка двоичной вставкой
Доброе время суток. Есть программа на pascal, выполняющая сортировку массива по...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru