ソートアルゴリズム-(1)
25845 ワード
泡整列-O(n 2)
const bubbleSort = (array) => {
const copyArray = array.slice();
const length = copyArray.length;
for (let i = 0; i < length; i++) {
for (let j = i; j < length; j++) {
if (copyArray[i] > copyArray[j]) {
let temp = copyArray[i];
copyArray[i] = copyArray[j];
copyArray[j] = temp;
}
}
}
return copyArray;
};
マージソート-O(nlogn)const mergeSort = (array) => {
if (array.length < 2) {
return array;
}
const midIndex = Math.floor(array.length / 2);
// 분할
const leftArray = mergeSort(array.slice(0, midIndex));
const rightArray = mergeSort(array.slice(midIndex, array.length));
// 병합
let result = [];
while (leftArray.length > 0 && rightArray.length > 0) {
if (leftArray[0] < rightArray[0]) {
result.push(leftArray.shift());
} else {
result.push(rightArray.shift());
}
}
if (leftArray.length > 0) {
result = result.concat(leftArray);
}
if (rightArray.length > 0) {
result = result.concat(rightArray);
}
return result;
};
臀部整列-O(nlogn)class MinHeap { // 최소 힙 클래스
constructor(arr) {
this.arr = [];
arr.forEach((value) => this.push(value));
}
isEmpty() {
return this.arr.length === 0;
}
heapify() {
if (!this.isEmpty()) {
const length = this.arr.length;
let index = 0;
let minIndex = 0;
let leftIndex, rightIndex;
while (index < length) {
leftIndex = MinHeap.getLeftIndex(index);
rightIndex = MinHeap.getRightIndex(index);
if (this.arr[leftIndex] && this.arr[leftIndex] < this.arr[index]) {
minIndex = leftIndex;
}
if (this.arr[rightIndex] && this.arr[rightIndex] < this.arr[minIndex]) {
minIndex = rightIndex;
}
if (minIndex !== leftIndex && minIndex !== rightIndex) {
break;
}
this.swap(index, minIndex);
index = minIndex;
}
}
}
pop() {
if (!this.isEmpty()) {
const value = this.arr.shift();
if (this.arr.length > 0) {
this.arr.unshift(this.arr.pop());
this.heapify();
}
return value;
}
}
push(value) {
this.arr.push(value);
let index = this.arr.length - 1;
let parentIndex;
while (true) {
parentIndex = MinHeap.getParentIndex(index);
if (this.arr[parentIndex] > this.arr[index]) {
this.swap(index, parentIndex);
index = parentIndex;
} else {
break;
}
}
}
swap(index1, index2) {
let temp = this.arr[index1];
this.arr[index1] = this.arr[index2];
this.arr[index2] = temp;
}
static getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
static getLeftIndex(index) {
return 2 * index + 1;
}
static getRightIndex(index) {
return 2 * index + 2;
}
}
const heapSort = (array) => {
const minHeap = new MinHeap(array);
const result = [];
while (!minHeap.isEmpty()) {
result.push(minHeap.pop());
}
return result;
};
Reference
この問題について(ソートアルゴリズム-(1)), 我々は、より多くの情報をここで見つけました https://velog.io/@winters0727/정렬-알고리즘-1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol