259 / 76 / 16
Регистрация: 05.04.2018
Сообщений: 1,027
Записей в блоге: 1
1

Сортировка выбором

16.10.2018, 10:10. Показов 749. Ответов 5
Метки нет (Все метки)

Привет.
Готовлюсь к собеседованиям и решил подтянуть все сортировки. Помню весной решал такую задачу на сортировку выбором:
-Сортировка выбором. Сначала выполняется поиск минимального элемента в массиве, после чего сохраняется во временную переменную. Затем, этот элемент удаляется в массиве, а все последующие за ним элементы передвигаются на одну позицию влево. После этого сохраненный элемент заносится в последнюю позицию, которая освободилась после сдвига элементов влево.
вот код для этой задачи:
Кликните здесь для просмотра всего текста
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
53
54
55
56
57
58
#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;
 
void sort(int [], int);
 
int main ()
{
    srand(time(NULL));
    int size = 500;
    int *array = new int[size];
    
    cout << "Without sort:\n";
    for(int i = 0; i < size; ++i){
        array[i] = 1 + rand() % 1000;
        cout << setw(4) << array[i];
    }
    
    sort(array, size);
    
    cout << "\n\nAfter sort:\n";
    for(int i = 0; i < size; ++i){
        cout << setw(4) << array[i];
    }
    
    delete[]array;
 
    return 0;
}
 
void sort(int arr[], int size)
{
    int max, index, temp;
    
    for(int i = size - 1; i >= 1; --i)
    {
        max = arr[i];
        index = i;
        
        for(int j = i - 1; j >= 0; --j)
        {
            if(max < arr[j])
            {
                max = arr[j];
                index = j;
            }
        }
        
        temp = arr[index];
        
        for(int x = index; x < i; ++x){
            arr[x] = arr[x + 1];
        }
        
        arr[i] = temp;
    }
}

Я тогда решил, что это и есть сортировка выбором, но вот сейчас я читаю материал по сортировкам, и там совсем другой код приводится, с таким описанием:
-Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в надлежащем порядке.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void sort(int arr[], int size)
{
    int index = 0, temp = 0;
    
    for(int i = 0; i < size; ++i)
    {
        index = i;
        for(int j = i; j < size; ++j)
        {
            if(arr[index] > arr[j]) {
                index = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
}

какой код является правильным для этой сортировки?

Добавлено через 8 минут
и опять- таки, в описании: "Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент."
А в приведенном коде просто элемент первой итерации сравнивается со следующими и, если он больше, то они меняются местами. Дак какое описание этой сортировки верное и какой у нее код?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.10.2018, 10:10
Ответы с готовыми решениями:

сортировка выбором
не могу разобраться с задачей, не разбираюсь в указателях(((: сортировка выбором символов в строке....

Сортировка выбором
#include &quot;stdafx.h&quot; #include&quot;iostream&quot; #include&quot;time.h&quot; using namespace std; int main()...

Сортировка выбором
Сортировка выбором. Дана последовательность чисел а1, а2,..., аn. Требуется переставить элементы...

Сортировка выбором
Что не так с сортировкой простого выбора????((( #include &lt;iostream&gt; using namespace std; ...

5
1971 / 1096 / 467
Регистрация: 11.10.2018
Сообщений: 5,611
16.10.2018, 10:26 2
Цитата Сообщение от Джон Кофи Посмотреть сообщение
Я тогда решил, что это и есть сортировка выбором, но вот сейчас я читаю материал по сортировкам, и там совсем другой код приводится, с таким описанием:
-Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением.
- Вы же говорили, что находится элемент с наименьшим значением, да и в коде выше(1 код) ищется наименьший элемент - хотя имя у него "max".
0
259 / 76 / 16
Регистрация: 05.04.2018
Сообщений: 1,027
Записей в блоге: 1
16.10.2018, 10:54  [ТС] 3
Цитата Сообщение от FFPowerMan Посмотреть сообщение
Вы же говорили, что находится элемент с наименьшим значением
это я процитировал текст с материала, моего тут ничего нет. Я только разобраться хочу, какой код и описание мне использовать, когда мне зададут вопрос по этой сортировке.

Добавлено через 24 минуты
читаю наш форум и тут свой вариант какой же верный, или верны все?)
Алгоритмы сортировок
0
1971 / 1096 / 467
Регистрация: 11.10.2018
Сообщений: 5,611
16.10.2018, 10:55 4
Ну вот сортировка выбором на этом форуме:
Алгоритмы сортировок
Самая первая сортировка там.
Я так предполагаю, что на форуме верный.
1
259 / 76 / 16
Регистрация: 05.04.2018
Сообщений: 1,027
Записей в блоге: 1
16.10.2018, 11:11  [ТС] 5
FFPowerMan, там же читаю Думаю mik-a-el не будет в сортировках ошибаться)) приму эту ссылку за истину)
хотя все же интересно разобраться, правильно ли то, что существуют различные реализации одного алгоритма? ведь для каждого свое количество тиков.
на вики такой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
for (size_t idx_i = 0; idx_i < size - 1; idx_i++) {
         size_t min_idx = idx_i;
         for (size_t idx_j = idx_i + 1; idx_j < size; idx_j++) {
             if (array[idx_j] < array[min_idx]) {
                 min_idx = idx_j;
             }
         }
 
         if (min_idx != idx_i) {
             swap(array[idx_i], array[min_idx]);
             min_idx = idx_i;
         }
     }
0
1971 / 1096 / 467
Регистрация: 11.10.2018
Сообщений: 5,611
16.10.2018, 11:21 6
Ну да, на Википедии более оптимизированный вариант, чем здесь. Там оптимизация только в том, что нет сравнения и замены последнего элемента массива с самим собой, а так в точности все тоже самое.
C++
1
idx_i < size - 1;
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.10.2018, 11:21
Помогаю со студенческими работами здесь

Сортировка выбором
#include &lt;iostream&gt; #include &lt;math.h&gt; #include &lt;conio.h&gt; #include &lt;cstdlib&gt; using namespace...

Сортировка выбором
Помогите тут сделать сортировку выбором for (i = 0; i&lt;n; i++) { for (j = 0; j&lt;n; j++) {...

сортировка выбором
нужно сделать вместо сортировки пузырьком, сортировку выбором, помогите пожалуйста void...

Сортировка выбором
Обьясните вот эту строчку min = ( a &lt; a ) ? j : min; #include &lt;iostream&gt; using namespace std;...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru