Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
madendinara
0 / 0 / 0
Регистрация: 11.09.2016
Сообщений: 5
1

Реализовать сортировку выбором с выводом максимов на каждом проходе

29.10.2016, 00:18. Просмотров 827. Ответов 7
Метки нет (Все метки)

{вырезано} решите пожалуйста, очень прошу, сейчас нужно до утра сдать, очень прошу, можно с массивом и с вектором.

Selection Sort.

Let us work in the following manner:

- over the whole array find the position of the maximum element (5 in the case above - 0-based index of value 9);
- swap this element with the last one (because in the sorted array it should be the last, of course) - i.e. with position N-1;
- now regard the sub-array of length N-1, without the last value (which is already "in right place");
- find the position of maximum element in this sub-array (i.e. second to maximum in the whole array) - now it would be index 7 (where the value 6 resides);
- swap it with the last element in the sub-array (i.e. with position N-2);
- now regard the sub-array of the length N-2 (without two last elements) - do the following selection and swap and so on;
- algorithm ends when "sub-array" decreases to the length of 1.

Let us see an example step by step:

[3, 1, 4, 1, 5, 9, 2, 6, 5, 3] - max is 9 at position 5, swap 5-th with 9-th
[3, 1, 4, 1, 5, 3, 2, 6, 5], 9 - max is 6 at position 7, swap 7-th with 8-th
[3, 1, 4, 1, 5, 3, 2, 5], 6, 9 - max is 5 at position 4, swap 4-th with 7-th - they are equal!
[3, 1, 4, 1, 5, 3, 2], 5, 6, 9 - max is 5 at position 4, swap 4-th with 6-th
[3, 1, 4, 1, 2, 3], 5, 5, 6, 9 - max is 4 at position 2, swap 2-th with 5-th
...
[1], 1, 2, 3, 3, 4, 5, 5, 6, 9 - subarray of length 1 is reached, stop an algorithm.
Постановка Задачи.
Вы должны реализовать алгоритм, описанный выше, и распечатать индекс максимального значения при каждом проходе.
Входные данные будут содержать N Размер массива в первой строке.
Следующая строка будет содержать сам массив (все элементы будут разными).
Ответ должен содержать показатели максимумами при каждом проходе (N-1 значения).
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.10.2016, 00:18
Ответы с готовыми решениями:

Реализовать сортировку выбором
Сортировка выбором. «Дана последовательность чисел а1, а2, ..., а n. Нужно переставить элементы...

Реализовать сортировку выбором (в порядке убывания значений) для целочисленного массива
Реализовать сортировку выбором (в порядке убывания значений) для целочисленного массива arr...

Реализовать сортировку несколькими методами (перестановкой, выбором, вставкой) и оценить скорость их работы.
Дан массив. Реализовать сортировку несколькими методами (перестановкой, выбором, вставкой) и...

При каждом проходе брекпойнта функция клика дублируется
Подскажите, почему у меня при каждом проходе брекпойнта <1070px событе клика дублируется, т.е. при...

Парсинг файлов в цикле, обращение на каждом проходе к Awesomium
Если обрабатываю один файл, то все успешно идет, то есть текст вставляю в браузер Awesomium....

7
OlafNestandart
54 / 54 / 31
Регистрация: 24.10.2016
Сообщений: 186
29.10.2016, 00:49 2
Так что ли?
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
#include <cstddef>
#include <algorithm>
#include <iostream>
 
template <typename T>
void selection_sort(T* arr, size_t size) {
    if (size > 0) {
        T max = arr[0];
        size_t index = 0;
        for (size_t i = 0; i < size; i++) {
            if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        if (index != --size)
            std::swap(arr[index], arr[size]);
        selection_sort(arr, size);
    }
}
 
int main() {
    int arr[] = {5, 3, 9, 7, 1};
    selection_sort(arr, 5);
    for (int i = 0; i < 5; i++)
        std::cout << arr[i] << " ";
}
0
madendinara
0 / 0 / 0
Регистрация: 11.09.2016
Сообщений: 5
29.10.2016, 00:57  [ТС] 3
как по инпутам и аутпутам, там ответ должен содержать число проходов, то есть сколько раз должен пройтись цикл, можете по задаче решить, прям то же самое, пожалуйста
0
OlafNestandart
54 / 54 / 31
Регистрация: 24.10.2016
Сообщений: 186
29.10.2016, 01:05 4
Не понял вопроса. Очевидно же что будет size проходов.
0
madendinara
0 / 0 / 0
Регистрация: 11.09.2016
Сообщений: 5
29.10.2016, 01:06  [ТС] 5
Постановка Задачи
Вы должны реализовать алгоритм, описанный выше, и распечатать индекс максимального значения при каждом проходе.

Входные данные будут содержать N Размер массива в первой строке.
Следующая строка будет содержать сам массив (все элементы будут разными).
Ответ должен содержать показатели максимумами при каждом проходе (N-1 значения).
0
OlafNestandart
54 / 54 / 31
Регистрация: 24.10.2016
Сообщений: 186
29.10.2016, 01:14 6
Лучший ответ Сообщение было отмечено madendinara как решение

Решение

Просто вывод в cout в selection_sort пойдет?
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
#include <cstddef>
#include <algorithm>
#include <iostream>
 
template <typename T>
void selection_sort(T* arr, size_t size) {
    if (size > 0) {
        T max = arr[0];
        size_t index = 0;
        for (size_t i = 0; i < size; i++) {
            if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        if (index != --size)
            std::swap(arr[index], arr[size]);
        std::cout << index << " ";
        selection_sort(arr, size);
    }
}
 
int main() {
    int arr[] = {5, 3, 9, 7, 1};
    selection_sort(arr, 5);
    std::cout << std::endl;
    for (int i = 0; i < 5; i++)
        std::cout << arr[i] << " ";
}
0
nofx
7 / 7 / 5
Регистрация: 28.10.2012
Сообщений: 134
Завершенные тесты: 4
29.10.2016, 02:13 7
Цитата Сообщение от madendinara Посмотреть сообщение
Вы должны реализовать алгоритм, описанный выше, и распечатать индекс максимального значения при каждом проходе
- мне показалось что нужно брать индекс максимального, потом индекс минимального...но дальше с их ответом не сходится....

Вот вам код, но он НЕ правильный, они там другую логику хотят...а какую я не догнал

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
44
45
46
47
48
49
50
51
52
/*
input data :
6
31 41 59 26 53 58
 
answer :
       2 2 2 1 0
*/
 
#include <iostream>
#include <array>
 
template<class T>
void sort_max_or_min(T* arr, const size_t n, bool is_max)
{
    if (n == 0) return;
 
    int max_min = arr[0];
    int ind = 0;
 
    for (auto i = 0; i < n - 1; i++)
    {
        if ((is_max && arr[i] > max_min) || (!is_max && arr[i] < max_min))
        {
            max_min = arr[i];
            ind = i;
        }
    }
 
    //ну собственно сам свап (он не нужен)
    if (is_max)
        std::swap(arr[ind], arr[n - 1]);
    else
        std::swap(arr[ind], arr[0]);
    
    //выводим индекс и уменьшаем размер
    std::cout << ind << " ";
    sort_max_or_min(arr, n-1, !is_max);
 
}
 
int main(int argc, int**argv)
{
    const int n = 6;
    int arr[] = { 31, 41, 59, 26, 53, 58 };
 
    sort_max_or_min<int>(arr, n, true );
 
    getchar();
    return 0;
 
}
Добавлено через 6 минут
(59 (индекс 2),потом 26 (индекс 2), потом 58 (индекс 4....) , причем индекс без учета индекса предыдущего числа.
Они там по другому хотят...
0
OlafNestandart
54 / 54 / 31
Регистрация: 24.10.2016
Сообщений: 186
29.10.2016, 07:12 8
Блин, ну я и тормоз. Не дочитал до конца задание и туплю - чего от меня хотят?
Так выводит то, что нужно. Или нужно еще и ввод распарсить?
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
#include <cstddef>
#include <algorithm>
#include <iostream>
 
template <typename T>
void selection_sort(T* arr, size_t size) {
    if (size > 0) {
        T max = arr[0];
        size_t index = 0;
        for (size_t i = 0; i < size; i++) {
            if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        if (index != --size)
            std::swap(arr[index], arr[size]);
        if (size > 0) {
            std::cout << index << " ";
            selection_sort(arr, size);
        } else {
            std::cout << std::endl;
        }
    }
}
 
int main() {
    int arr[] = {31, 41, 59, 26, 53, 58};
    selection_sort(arr, 6);
    for (int i = 0; i < 6; i++)
        std::cout << arr[i] << " ";
}
0
29.10.2016, 07:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.10.2016, 07:12

Модифицировать код сортировки так, чтобы на каждом следующем проходе количество сравнений декрементировалось
Помогите разобраться. Нужно модифицировать так, чтобы на втором проходе было 8 сравнений, на...

Задача на сортировку простым выбором
Вот такая задача Дана целочисленная матрица размером MхN. Пусть для каж-дой строки матрицы...

Запрограммируйте сортировку выбором в виде процедуры
8.Запрограммируйте сортировку выбором в виде процедуры. Поиск наименьшего числа сделайте ее...


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

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

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