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


#1
Мое решение

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;
}
}
}


#2

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

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

Типа такого:

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);

#3

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


#4

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

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


#5

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

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


#6

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


#7

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

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;
    }
  }
}

#8

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


#9

Это - решение, скопированное посимвольно из упражнения №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;
}


#10

И откуда у вас такая уверенность что оно скопировано? Там задача не широкая,чтобы 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;
});

#11

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

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

#13

Уважаемый.
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;
		}
	}
}

#14

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


#15

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


#16

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


#17

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