Данный отчёт сгенерирован 10.02.2023 18:21:31 UTC.
HTML версия (этот сайт) сгенерирован 10.02.2023 18:21:38 UTC.
Коммит: [bfeb65b9] add automatic zip creation 10.02.2023 18:21:31
HTML версия (этот сайт) сгенерирован 10.02.2023 18:21:38 UTC.
Коммит: [bfeb65b9] add automatic zip creation 10.02.2023 18:21:31
Задача: Часткове сортування
10.02.2023 18:21:31
Описание: Запрограмувати алгоритм часткового сортування у вигляді функції partSort(arr),
яка частково впорядковує переданий їй масив та повертає новий індекс базового елемента.
Базовим вважати початковий елемент масиву-аргументу, менші значення ставити спочатку.
Часова складність алгоритму має бути O(n).
Не використовувати метод sort.
10.02.2023 18:21:31
Решений: 20
10.02.2023 18:21:31
Часткове сортування
10.02.2023 18:21:31
function partSort(arr)
{
function change(i, j)
{
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
let begin = 0
let end = arr.length
let s = begin
end--
while(true)
{
while (arr[begin] <= arr[s]) begin++
while (arr[end] > arr[s]) end--
if (begin < end)
{
change(begin, end)
}
else
{
break
}
}
change(end, s)
return end
}
function partSort(a) {
let p = l = 0, r = a.length;
r--;
while(true) {
while(a[l] <= a[p]) l += 1;
while(a[r] > a[p]) r -= 1;
if(l < r)
[a[l], a[r]] = [a[r], a[l]];
else
break;
}
[a[r], a[p]] = [a[p], a[r]];
return r;
}
function partSort(arr, k=0){
let a = arr[k]
for(i=1;i< arr.length;i++){
if(arr[i]< a){
let k = arr[i]
arr.splice(i,1)
arr.unshift(k)
}
}
return arr.indexOf(a)
}
function partSort (arr) {
let k = 0;
let arr1 = arr[k];
for(i = 1; i < arr.length; i++) {
if(arr[i] < arr1) {
let k = arr[i];
arr.splice (i, 1);
arr.unshift (k);
}
}
return arr.indexOf (arr1);
}
function partSort(arr, k=0){
let a = arr[k]
for(i=1;i< arr.length;i++){
if(arr[i]< a){
let k = arr[i]
arr.splice(i,1)
arr.unshift(k)
}
}
return arr.indexOf(a)
}
function partSort(arr, a = 0, b = arr.length - 1) {
function change(i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let p = a;
while (1) {
while (arr[a] <= arr[p])
a++;
while (arr[b] > arr[p])
b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}
function partSort(arr, j=0){
let a = arr[j]
for(i=1;i< arr.length;i++){
if(arr[i]< a){
let j = arr[i]
arr.splice(i,1)
arr.unshift(j)
}
}
return arr.indexOf(a)
}
function partSort(arr) {
let a = 0;
let b = arr.length - 1;
let p = 0;
if(arr.length == 2 && arr[0] < arr[1]) b--
while (arr.length > 2) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b) [arr[a], arr[b]] = [arr[b], arr[a]];
else break;
}
[arr[b], arr[p]] = [arr[p], arr[b]];
return b;
}
function partSort(a){
let t = a[0];
for(let length=a.length-1; length>=0; length--){
let max = length;
for(let i=0; i if(a[max]< a[i]){
let tmp = a[max];
a[max] = a[i];
a[i] = tmp;
}
}
}
return a.indexOf(t);
}
function partSort(arr){
function change(i, j) {
let buffer = arr[i];
arr[i] = arr[j];
arr[j] = buffer;
}
let p = 0;
let a = 0;
let b = arr.length - 1;
while(1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}
function partSort(arr) {
let a = arr[0];
let indx = 0;
let i = 1;
while (i < arr.length) {
if (a >= arr[i]) {
arr.unshift(arr[i]);
arr.splice(i + 1, 1);
indx++;
}
i++;
}
return indx;
}
function partSort(arr, a = 0, b = arr.length - 1) {
function change(i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let p = a;
while (1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b) change(a, b);
else break;
}
change(b, p);
return b;
}
function partSort(arr){
let left = 0
let right = arr.length - 1
while (left < right){
while (arr[left] <= arr[0]) ++left
while (arr[right] > arr[0]) --right
if (left < right) [arr[left], arr[right]] = [arr[right], arr[left]]
}
[arr[right], arr[0]] = [arr[0], arr[right]]
return right
}
function partSort(arr, a = 0, b = arr.length - 1) {
function change(i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let p = a;
while (1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b) change(a, b);
else break;
}
change(b, p);
return b;
}
function partSort(a) {
const swap = (i, j) => {
let t = a[i];
a[i] = a[j];
a[j] = t;
};
let l = 0, r = a.length;
let p = l;
r -= 1;
while(true) {
while(a[l] <= a[p]) l += 1;
while(a[r] > a[p]) r -= 1;
if(l < r)
swap(l, r);
else
break;
}
swap(r, p);
return r;
}
function partSort(arr){
let basis = arr[0]
let temp = 0
for(let i = 0;i< arr.length;i++){
for(let j = i;j< arr.length;j++){
if(arr[i]-arr[j]>0){
console.log(arr)
console.log(arr[i],arr[j],arr[i]-arr[j])
temp = arr[j]
arr.splice(j,1,arr[i])
arr.splice(i,1,temp)
temp = 0
}
}
}
return arr.indexOf(basis)
}
function partSort(arr, a=0, b=arr.length)
{
function change(i, j) {
let t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
let p = a;
b--;
while(1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}
function partSort(a){
function change(b, c){
let temp = a[b];
a[b] = a[c];
a[c] = temp;
}
let beg = 1;
let end = a.length-1;
while(1){
while (a[beg] while (a[end]>a[0]) end--;
if (beg else break;
}
change (0, end);
return (end);
}
function partSort(arr)
{
let b = arr.length;
let a = 0;
function change(i, j) {
let t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
let p = 0;
b--;
while(1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}
function partSort(arr,a = 0,b = arr.length)
{
// внутрішня функція
function change(i, j) {
let t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
// позиція опорного елемента
let p = a;
b--;
while(1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}
{
function change(i, j)
{
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
let begin = 0
let end = arr.length
let s = begin
end--
while(true)
{
while (arr[begin] <= arr[s]) begin++
while (arr[end] > arr[s]) end--
if (begin < end)
{
change(begin, end)
}
else
{
break
}
}
change(end, s)
return end
}
let p = l = 0, r = a.length;
r--;
while(true) {
while(a[l] <= a[p]) l += 1;
while(a[r] > a[p]) r -= 1;
if(l < r)
[a[l], a[r]] = [a[r], a[l]];
else
break;
}
[a[r], a[p]] = [a[p], a[r]];
return r;
}
let a = arr[k]
for(i=1;i< arr.length;i++){
if(arr[i]< a){
let k = arr[i]
arr.splice(i,1)
arr.unshift(k)
}
}
return arr.indexOf(a)
}
let k = 0;
let arr1 = arr[k];
for(i = 1; i < arr.length; i++) {
if(arr[i] < arr1) {
let k = arr[i];
arr.splice (i, 1);
arr.unshift (k);
}
}
return arr.indexOf (arr1);
}
let a = arr[k]
for(i=1;i< arr.length;i++){
if(arr[i]< a){
let k = arr[i]
arr.splice(i,1)
arr.unshift(k)
}
}
return arr.indexOf(a)
}
function change(i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let p = a;
while (1) {
while (arr[a] <= arr[p])
a++;
while (arr[b] > arr[p])
b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}
let a = arr[j]
for(i=1;i< arr.length;i++){
if(arr[i]< a){
let j = arr[i]
arr.splice(i,1)
arr.unshift(j)
}
}
return arr.indexOf(a)
}
let a = 0;
let b = arr.length - 1;
let p = 0;
if(arr.length == 2 && arr[0] < arr[1]) b--
while (arr.length > 2) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b) [arr[a], arr[b]] = [arr[b], arr[a]];
else break;
}
[arr[b], arr[p]] = [arr[p], arr[b]];
return b;
}
let t = a[0];
for(let length=a.length-1; length>=0; length--){
let max = length;
for(let i=0; i
let tmp = a[max];
a[max] = a[i];
a[i] = tmp;
}
}
}
return a.indexOf(t);
}
function change(i, j) {
let buffer = arr[i];
arr[i] = arr[j];
arr[j] = buffer;
}
let p = 0;
let a = 0;
let b = arr.length - 1;
while(1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}
let a = arr[0];
let indx = 0;
let i = 1;
while (i < arr.length) {
if (a >= arr[i]) {
arr.unshift(arr[i]);
arr.splice(i + 1, 1);
indx++;
}
i++;
}
return indx;
}
function change(i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let p = a;
while (1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b) change(a, b);
else break;
}
change(b, p);
return b;
}
let left = 0
let right = arr.length - 1
while (left < right){
while (arr[left] <= arr[0]) ++left
while (arr[right] > arr[0]) --right
if (left < right) [arr[left], arr[right]] = [arr[right], arr[left]]
}
[arr[right], arr[0]] = [arr[0], arr[right]]
return right
}
function change(i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let p = a;
while (1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b) change(a, b);
else break;
}
change(b, p);
return b;
}
const swap = (i, j) => {
let t = a[i];
a[i] = a[j];
a[j] = t;
};
let l = 0, r = a.length;
let p = l;
r -= 1;
while(true) {
while(a[l] <= a[p]) l += 1;
while(a[r] > a[p]) r -= 1;
if(l < r)
swap(l, r);
else
break;
}
swap(r, p);
return r;
}
let basis = arr[0]
let temp = 0
for(let i = 0;i< arr.length;i++){
for(let j = i;j< arr.length;j++){
if(arr[i]-arr[j]>0){
console.log(arr)
console.log(arr[i],arr[j],arr[i]-arr[j])
temp = arr[j]
arr.splice(j,1,arr[i])
arr.splice(i,1,temp)
temp = 0
}
}
}
return arr.indexOf(basis)
}
{
function change(i, j) {
let t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
let p = a;
b--;
while(1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}
function change(b, c){
let temp = a[b];
a[b] = a[c];
a[c] = temp;
}
let beg = 1;
let end = a.length-1;
while(1){
while (a[beg]
if (beg
}
change (0, end);
return (end);
}
{
let b = arr.length;
let a = 0;
function change(i, j) {
let t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
let p = 0;
b--;
while(1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}
{
// внутрішня функція
function change(i, j) {
let t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
// позиція опорного елемента
let p = a;
b--;
while(1) {
while (arr[a] <= arr[p]) a++;
while (arr[b] > arr[p]) b--;
if (a < b)
change(a, b);
else
break;
}
change(b, p);
return b;
}