Нужна помощь в понимании алгоритма выбора сортировки - PullRequest
0 голосов
/ 24 апреля 2018

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

Ниже приведены инструкции и мой ответ:

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

Original Array: 30 8 2 25 27 20 
PASS 1: 8 30 2 25 27 20 
PASS 2: 8 2 30 25 27 20 
PASS 3: 8 2 25 30 27 20 
PASS 4: 8 2 25 27 30 20 
PASS 5: 8 2 25 27 20 30

Может кто-нибудь сказать мне, правильно ли я это сделал?

Ответы [ 4 ]

0 голосов
/ 24 апреля 2018

Я рад, что вы попробовали это

Алгоритм:

repeat (numOfElements - 1) times

  set the first unsorted element as the minimum

  for each of the unsorted elements

    if element < currentMinimum

      set element as new minimum

  swap minimum with first unsorted position

Вывод будет:

Pass 1 : 2 8 30 25 27 20
Pass 2 : 2 8 30 25 27 20
Pass 3 : 2 8 20 25 27 30
Pass 4 : 2 8 20 25 27 30
Pass 5 : 2 8 20 25 27 30

Вы можете дать пользовательский ввод, и он покажетвы шаг за шагом выводите: https://visualgo.net/bn/sorting

Надеюсь, это поможет: D

Удачи в вашем обучении!

0 голосов
/ 24 апреля 2018

В псевдокоде:

Repeat until no unsorted elements remain:
    Search the unsorted part of the data to find the smallest value
    Swap the smallest found value with the first element of the unsorted part

В соответствии с этим ваш список данных будет ...

Original Array: 30 8 2 25 27 20

P1: [2] 8 30 25 27 20 // smallest(2), swap this with the first value(30)

P2: [2 8] 30 25 27 20 // smallest(8), don't need to swap 

P3: [2 8 20] 25 27 30 // smallest(20), swap this with the first ele of unsorted list(30)

P4: [2 8 20 25] 27 30 // smallest(25), don't need to swap

P5: [2 8 20 25 27] 30 // smallest(27), don't need to swap

P6: [2 8 20 25 27 30] // smallest(30), don't need to swap... sorted!

PASS 6 не требуется, так как последний элемент уже отсортирован.

Проверьте это видео из CS50 (хорошо объяснено Университетом Хаварда.): https://www.youtube.com/watch?v=3hH8kTHFw2A

0 голосов
/ 24 апреля 2018

Если вы посмотрите на свои результаты, должно быть очевидно, что вы не сделали это правильно.Восемь не меньше двух!:)


Возьмите первый предмет: 30. Найдите мин: 2. Поменяйте местами.

PASS 1: 2 | 8 30 25 27 20 

Первая часть списка теперь отсортирована (обозначается через канал).

Возьмите следующий предмет: 8. Найдите мин - 8 на самом деле мин.Обмен не происходит.

PASS 2: 2 8 | 30 25 27 20 

Возьмите следующий предмет: 30. Найдите мин: 20. Поменяйте местами.

PASS 3: 2 8 20 | 25 27 30 

Возьмите следующий предмет: 25. Это мин.Обмен не происходит.

PASS 4: 2 8 20 25 | 27 30 

Возьмите следующий предмет: 27. Это мин.Обмен не происходит.

PASS 5: 2 8 20 25 27 | 30 

Возьмите следующий предмет: 30. Это мин.Обмен не происходит.

Список теперь отсортирован.

0 голосов
/ 24 апреля 2018

Я заметил, что 2 - самый маленький элемент в вашем массиве. Таким образом, на первом проходе он должен быть в начале массива. Пожалуйста, ознакомьтесь с приведенными ниже примерами.

ПРИМЕР 1: обр [] = 64 25 12 22 11

// Найти минимальный элемент в arr [0 ... 4] // и поместите его в начале 11 25 12 22 64

// Найти минимальный элемент в arr [1 ... 4] // и помещаем его в начало arr [1 ... 4] 11 12 25 22 64

// Найти минимальный элемент в arr [2 ... 4] // и помещаем его в начало arr [2 ... 4] 11 12 22 25 64

// Найти минимальный элемент в arr [3 ... 4] // и помещаем его в начало arr [3 ... 4] 11 12 22 25 64

ССЫЛКА 1: https://www.hackerearth.com/practice/algorithms/sorting/selection-sort/tutorial/

ССЫЛКА 2: https://www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...