Dia 58/2019 - Algoritmos em JS: Classificação

Desafio #92daysofcode que fiz no final de 2019. Nesse artigo temos o dia 58, mostrando o uso de classificação.

Código

1
2
3
const swap = (array, a, b) => {
[array[a], array[b]] = [array[b], array[a]];
}
1
2
3
4
5
6
7
8
9
10
11
12
const bubbleSort = array => {
const { length } = array;

for (let i = 0; i < length; i++) {
for (let j = 0; j < length - 1; j++) {
if (array[j] > array[j + 1]) {
[array[j], array[j+1]] = [array[j], array[j+1]]; //swap
}
}
}
return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const insertionSort = array => {
const { length } = array;
let temp;

for (let i = 1; i < length; i++) {
let j = i;
temp = array[i];
while (j > 0 && array[j - 1] > temp) {
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}

return array;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const heapify = (array, index, heapSize) => {
let largest = index;
const left = (2 * index) + 1;
const right = (2 * index) + 2;
if (left < heapSize && array[left] > array[index]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (largest !== index) {
swap(array, index, largest);
heapify(array, largest, heapSize);
}
}

const buildMaxHeap = array => {
for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
heapify(array, i, array.length);
}
return array;
}

const heapSort = array => {
let heapSize = array.length;
buildMaxHeap(array);
while (heapSize > 1) {
swap(array, 0, --heapSize);
heapify(array, 0, heapSize);
}
return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const merge = (left, right) => {
let i = 0;
let j = 0;
const result = [];

while (i < left.length && j < right.length) {
result.push(left[i] < right[j] ? left[i++] : right[j++]);
}

return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

const mergeSort = array => {
if (array.length > 1) {
const { length } = array;
const middle = Math.floor(length / 2);
const left = mergeSort(array.slice(0, middle));
const right = mergeSort(array.slice(middle, length));
array = merge(left, right);
}

return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const partition = (array, left, right) => {
const pivot = array[Math.floor((right + left) / 2)];
let i = left;
let j = right;

while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swap(array, i, j);
i++;
j--;
}
}
return i;
}

const quick = (array, left, right) => {
let index;
if (array.length > 1) {
index = partition(array, left, right);
if (left < index - 1) {
quick(array, left, index - 1);
}
if (index < right) {
quick(array, index, right);
}
}
return array;
}

const quickSort = array => {
return quick(array, 0, array.length - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const selectionSort = (array, compare) => {
const { length } = array;
const fn = compare ? compare : (a, b) => a - b;
let indexMin;

for (let i = 0; i < length - 1; i++) {
indexMin = i;

for (let j = i; j < length; j++) {
if (fn(array[indexMin], array[j]) > 0) {
indexMin = j;
}
}

if (i !== indexMin) {
swap(array, i, indexMin);
}
}

return array;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const shellSort = array => {
let increment = array.length / 2;

while (increment > 0) {
for (let i = increment; i < array.length; i++) {
let j = i;
const temp = array[i];
while (j >= increment && array[j - increment] > temp) {
array[j] = array[j - increment];
j -= increment;
}
array[j] = temp;
}
if (increment === 2) {
increment = 1;
} else {
increment = Math.floor((increment * 5) / 11);
}
}

return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// https://en.wikipedia.org/wiki/Sorting_algorithm
// https://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o

// https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/sorting.html
// https://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-comparacao/28261

/*
* Bubble Sort
***********************************/
console.log(bubbleSort([7,5,2,4,3,9]));
// [2, 3, 4, 5, 7, 9]
console.log(bubbleSort([9,7,5,4,3,1]));
// [1, 3, 4, 5, 7, 9]
console.log(bubbleSort([1,2,3,4,5,6]));
// [1, 2, 3, 4, 5, 6]
console.log('------------------------------------------------');

/*
* Insertion Sort
***********************************/
console.log(insertionSort([9, 2, 5, 6, 4, 3, 7, 10, 1, 8]));
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
console.log('------------------------------------------------');

/*
* Heap Sort
***********************************/
console.log(heapSort([3, 0, 2, 5, -1, 4, 1]));
// [-1 , 0, 1, 2, 3, 4, 5]
console.log('------------------------------------------------');

/*
* Merge Sort
***********************************/
console.log(mergeSort([10, 4, 2, 5, 2, 1, 9, 0]));
// [0, 1, 2, 2, 4, 5, 9, 10]
console.log('------------------------------------------------');

/*
* Quick Sort
***********************************/
console.log(quickSort([11,8,14,3,6,2,7],0,6));
// [2, 3, 6, 7, 8, 11, 14]
console.log(quickSort([11,8,14,3,6,2,1, 7],0,7));
// [1, 2, 3, 6, 7, 8, 11, 14]
console.log(quickSort([16,11,9,7,6,5,3, 2],0,7));
// [2, 3, 5, 6, 7, 9, 11, 16]
console.log('------------------------------------------------');

/*
* Selection Sort
***********************************/
console.log(selectionSort([3, 0, 2, 5, -1, 4, 1], (a, b) => a - b));
// [-1,0,1,2,3,4,5]
console.log(selectionSort([3, 0, 2, 5, -1, 4, 1], (a, b) => b - a));
// [5,4,3,2,1,0,-1]
console.log('------------------------------------------------');

/*
* Shell Sort
***********************************/
console.log(shellSort([3, 0, 2, 5, -1, 4, 1]));
// [-1,0,1,2,3,4,5]
console.log('------------------------------------------------');

Conclusão

A postagem original pode ser vista no meu Instagram e o código está acessível no meu Github.

Relacionados

Ao fechar este aviso ou continuar navegando no site Nerd Calistênico, você aceita o uso de cookies.

Este site usa cookies para assegurar a melhor experiência para os nossos usuários. Consulte nossa política de privacidade.

Uma nova versão está disponível. Clique aqui para atualizar.