Задание на сортировку javascript
Задание:
Программа сортирует полученную строку определённым образом. Строка состоит из слов и чисел, состоящих из 2-х цифр.
Пример, строка на входе:
four 52 along 96 25 gym root 15 hat 73 bank success 38 46
Сортировка будет выглядеть следующим образом:
1 шаг: along four 52 25 gym root 15 hat 73 bank success 38 46 96
2 шаг: bank along four 52 25 gym root 15 hat success 38 46 96 73
3 шаг: four bank along 25 gym root 15 hat success 38 46 96 73 52
4 шаг: gym four bank along 25 root 15 hat success 38 96 73 52 46
5 шаг: hat gym four bank along 25 root 15 success 96 73 52 46 38
6 шаг: root hat gym four bank along 15 success 96 73 52 46 38 25
7 шаг: success root hat gym four bank along 96 73 52 46 38 25 15
Проанализируй шаги сортировки, на основании имеющихся данных напиши алгоритм, который воспроизводит ту же самую логику сортировки. Описать алгоритм сортировки на языке программирования javascript.
Я сделал программу только для чисел, хотел потом переделать ее и для слов, но в конечном итоге получается полный бред
function sortArray(arr) {
let size = arr.length;
for (let i = 0; i < size; i++) {
let minIndex = findMinIndex(arr, i, size - i - 1);
if (minIndex !== i) {
// если минимальный элемент не на своем месте, перемещаем его
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
let maxIndex = findMaxIndex(arr, i, size - i - 1);
if (maxIndex !== size - i - 1) {
// если максимальный элемент не на своем месте, перемещаем его
[arr[size - i - 1], arr[maxIndex]] = [arr[maxIndex], arr[size - i - 1]];
}
console.log(arr);
}
return arr;
}
function findMinIndex(arr, start, end) {
let minIndex = start;
for (let i = start; i <= end; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
return minIndex;
}
function findMaxIndex(arr, start, end) {
let maxIndex = end;
for (let i = end; i >= start; i--) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
let inputArr = [52, 96, 25, 15, 73, 38, 46];
let sortedArr = sortArray(inputArr);
console.log(sortedArr);
Ответы (3 шт):
Сам алгоритм предполагает, что надо наибольшее число поставить вконец строки, а наименьшее слово в начало.
Под наибольшим и наименьшем я подразумеваю код первого символа.
Воспользуемся массивом для перестановки слов в строке
function letnum(c) {
const z = c.split(' ');
// 49 - 57 числа
// 97-122, 65 90, буквы. Возьмем только прописные под задачу
// Каждый обход будем находить по 1 слову и 1 числу.
// Слово с минимальным кодом, число с максимальным кодом
let charic = 300;
let charIdx = 0;
let numbers = 0;
let numIdx = 0;
let transform;
for (let j = 0; j < z.length / 2; j++) {
for (let i = j; i < z.length - j; i++) {
// слова
if (z[i].charCodeAt(0) > 96 && z[i].charCodeAt(0) < charic) {
charic = z[i].charCodeAt(0);
charIdx = i;
}
// числа
if (z[i].charCodeAt(0) < 58 && z[i].charCodeAt(0) > numbers) {
numbers = z[i].charCodeAt(0);
numIdx = i;
}
}
if (numIdx > charIdx) {
// вырезаем элемент
transform = z.splice(numIdx, 1)[0];
// Добавляем его в конец массива
z.push(transform);
// Вырезаем элемент
transform = z.splice(charIdx, 1)[0];
// Добавляем его в начало массива
z.unshift(transform);
} else {
transform = z.splice(charIdx, 1)[0];
z.unshift(transform);
// Т.к. индекс сметсился, нам надо тоже сделать сдвиг
transform = z.splice(numIdx + 1, 1)[0];
z.push(transform);
}
charic = 300;
numbers = 0;
console.log(j, z.join(' ')) // Промежуточные значения
}
// Собираем массив в строку и возвращаем результат
return z.join(' ');
}
console.log(letnum('four 52 along 96 25 gym root 15 hat 73 bank success 38 46'))Данный код будет работать для заданной строки или строки с аналогичными данными, где количество элементов(слов) будет четное, а количество слов и цифр одинаковое.
Самым универсальным решением, будет обычная сортировка массива, однако она не является решением под вашу задачу и не соблюдает заданный порядок
function sortString(c) {
// преобразуем строку в массив с разделителем "пробел"
return c.split(' ').sort((a,b) => b.charCodeAt(0) - a.charCodeAt(0)).join(' ');
}
console.log(sortString('four 52 along 96 25 gym root 15 hat 73 bank success 38 46'))Или же над описанием задачи не заморачивались, или же вы не изложили её полностью/искажённо. Так или иначне, но когда условие оставляет много вопросов типа "а что если ...", то это не очень гуд. Решение ниже вам может и не пригодится, но я попробовал сделать его более универсальным. Суть остаётся та же - при каждой итерации, находим первое в алфавитном порядке слово и максимально число отдельно из еще незатронутых, которые перемещаем в начало и в конец соответственно. Будет работать и со строкой, состоящей из одних слов или чисел. Соотношение слов и чисел влияет только на кол-во шагов (проходов по массиву).
const sorting = str => {
const arr = str.split(/\s+/);
const arrLen = arr.length;
let shiftS = 0;
let shiftE = arrLen;
for (let step = 0; step < arrLen; step++) {
let minNum = null;
let minWord = null;
for (const v of arr.slice(shiftS, shiftE)) {
let nan = isNaN(parseFloat(v));
if (nan && (minWord === null || minWord >= v)) {
minWord = v;
}
if (!nan && (minNum === null || +v >= +minNum)) {
minNum = v;
}
}
if (minWord === null && minNum === null) {
break;
}
if (minWord !== null) {
arr.unshift(...arr.splice(arr.indexOf(minWord, shiftS), 1));
shiftS++;
}
if (minNum !== null) {
arr.push(...arr.splice(arr.indexOf(minNum, shiftS), 1));
shiftE--;
}
console.log(`${step+1} шаг: ${arr.join(' ')}`);
}
console.log('Finish');
};
// строка из примера
sorting('four 52 along 96 25 gym root 15 hat 73 bank success 38 46');
// разное колво слов и чисел
sorting('four 52 along 96 25 gym root hat 73 bank success');
// только слова
sorting('four along gym root hat bank success');
// только числа. * добавил еще и однозначные числа
sorting('22 2 14 87 5 35 1');
// с одинаковыми значенияим
sorting('four 52 four 52 along 96 bank four');Еще один вариант, комментарии в коде.
function find(lst, l, r, what, cond) { // универсальная функция поиска минимального или максимального числа или строки в указанном диапазоне поиска
m = p = null
for (let i = l; i <= r; i++) {
x = lst[i]
c = cond === '>' ? (x > m) : (x < m)
if (typeof x === what && (c || (m === null))) { // если у значения нужный тип и условие сравнения выполняется
m = x // запоминаем значение
p = i // запоминаем индекс значения
}
}
return p // возвращаем индекс найденного значения
}
str = 'four 52 along 96 25 gym root 15 hat 73 bank success 38 46'
lst = str.split(' ').map((x) => parseInt(x) || x); // сразу переведем числа в числа - для их быстрого различения в функции find
cnt = l = 0
r = lst.length - 1
console.log(cnt + ' шаг: ' + str)
while ((r - l) > 0) { // повторяем, пока границы поисковой зоны в массиве не сойдутся
i = find(lst, l, r, 'string', '<') // ищем минимальную строку в диапазоне от l до r
lst.unshift(lst[i]) // найденное значение "вдвигаем" с левой стороны массива
lst.splice(i + 1, 1) // удаляем исходное вхождение
i = find(lst, l++, r--, 'number', '>') // ищем максимальное число в диапазоне от l до r, а потом сужаем границы поисковой зоны в массиве для следующего шага
lst.push(lst[i]) // найденное значение добавляем с правой стороны массива
lst.splice(i, 1) // удаляем исходное вхождение
console.log(++cnt + ' шаг: ' + lst.join(' ')) // выводим результат шага в консоль
}