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

Goodzilla365 · 16.Июль.2018 11:30:23

Мое решение

for (var i = 0; i < numbers.length; i++ ) {
for (var j = i; j < numbers.length; j++ ) {
if (numbers[i] > numbers[j]) {
var temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
}

Deepspiral · 16.Июль.2018 11:42:30

Так это вроде как сортировка пузырьком. Недостаток проверки в том, что любая сортировка засчитывается, независимо от ее эффективности.

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

Типа такого:

var swapItems = function (firstIndex, secondIndex) {
  var swap = numbers[firstIndex];
  numbers[firstIndex] = numbers[secondIndex];
  numbers[secondIndex] = swap;
}

for (var j = 0; j < numbers.length - 1; j ++) {
  var minValue = numbers[j];
  var minValueIndex = j;

  for (var i = j + 1; i < numbers.length; i ++) { 
    if (numbers[i] < minValue) {
     minValue = numbers[i];
     minValueIndex = i; 
    } 
  }

  if (j != minValueIndex) {
    swapItems(j, minValueIndex);
  } 
}

console.log(numbers);

Goodzilla365 · 16.Июль.2018 11:58:57

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

Deepspiral · 16.Июль.2018 12:05:03

Нет, у вас в решении другой алгоритм, он называется “сортировка пузырьком”. А нужно сортировку выбором. Отличие в том, что не нужно первое же найденное значение, которое меньше базового, менять с базовым местами. Сначала нужно убедиться, что найденное значение действительно меньше всех.

Мне так кажется после прочтения википедии

istomindev · 18.Июль.2018 06:15:18

var numbers = [3, 5, 15, 6, 2, 1];

numbers.sort(function(a, b){return a - b});

Deepspiral · 18.Июль.2018 11:10:06

Формально задачу вы решили неверно - это сортировка методом быстрой сортировки.

gagharut · 25.Июль.2018 16:54:26

Про это что скажете? Тоже по алгоритму сделал…

var usersByDay = [4, 2, 1, 3];
  for (var i = 0; i <= usersByDay.length - 2; i++) {
  var minValue = usersByDay[i];

  for (var j = i + 1; j <= usersByDay.length - 1; j++) {
    if (usersByDay[j] < minValue) {
      minValue = usersByDay[j];
      var swap = usersByDay[i];
      usersByDay[i] = minValue;
      usersByDay[j] = swap;
    }
  }
}

Deepspiral · 25.Июль.2018 17:26:39

Это же сортировка пузырьком.

Gemini · 02.Сентябрь.2018 11:06:00

Это - решение, скопированное посимвольно из упражнения №24 следующего курса, посвященного массивам. Да, там авторы не написали про “метод пузырька”, просто как-то нечаянно перескочили в предыдущих уроках с “прямого выбора” на “пузырек”. И да, не пройдя этот курс, крайне сложно делать практику для предыдущего курса (вложенные циклы, своп, операции с массивами и их длиной), но стоило ли…
И всякий случай, у меня вот такое решение получилось:
for (var i=0; i<numbers.length-1; i++)
{
var min = i;
for (var j=i+1; j<numbers.length; j++)
{
if (numbers[j]<numbers[min])
{min=j;
}
}
var swap=numbers[i];
numbers[i]=numbers[min];
numbers[min]=swap;
}

gagharut · 02.Сентябрь.2018 17:11:11

И откуда у вас такая уверенность что оно скопировано? Там задача не широкая,чтобы 150 видов кода было. Полтора месяца назад я только начинал понимать js и решил таким образом. А пишу я код на visual studio и всегда привожу в нормальный вид перед реализацией.
Ps.
Пользуюсь сейчас методом .sort

var numbers = [1, 2, 3, 4, 5, 6, 158, 200, 97, 33, 68];

numbers.sort(function (number1, number2) {
	return number1 - number2;
});

Gemini · 03.Сентябрь.2018 03:55:53

Хм… Вы уверены, что стоит дополнительно привлекать внимание к этому? Ну ок, вот аргументы:

Посимвольное совпадение - это конечно вероятно (нот-то всего 7), но…
Вплоть до названий переменных из другого задания (usersByDay),
С заменой исходного массива в стартовой задаче, на массив из другой задачи…
…даже без мелкого изменения, чтобы доделать образец до требуемого решения.
А достаточно было 3 строки свопа вынести в другую часть цикла, и все, ноль вопросов

gagharut · 03.Сентябрь.2018 07:18:17

Уважаемый.
1.По материалу,надо учится и глупо было бы мною копировать чужой код.
2.Мой вопрос был к Deepspiral,чтобы понять материал,который мы изучаем стоит ли вообще учить,т.к. там писали что метод очень плохой и я засомневался стоит ли учить такой материал,который приводит к плохому коду.
3.В тот момент я особо не понимал сути решаемой задачи. Я знал алгоритм,который был задан в задаче,но не сумел бы его использовать в другой задаче,сейчас уже мое понимание стало шире и лучше.
4.Вопрос к вам. Вы пришли тут учится к новому или разводить кашу?
5.Еще раз,в уроке учат только делать по одному-двум алгоритмам,как еще делать по другому? И да я взял из других задач имена переменных,т.к. имя подошло к задаче. И если вы проходили курс по “Продвинуты javascript уровень 1”,то знайте,что надо давать переменным правильные имена.
6. Дальше я не буду вам ничего писать,т.к. я пришел сюда учится,а не копировать чужой код.

Ps. И чем же отличается ваш код

for (var i = 0; i < numbers.length - 1; i++) {
	var min = i;
	for (var j = i + 1; j < numbers.length; j++) {
		if (numbers[j] < numbers[min]) {
			min = j;
		}
	}
	var swap = numbers[i];
	numbers[i] = numbers[min];
	numbers[min] = swap;
}

От моей

for (var i = 0; i <= usersByDay.length - 2; i++) {
	var minValue = usersByDay[i];

	for (var j = i + 1; j <= usersByDay.length - 1; j++) {
		if (usersByDay[j] < minValue) {
			minValue = usersByDay[j];
			var swap = usersByDay[i];
			usersByDay[i] = minValue;
			usersByDay[j] = swap;
		}
	}
}

Что ваши 3 строки вне цикла for?

var swap = numbers[i];
numbers[i] = numbers[min];
numbers[min] = swap;

Ну смешно же…

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

Pss. И чем же отличается наш код от кода ТС???

for (var i = 0; i < numbers.length; i++) {
	for (var j = i; j < numbers.length; j++) {
		if (numbers[i] > numbers[j]) {
			var temp = numbers[i];
			numbers[i] = numbers[j];
			numbers[j] = temp;
		}
	}
}

Gemini · 03.Сентябрь.2018 07:37:17

А, то есть вы не видите разницы? Тогда действительно дальше и не о чем говорить, и незачем

gagharut · 03.Сентябрь.2018 07:38:28

Чем ваш код отличается от Сортировка выбором ?
Аяяй,вот откуда скопировали…
Смешно просто.
Если я не вижу разницу,лучше будьте компетентным и объясните,а не флудите. И разговор не о том,что я не понимаю,а о том,что вы пишете,что я скопировал код. Тогда и вы скопировали из соседнего топика.
Пол форума тогда тырят друг у друга код задачи…
Удачи!

Gemini · 03.Сентябрь.2018 07:45:53

И вам удачи! Но на всякий случай рекомендую хотя бы попытаться разобраться, что меняется в процессе работы цикла, в зависимости от положения строк со свопом

gagharut · 03.Сентябрь.2018 07:52:06

Вот. Уже другой разговор. А то пишете скопировал скопировал,не приятно же… Я не стал изучать,т.к. пишут что метод не очень медленный для работы с средними или большим кол-вом данных. В массивах же не только циферки,там еще объекты,другие массивы,строки,объекты с массивами и т.д. Таким подходом просто геморойно делать поиск/сортировку…

soze · 20.Март.2019 12:05:39

не могу продвинуться дальше при сортировке выборкой. возникает проблема если есть одинаковые числа в массиве.
var numbers = [ 34,115,22,34,12,1,34];

for (var j = 0; j < numbers.length; j++) {
var min = numbers[numbers.length - 1];
var indexMin;
for (var i = j; i < numbers.length; i++) {
if (min > numbers[ i ]) {
min = numbers[ i ];
console.log( 'min: ’ + min);
var indexMin = numbers.indexOf( min );
console.log('minIndex: ’ + indexMin);
} else if (min === numbers[ i ]) {
var indexMin = numbers.indexOf(min);
}
}

var swap = numbers[ j ];
numbers[ j ] = numbers[indexMin];
numbers[ indexMin ] = swap;
console.log(numbers);
}

haosmos · 28.Апрель.2019 21:22:53

Товарищи, помогите, пожалуйста, разобраться.

Тут приводили решение:

var numbers = [3, 5, 15, 6, 2, 1];
var sort = [];

for (var i = 0; i < numbers.length; i++) {
  for (j = i; j < numbers.length; j++) {
    if (numbers[j] < numbers[i]) {
      var tmp = numbers[i];
      numbers[i] = numbers[j];
      numbers[j] = tmp;
    }
  }
}

Объясните, пожалуйста, как это работает? А именно, зачем нужен второй цикл внутри первого? С виду оба цикла проходятся по одному и тому же массиву и выполняют одни и те же действия. Однако код работает — сортировка происходит от меньшего к большему, — но почему работает этот код и зачем нужен второй цикл я не могу понять. Надеюсь, что кто-нибудь поможет разобраться.

zateya · 29.Апрель.2019 06:16:16

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

var numbers = [3, 5, 15, 6, 2, 1];
var sort = [];

for (var i = 0; i < numbers.length; i++) {
  for (j = i; j < numbers.length; j++) {
    if (numbers[j] < numbers[i]) {
      var tmp = numbers[i];
      numbers[i] = numbers[j];
      numbers[j] = tmp;
    }
  }
}

Смотрите что у нас происходит.
3, 5, 15, 6, 2, 1

Сначала мы попадаем во внешний цикл, где i присваивается 0.
i = 0;
если вызовем тут console.log(numbers[i]) то получим тройку, первый элемент массива.

Дальше мы попадаем во внутренний цикл, где j у нас присваивается i.
Т.е. j = 0. numbers[j] опять даст 3 - первый элемент массива.
3 не меньше 3 (хм… и зачем мы сравниваем элемент сам с собой, возможно, нам стоило сразу начать со следующего?),
а значит условие не выполнится и мы пойдем на следующий круг цикла.

Т.е. j = 1 numbers[j] даст 5, второй элемент массива.
i у нас по прежнему 0 (помним внешний цикл), а numbers[i] - первый элемент массива.
5 не меньше 3, значит следующее условие не выполняется и мы опять наращиваем счетчик j.

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

Наш массив:
3, 5, 15, 6, 2, 1

т.е. сначала 2 поменяется с 3
2 5 15 6 3 1

а потом 1 поменяется с 2
1 5 15 6 3 2

Ок, дошли до конца внутреннего цикла, опять вернулись во внешний.
i = 1, numbers[i] - второй элемент массива, т.е 5.

Зашли во внутренний цикл
j = 1, numbers[j] - опять второй элемент массива, т.е 5.
мы опять 5 сравниваем с 5 (хотя казалось бы зачем)
5 не меньше 5, переходим на следующий виток цикла
j = 2, numbers[j] = 15
15 не меньше 5, значит опять наращиваем j.

Что мы делали - мы сравнивали попарно второй элемент массива. Мы каждый раз сдвигаем область сравнения на 1 элемент (т.е. берем хвостик). После каждого прохода внешнего цикла мы получаем один правильно отсортированный элемент.

сейчас у нас так:
1 5 15 6 3 2

сначала 3 поменяется с 5
1 3 15 6 5 2

а потом 2 поменяется с 3
1 2 15 6 5 3

Закончили внутренний цикл - опять идем во внешний.
i = 2, третий эл-т массива
Сравниваем попарно начиная с 3-го и переставляем.
и т.д.

Все очень логично:
Находим минимум - ставим в начало (переставляем старые значения на освободившееся место, чтобы не пропали)
Из оставшихся (сдвинули на один) опять попарно находим минимум - ставим в начало. (нам же надо выстроить последовательно)
Из оставшихся (сдвинули на один) опять попарно находим минимум - ставим в начало.
…

Hierumo · 29.Апрель.2019 07:07:39

Добавил визуализации в код.
Смысл в том, что все элементы перебираются в цикле. И на каждой итерации такого “внешнего” цикла, происходит запуск “внутреннего” цикла, в котором происходит перестановка циферей. Суть условия в том, что если текущее число из позиции номера итерации “внешнего” цикла больше какого то числа из списка “внутреннего” цикла, то они меняются местами через буферную переменную tmp.

var numbers = [3, 5, 15, 6, 2, 1];
for (var i = 0; i < numbers.length; i++) {
console.log('Массив выглядит так перед каждой внешней итерацией ' + numbers);  
for (j = i; j < numbers.length; j++) {
    if (numbers[j] < numbers[i]) {
      var tmp = numbers[i];
      numbers[i] = numbers[j];
      numbers[j] = tmp;
    }
console.log('А вот так выглядит после каждой внутренней итерации ' + numbers);
  }
}
console.log('Конечный итог: ' + numbers);