DSA: JS로 보스처럼 정렬하기
목차
버블 정렬
Bubble sort is a very simply sorting algorithm. This algorithm doesn't have particular use cases other than have an introduction to the sorting algorithms for education purposes.
Bubble Sort algorithm loops through an array and compares two adjacent elements. Depending a condition, we determine if we require to switch the elements. In this way it is bubbling up the maximum value to the end of the array.
For each pair, we compare if the first element is greater than the second then the two elements are swapped. Otherwise, we continue with the next pair of elements.
의사 코드
Look at each adjacent pair If two adjacent elements are not in order Swap them and set swap counter to falsy value
시간 복잡도
버블 정렬은 이상적인 정렬 알고리즘이 아닙니다. 의사 코드에서 쌍을 비교해야 한다는 것을 알 수 있습니다. 이것은 우리가 하나의 중첩 루프를 갖게 될 것이라고 생각하게 합니다! 중첩 루프는 시간 복잡도를 O(n²)로 만듭니다.
최상의 시나리오에서는 배열이 이미 정렬되어 있습니다. 알고리즘을 약간 최적화하면 O(n)의 최상의 경우에 도달할 수 있습니다(배열이 이미 정렬된 경우).
구현
const bubbleSort = (arr) => {
if (!arr) return;
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
최적화
const bubbleSort = (arr) => {
let swapped;
for (let i = 0; i < arr.length; i++) {
swapped = false;
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (swapped == false)
break;
}
return arr;
}
선택 정렬
One more algorithm that is used for educational purposes is Selection sort. The selection sort algorithm sorts an array by repeatedly finding the minimum element (or maximum, depending the order) from the unsorted part and putting it at the beginning. In every iteration, the minimum (or maximum) element from the unsorted subarray is picked and moved to the sorted subarray.
의사 코드
Repeat in the unsorted array:
Search the unsorted data to find the smallest value
Swap the smallest value with the first unsorted element
시간 복잡도
이 검색 알고리즘은 배열의 요소를 첫 번째 요소와 비교합니다. 두 요소 중 더 작은 요소를 찾으면 첫 번째 위치로 바꿉니다. 알고리즘은 배열이 정렬될 때까지 이 패턴을 반복합니다. 쌍의 비교가 필요하므로 이를 달성하려면 두 개의 중첩 루프가 필요하다는 것을 다시 알 수 있습니다. 그것은 우리의 복잡성을 O(n²)로 만듭니다.
구현
const selectionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (arr[min] < arr[i]) {
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
return arr;
}
삽입 정렬
Insertion sort is a sorting algorithm that works similar to how you sort playing cards in your hands. Weird eh?
The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Insertion sort is efficient for small data values or almost sorted arrays.
The algorithm is simple. We iterate through the array, we pick an element from the unsorted part and we insert it to the correct place.
의사 코드
The first element of the array is 'sorted'
Repeat to the unsorted part of the array
Find the position of the next unsorted item
Insert into the 'sorted' position by shifting elements
시간 복잡도
최악의 경우 배열은 반대 순서로 정렬됩니다. 그리고 모든 요소를 비교하여 적절한 위치에 삽입해야 합니다. 그것은 O(n²)가 될 것입니다.
구현
const insertionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
if (arr[i] < arr[0]) {
arr.unshift(arr.splice(i, 1)[0])
} else {
for (let j = 1; j < i; j++) {
if (arr[i] > arr[j - 1] && arr[i] < arr[j]) {
arr.splice(j, 0, arr.splice(i, 1)[0])
}
}
}
}
return arr
}
병합 정렬
Merge sort is using the divide and conquer technique. We will have a mergeSort function that partitions the array and a merge function that merge the partitions.
The main algorithm of merge sort divides the input array into two halves and calls itself with the two halves. This recursion continues until we reach granular components that are sorted. Then we proceed with merging these individual pieces into one result array.
의사 코드
• 배열의 중간 요소를 찾습니다. mid = Math.floor((array.length)/2)
• 어레이를 좌우로 접합
• 호출 병합 정렬 켜기(왼쪽, 중간)
• 호출 병합 정렬 켜짐(mid+1,right)
• 왼쪽이 오른쪽보다 작을 때까지 계속합니다.
• 그런 다음 병합 기능을 호출하여 배열 병합을 수행합니다.
시간 복잡도
병합 정렬은 복잡한 알고리즘입니다. 알고리즘을 반으로 나누면 O(nlogn)의 시간 복잡도가 커집니다. 보조 결과 배열이 필요하며 이로 인해 O(n)의 공간 복잡도가 발생합니다.
구현
const mergeSort = (arr) => {
if (arr.length === 1) {
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle)
const right = arr.slice(middle)
return merge(mergeSort(left), mergeSort(right))
}
const merge = (left, right) => {
let arr = []
// Break out of loop if any one of the array gets empty
while (left.length && right.length) {
if (left[0] < right[0]) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}
return [...arr, ...left, ...right]
}
빠른 정렬
QuickSort is a Divide and Conquer sorting algorithm. It's much faster than linear sorting algorithms. Quick-sort is a comparison sorting algorithm, meaning that the sorting occurs by iterating through the array and comparing two defined values to a pivot. This pivot determines how to partition the collection. We have different ways to pick the pivot value, and this can affect the complexity of the algorithm.
의사 코드
While the collection is unsorted
Pick a pivot
Partition the array
All values smaller than pivot to the left and larger to the right
Perform pivot and partition on the left and the right partition
시간 복잡도
이 알고리즘의 성능은 피벗에 크게 의존합니다. 항상 첫 번째 요소를 피벗으로 선택하고 이미 정렬된 배열이 있는 경우 퀵 정렬이 정렬을 시도합니다. 첫 번째 요소를 피벗으로 선택하면 호출 스택이 정말 길어집니다. 이 최악의 경우 O(n²)의 복잡도에 도달할 수 있습니다. 그러나 성능 피벗이 있는 평균적인 경우는 O(nlogn)입니다.
const quickSort = (arr, low, high) => {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
return arr;
}
const partition = (arr, low, high) => {
const pivot = arr[high];
let i = (low - 1);
for (let j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
const swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
기타 정렬 알고리즘
Other famous sorting algorithms are:
- Heap Sort
Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort algorithm where we first find the minimum element and place it at the beginning. We repeat the same process for the remaining elements. Time complexity: O(N log N).
- Counting Sort
Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects that are having distinct key-values. Then do arithmetic to calculate the position of each object in the output sequence. Time complexity: O(n)
- Radix Sort
The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.
- Bucket Sort
Bucket sort is mainly useful when input is uniformly distributed over a range. For example, when we want to sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range.
Reference
이 문제에 관하여(DSA: JS로 보스처럼 정렬하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/ale3oula/dsa-sorting-like-a-boss-with-js-42om텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
