[Algorithms] Quicksort algorithm using TypeScript
typescript Using ALGORITHM Algorithms
2023-09-14 09:00:49 时间
Quicksort (also called partition sort and pivot sort) is arguably the most used sorting algorithm. It is the one commonly implemented internally in language runtimes. In this lesson we cover the quick sort algorithm, why is it called quick and how to implement it using TypeScript / JavaScript.
export function quickSort(array) { array = [...array]; partition(array, 0, array.length); return array; } function partition(array, start, end) { const length = end - start; if (length <= 1) return; // select the pivot const pivotIndex = start + Math.floor(Math.random() * length); // move the pivot to the beginning of the array [array[start], array[pivotIndex]] = [array[pivotIndex], array[start]]; // get the pivot value const pivot = array[start]; // get the pivot index let pivotRank = start; // loop thought the array, swap every number each is smaller // than the pivor for (let index = start + 1; index < end; index++) { if (array[index] < pivot) { // increase the rank poisition first pivotRank++; // swap the current number and rand poisition [array[index], array[pivotRank]] = [array[pivotRank], array[index]]; } } // move the pivot to the pivotRank position if (pivotRank !== start) { [array[start], array[pivotRank]] = [array[pivotRank], array[start]]; } partition(array, start, pivotRank); partition(array, pivotRank + 1, end); } const test = [5, 1, 8, 7, 4, 3, 6, 9]; const res = quickSort(test); document.write(res);
Simpfily way:
function quickSort (array) { if (array.length <= 1) { return array; } let pivotIndex = 0; let pivot = array[pivotIndex]; let less = [] let greater = [] for (let i in array) { if (i != pivotIndex) { array[i] > pivot ? greater.push(array[i]): less.push(array[i]); } } return [ ...quickSort(less), pivot, ...quickSort(greater) ] } console.log(quickSort([6, 5, 4, 3, 2, 1, 7,9, 8]))
相关文章
- [Typescript] Using Extract type until to get the value from Union type
- [Typescript] Default value for Builder pattern - 04 (keyof {} -> never)
- [Typescript] TS-toolbelt Split
- [Typescript] Extract the Discriminator from a Discriminated Union
- [Typescript] 73. Medium - Join
- [Typescript Challenges] 9. Easy - Concat
- [TypeScript] Decorator-based Validation using Class Validator
- [Vuex] Lazy Load a Vuex Module at Runtime using TypeScript
- [Vuex] Perform Async Updates using Vuex Actions with TypeScript
- [Algorithms] Insertion sort algorithm using TypeScript
- [Algorithms] Binary Search Algorithm using TypeScript
- [TypeScript] Interface and Class
- [TypeScript] Using Gulp with TypeScript
- [Typescript] Create a Type-Safe Request Handler with Zod and Express
- [Typescript] 64. Hard - AllCombinations
- [Typescript Challenges] 4. Easy - First of Array
- [Typescript] Using 'Pick' to create a sub-type from original type
- [Vuex] Lazy Load a Vuex Module at Runtime using TypeScript
- [Algorithm] Maximum Contiguous Subarray algorithm implementation using TypeScript / JavaScript
- [Algorithms] Insertion sort algorithm using TypeScript
- [TypeScript] Asynchronous Iteration using for-await-of
- [Vue + TS] Use Dependency Injection in Vue Using @Inject and @Provide Decorators with TypeScript
- [TypeScript] Using Exclude and RootDir until File Globs Lands in 2.0.
- [TypeScript] Inheritance
- TypeScript里的混合类型