SORT COLORS

What is a Sorting Algorithm?

Sorting algorithms are a phối of instructions that take an array or menu as an input đầu vào và arrange the items into a particular order.

Bạn đang xem: Sort colors

Sorts are most commonly in numerical or a khung of alphabetical (called lexicographical) order, và can be in ascending (A-Z, 0-9) or descending (Z-A, 9-0) order.

Why Sorting Algorithms are Important

Since sorting can often reduce the complexity of a problem, it is an important algorithm in Computer Science. These algorithms have direct applications in searching algorithms, database algorithms, divide và conquer methods, data structure algorithms, and many more.

Trade-Offs of Algorithms

When using different algorithms some questions have sầu to be asked. How big is the collection being sorted? How much memory is at disposal to lớn be used? Does the collection need lớn grow?

The answers to lớn these questions may determine what algorithm is going to work best for the situation. Some algorithms lượt thích merge sort may need a lot of space khổng lồ run, while insertion sort is not always the faschạy thử but it doesn"t require many resources to run.

You should determine what the requirements of the system are and its limitations before deciding what algorithm to lớn use.

Some Common Sorting Algorithms

Some of the most comtháng sorting algorithms are:

Selection SortBubble SortInsertion SortMerge SortQuiông xã SortHeap SortCounting SortRadix SortBucket Sort

But before we get inlớn each of these, let"s learn a bit more about what makes classifies a sorting algorithm.

Classification of a Sorting Algorithm

Sorting algorithms can be categorized based on the following parameters:

Based on Number of Swaps or Inversion This is the number of times the algorithm swaps elements khổng lồ sort the input. Selection Sort requires the minimum number of swaps.Based on Recursion or Non-Recursion Some sorting algorithms, such as Quick Sort , use recursive techniques to sort the đầu vào. Other sorting algorithms, such as Selection Sort or Insertion Sort , use non-recursive sầu techniques. Finally, some sorting algorithm, such as Merge Sort , make use of both recursive sầu as well as non-recursive sầu techniques khổng lồ sort the đầu vào.Based on Stability Sorting algorithms are said to lớn be stable if the algorithm maintains the relative sầu order of elements with equal keys. In other words, two equivalent elements remain in the same order in the sorted output as they were in the input.Insertion sort , Merge Sort , and Bubble Sort are stableHeap Sort & Quiông xã Sort are not stableBased on Extra Space Requirement Sorting algorithms are said lớn be in place if they require a constant O(1) extra space for sorting.Insertion sort & Quick-sort are in place sort as we move sầu the elements about the pivot và do not actually use a separate array which is NOT the case in merge sort where the form size of the đầu vào must be allocated beforehand lớn store the output during the sort.Merge Sort is an example of out place sort as it require extra memory space for its operations.

Best possible time complexity for any comparison based sorting

Any comparison based sorting algorithm must make at least nLog2n comparisons to sort the input đầu vào array, & Heapsort và merge sort are asymptotically optimal comparison sorts. This can be easily proved by drawing a decision tree diagram.

Bucket Sort

Bucket Sort is a comparison sort algorithm that operates on elements by dividing them into different buckets và then sorting these buckets individually. Each bucket is sorted individually using a separate sorting algorithm or by applying the bucket sort algorithm recursively.

Bucket Sort is mainly useful when the input is uniformly distributed over a range.

Assume you have the following problem in front of you

You have sầu been given a large array of floating point integers lying uniformly between the lower and upper bound. This array now needs khổng lồ be sorted.

A simple way to solve this problem would be lớn use another sorting algorithm such as Merge sort, Heap Sort or Quiông chồng Sort. However, these algorithms guarantee a best case time complexity of O(NlogN). However, using bucket sort, the above task can be completed in O(N)time.

Let"s have a closer look at it.

Consider that you need to lớn create an array of lists, that is of buckets. Elements now need to be inserted into lớn these buckets on the basis of their properties. Each of these buckets can then be sorted individually using Insertion Sort.

Pseubởi Code for Bucket Sort:

void bucketSort(float<> a,int n) for(each floating integer "x" in n) insert x inlớn bucket; for(each bucket) sort(bucket);

Counting Sort

Counting Sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic khổng lồ calculate the position of each object in the output sequence.

Example:

For simplithành phố, consider the data in the range 0 khổng lồ 9. Input data: 1, 4, 1, 2, 7, 5, 2 1) Take a count array to store the count of each chất lượng object. Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 2 0 1 1 0 1 0 0 2) Modify the count array such that each element at each index stores the sum of previous counts. Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 4 4 5 6 6 7 7 7The modified count array indicates the position of each object in the output sequence. 3) đầu ra each object from the input đầu vào sequence followed by decreasing its count by 1. Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2. Put data 1 at index 2 in output. Decrease count by 1 to lớn place next data 1 at an index 1 smaller than this index.

Properties

Space complexity: O(K)Best case performance: O(n+K)Average case performance: O(n+K)Worst case performance: O(n+K)Stable: Yes (K is the number of distinct elements in the array)

Implementation in JavaScript

let numbers = <1, 4, 1, 2, 7, 5, 2>;let count = <>;let i, z = 0;let max = Math.max(...numbers); // initialize counterfor (i = 0; i 0) numbers = i; }// output sorted arrayfor (i=0; i

C++ Implementation

#include void countSort(int upperBound, int lowerBound, std::vector numbersToSort) //lower & upper bounds of numbers in vector int range = upperBound - lowerBound; //create a range large enough khổng lồ get every number between the min and max std::vector counts (range); //initialize of counts of the kích thước of the range std::fill(counts.begin(), counts.end(), 0); //fill vector of zeros for (int i = 0; i

Swift Implementation

func countingSort(_ array: ) // Create an array to store the count of each element let maxElement = array.max() ?? 0 var countArray = (repeating: 0, count: Int(maxElement + 1)) for element in array countArray += 1 var z = 0 var sortedArray = (repeating: 0, count: array.count) for index in 1 .. 0 sortedArray = index z += 1 countArray -= 1 print(sortedArray)

Insertion Sort

Insertion sort is a simple sorting algorithm for a small number of elements.

Example:

In Insertion sort, you compare the key element with the previous elements. If the previous elements are greater than the key element, then you move the previous element to the next position.

Start from index 1 khổng lồ form size of the đầu vào array.

< 8 3 5 1 4 2 >

Step 1 :

*
" width="242" height="47" loading="lazy">

key = 3 //starting from 1st index. Here `key` will be compared with the previous elements. In this case, `key` is compared with 8. since 8 > 3, move the element 8 lớn the next position và insert `key` to the previous position. Result: < 3 8 5 1 4 2 >Step 2 :

*
" width="242" height="75" loading="lazy">

key = 5 //2nd index 8 > 5 //move sầu 8 to 2nd index và insert 5 to lớn the 1st index. Result: < 3 5 8 1 4 2 >Step 3 :

*
" width="242" height="73" loading="lazy">

key = 1 //3rd index 8 > 1 => < 3 5 1 8 4 2 > 5 > 1 => < 3 1 5 8 4 2 > 3 > 1 => < 1 3 5 8 4 2 > Result: < 1 3 5 8 4 2 >Step 4 :

*
" width="242" height="73" loading="lazy">

key = 4 //4th index 8 > 4 => < 1 3 5 4 8 2 > 5 > 4 => < 1 3 4 5 8 2 > 3 > 4 ≠> stop Result: < 1 3 4 5 8 2 >Step 5 :

*
" width="242" height="62" loading="lazy">

key = 2 //5th index 8 > 2 => < 1 3 4 5 2 8 > 5 > 2 => < 1 3 4 2 5 8 > 4 > 2 => < 1 3 2 4 5 8 > 3 > 2 => < 1 2 3 4 5 8 > 1 > 2 ≠> stop Result: <1 2 3 4 5 8>

*
" width="242" height="63" loading="lazy">The algorithm shown below is a slightly optimized version lớn avoid swapping the key element in every iteration. Here, the key element will be swapped at the kết thúc of the iteration (step).

InsertionSort(arr<>) for j = 1 to arr.length key = arr i = j - 1 while i > 0 and arr > key arr = arr i = i - 1 arr = keyHere is a detailed implementation in JavaScript:

function insertion_sort(A) var len = array_length(A); var i = 1; while (i = 0 &và A > x) A = A; j = j - 1; A = x; i = i + 1; }A quichồng implementation in Swift is shown below:

var array = <8, 3, 5, 1, 4, 2> func insertionSort(array:inout Array) -> Array for j in 0.. 0 &và array > key) array = array i = i-1 array = key return array }The Java example is shown below:

public int<> insertionSort(int<> arr) for (j = 1; j 0 & arr > key) arr = arr i -= 1 arr = key } return arr;And in c....

void insertionSort(int arr<>, int n) int i, key, j; for (i = 1; i = 0 &và arr > key) arr = arr; j = j-1; arr = key; }

Properties:

Space Complexity: O(1)Time Complexity: O(n), O(n* n), O(n* n) for Best, Average, Worst cases respectively.Best Case: array is already sortedAverage Case: array is randomly sortedWorst Case: array is reversely sorted.Sorting In Place: YesStable: Yes

Heapsort

Heapsort is an efficient sorting algorithm based on the use of max/min heaps. A heap is a tree-based data structure that satisfies the heap property – that is for a max heap, the key of any node is less than or equal lớn the key of its parent (if it has a parent).

This property can be leveraged to access the maximum element in the heap in O(logn) time using the maxHeapify method. We perform this operation n times, each time moving the maximum element in the heap lớn the top of the heap & extracting it from the heap & into a sorted array. Thus, after n iterations we will have a sorted version of the input đầu vào array.

The algorithm is not an in-place algorithm và would require a heap data structure to lớn be constructed first. The algorithm is also unstable, which means when comparing objects with same key, the original ordering would not be preserved.

This algorithm runs in O(nlogn) time and O(1) additional space since all operations are performed entirely in-place.

The best, worst and average case time complexity of Heapsort is O(nlogn). Although heapsort has a better worse-case complexity than quicksort, a well-implemented quicksort runs faster in practice. This is a comparison-based algorithm so it can be used for non-numerical data sets insofar as some relation (heap property) can be defined over the elements.

An implementation in Java is as shown below :

import java.util.Arrays;public class Heapsort public static void main(String<> args) //kiểm tra arrayInteger<> arr = 1, 4, 3, 2, 64, 3, 2, 4, 5, 5, 2, 12, 14, 5, 3, 0, -1;String<> strarr = "hope you find this helpful!", "wef", "rg", "q2rq2r", "avs", "erhijer0g", "ewofij", "gwe", "q", "random";arr = heapsort(arr);strarr = heapsort(strarr);System.out.println(Arrays.toString(arr));System.out.println(Arrays.toString(strarr));//O(nlogn) TIME, O(1) SPACE, NOT STABLEpublic static > E<> heapsort(E<> arr)int heaplength = arr.length;for(int i = arr.length/2; i>0;i--)arr = maxheapify(arr, i, heaplength);for(int i=arr.length-1;i>=0;i--)E max = arr<0>;arr<0> = arr;arr = max;heaplength--;arr = maxheapify(arr, 1, heaplength);return arr;//Creates maxheap from arraypublic static > E<> maxheapify(E<> arr, Integer node, Integer heaplength)Integer left = node*2;Integer right = node*2+1;Integer largest = node;if(left.compareTo(heaplength) = 0)largest = left;if(right.compareTo(heaplength) = 0)largest = right;if(largest != node)E temp = arr;arr = arr;arr = temp;maxheapify(arr, largest, heaplength);return arr;Implementation in C++

#include using namespace std;void heapify(int arr<>, int n, int i) int largest = i; int l = 2*i + 1; int r = 2*i + 2; if (l arr) largest = l; if (r arr) largest = r; if (largest != i) swap(arr, arr); heapify(arr, n, largest); void heapSort(int arr<>, int n) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i=n-1; i>=0; i--) swap(arr<0>, arr); heapify(arr, i, 0); void printArray(int arr<>, int n) { for (int i=0; i

Radix Sort

Prerequisite: Counting Sort

QuickSort, MergeSort, and HeapSort are comparison-based sorting algorithms. CountSort is not. It has the complexity of O(n+k), where k is the maximum element of the đầu vào array. So, if k is O(n), CountSort becomes linear sorting, which is better than comparison based sorting algorithms that have O(nlogn) time complexity.

The idea is lớn extkết thúc the CountSort algorithm to get a better time complexity when k goes O(n2). Here comes the idea of Radix Sort.

The Algorithm:

For each digit i where i varies from the least significant digit to lớn the most significant digit of a number, sort input đầu vào array using countsort algorithm according to lớn ith digit. We used count sort because it is a stable sort.

Example: Assume the đầu vào array is:

10, 21, 17, 34, 44, 11, 654, 123

Based on the algorithm, we will sort the đầu vào array according lớn the one"s digit (least significant digit).

0: 101: 21 112:3: 1234: 34 44 6545:6:7: 178:9:

So, the array becomes 10, 21, 11, 123, 24, 44, 654, 17.

Now, we"ll sort according to the ten"s digit:

0:1: 10 11 172: 21 1233: 344: 445: 6546:7:8:9:

Now, the array becomes : 10, 11, 17, 21, 123, 34, 44, 654.

Finally, we sort according lớn the hundred"s digit (most significant digit):

0: 010 011 017 021 034 0441: 1232:3:4:5:6: 6547:8:9:

The array becomes : 10, 11, 17, 21, 34, 44, 123, 654 which is sorted. This is how our algorithm works.

Xem thêm: Biec Ron Là Gì - Ý Nghĩa Tượng Trưng Biếc Rờn

An implementation in C:

void countsort(int arr<>,int n,int place){ int i,freq=0; //range for integers is 10 as digits range from 0-9 int output; for(i=0;i=0;i--) output/place)%range>-1>=arr; freq<(arr/place)%range>--; for(i=0;i

Selection Sort

Selection Sort is one of the simplest sorting algorithms. This algorithm gets its name from the way it iterates through the array: it selects the current smallest element, & swaps it into lớn place.

Here"s how it works:

Find the smallest element in the array và swap it with the first element.Find the second smallest element và swap with with the second element in the array.Find the third smallest element and swap wit with the third element in the array.Repeat the process of finding the next smallest element và swapping it into lớn the correct position until the entire array is sorted.

But, how would you write the code for finding the index of the second smallest value in an array?

An easy way is khổng lồ notice that the smallest value has already been swapped inkhổng lồ index 0, so the problem reduces to finding the smallest element in the array starting at index 1.

Selection sort always takes the same number of key comparisons — N(N − 1)/2.

Implementation in C/C++

The following C++ program contains an iterative as well as a recursive sầu implementation of the Selection Sort algorithm. Both implementations are invoked in the main() function.

#include #include using namespace std;templatevoid print_array(T const(&arr)) for (size_t i = 0; i

Implementation in JavaScript

function selection_sort(A) var len = A.length; for (var i = 0; i

Implementation in Python

def seletion_sort(arr): if not arr: return arr for i in range(len(arr)): min_i = i for j in range(i + 1, len(arr)): if arr

Implementation in Java

public void selectionsort(int array<>) int n = array.length; //method to lớn find length of array for (int i = 0; i

Implementation in MATLAB

function = selectionSort(unsorted) len = length(unsorted); for i = 1:1:len minInd = i; for j = i+1:1:len if unsorted(j)

Properties

Space Complexity: O(n)Time Complexity: O(n2)Sorting in Place: YesStable: No

Bubble Sort

Just like the way bubbles rise from the bottom of a glass, bubble sort is a simple algorithm that sorts a list, allowing either lower or higher values lớn bubble up lớn the top. The algorithm traverses a danh mục and compares adjacent values, swapping them if they are not in the correct order.

With a worst-case complexity of O(n^2), bubble sort is very slow compared lớn other sorting algorithms lượt thích quicksort. The upside is that it is one of the easiest sorting algorithms to lớn underst& & code from scratch.

From technical perspective, bubble sort is reasonable for sorting small-sized arrays or specially when executing sort algorithms on computers with remarkably limited memory resources.

Example:

First pass through the list:

Starting with <4, 2, 6, 3, 9>, the algorithm compares the first two elements in the array, 4 và 2. It swaps them because 2 <2, 4, 6, 3, 9>It compares the next two values, 4 & 6. As 4 <2, 4, 6, 3, 9>The next two values are also swapped because 3 <2, 4, 3, 6, 9>The last two values, 6 & 9, are already in order, so the algorithm does not swap them.

Second pass through the list:

2 <2, 4, 3, 6, 9>The algorithm swaps the next two values because 3 <2, 3, 4, 6, 9>No swap as 4 <2, 3, 4, 6, 9>Again, 6 <2, 3, 4, 6, 9>

The danh mục is already sorted, but the bubble sort algorithm doesn"t realize this. Rather, it needs to lớn complete an entire pass through the menu without swapping any values lớn know the list is sorted.

Third pass through the list:

<2, 4, 3, 6, 9> => <2, 4, 3, 6, 9><2, 4, 3, 6, 9> => <2, 4, 3, 6, 9><2, 4, 3, 6, 9> => <2, 4, 3, 6, 9><2, 4, 3, 6, 9> => <2, 4, 3, 6, 9>

Clearly bubble sort is far from the most efficient sorting algorithm. Still, it"s simple khổng lồ wrap your head around and implement yourself.

PropertiesSpace complexity: O(1)Best case performance: O(n)Average case performance: O(n*n)Worst case performance: O(n*n)Stable: Yes

Video Explanation

Bubble sort algorithm

Example in JavaScript

let arr = <1, 4, 7, 45, 7,43, 44, 25, 6, 4, 6, 9>, sorted = false;while(!sorted) sorted = true; for(var i=0; i

Example in Java

public class BubbleSort static void sort(int<> arr) int n = arr.length; int temp = 0; for(int i=0; i arr) temp = arr; arr = arr; arr = temp; public static void main(String<> args) for(int i=0; i

Example in C++

// Recursive Implementationvoid bubblesort(int arr<>, int n)if(n==1)//Initial Casereturn;bool swap_flag = false;for(int i=0;iarr)int temp=arr;arr=arr;arr=temp;swap_flag = true; // IF no two elements were swapped in the loop, then return, as array is sorted if(swap_flag == false)return;bubblesort(arr,n-1);//Recursion for remaining array

Example in Swift

func bubbleSort(_ inputArray: ) -> guard inputArray.count > 1 else return inputArray // make sure our đầu vào array has more than 1 element var numbers = inputArray // function arguments are constant by mặc định in Swift, so we make a copy for i in 0.. numbers numbers.swapAt(j, j + 1) return numbers // return the sorted array

Example in Python

def bubbleSort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr > arr : arr, arr = arr, arr print(arr)

Example in PHP

function bubble_sort($arr) $kích cỡ = count($arr)-1; for ($i=0; $i

Example in C

#include int BubbleSort(int array<>, int n);int main(void) int arr<> = 10, 2, 3, 1, 4, 5, 8, 9, 7, 6; BubbleSort(arr, 10); for (int i = 0; i array) // For decreasing order use int swap = array; array = array; array = swap;

Quick Sort

Quiông chồng sort is an efficient divide và conquer sorting algorithm. Average case time complexity of Quichồng Sort is O(nlog(n)) with worst case time complexity being O(n^2) depending on the selection of the pivot element, which divides the current array inkhổng lồ two sub arrays.

For instance, the time complexity of Quick Sort is approximately O(nlog(n)) when the selection of pivot divides original array inlớn two nearly equal sized sub arrays.

On the other hvà, if the algorithm, which selects of pivot element of the input đầu vào arrays, consistently outputs 2 sub arrays with a large difference in terms of array sizes, quichồng sort algorithm can achieve sầu the worst case time complexity of O(n^2).

The steps involved in Quichồng Sort are:

Choose an element khổng lồ serve sầu as a pivot, in this case, the last element of the array is the pivot.Partitioning: Sort the array in such a manner that all elements less than the pivot are to the left, and all elements greater than the pivot are to the right.hotline Quicksort recursively, taking into lớn account the previous pivot to lớn properly subdivide the left và right arrays. (A more detailed explanation can be found in the comments below)

Example Implementations in Various Languages

Implementation in JavaScript:

const arr = <6, 2, 5, 3, 8, 7, 1, 4>;const quickSort = (arr, start, end) => if(start let pivot = end; // Set i to start - 1 so that it can access the first index in the sự kiện that the value at arr<0> is greater than arr // Succeeding comments will expound upon the above phản hồi let i = start - 1, j = start; // Increment j up lớn the index preceding the pivot while (j arr) j++; // When the value at arr is less than the pivot: // increment i (arr will be a value greater than arr) & swap the value at arr và arr else i++; swap(arr, j, i); j++; //The value at arr will be greater than the value of arr swap(arr, i + 1, pivot); //You return i + 1, as the values lớn the left of it are less than arr, và values to the right are greater than arr // As such, when the recursive quicksorts are called, the new sub arrays will not include this the previously used pivot value return i + 1;const swap = (arr, firstIndex, secondIndex) => let temp = arr; arr = arr; arr = temp;quickSort(arr, 0, arr.length - 1);console.log(arr);

Implementation in C

#include void swap(int* a, int* b) int t = *a; *a = *b; *b = t; int partition (int arr<>, int low, int high) { int pivot = arr; int i = (low - 1); for (int j = low; j

Implementation in Python3

import randomz=def quicksort(z): if(len(z)>1): piv=int(len(z)/2) val=z lft= res=quicksort(lft)+mid+quicksort(rgt) return res else: return z ans1=quicksort(z)print(ans1)

Implementation in MATLAB

a = <9,4,7,3,8,5,1,6,2>;sorted = quicksort(a,1,length(a));function = quicksort(unsorted, low, high) if low The space complexity of quiông chồng sort is O(n) . This is an improvement over other divide & conquer sorting algorithms, which take O(nlong(n)) space.

Quick sort achieves this by changing the order of elements within the given array. Compare this with the merge sort algorithm which creates 2 arrays, each length n/2, in each function call.

However there does exist the problem of this sorting algorithm being of time O(n*n) if the pivot is always kept at the middle. This can be overcomed by utilizing a random pivot

Complexity

Best, average, worst, memory: n log(n)n log(n)n 2log(n). It"s not a stable algorithm, và quicksort is usually done in-place with O(log(n)) staông chồng space.

The space complexity of quick sort is O(n). This is an improvement over other divide and conquer sorting algorithms, which take O(n log(n)) space.

Timsort

Timsort is a fast sorting algorithm working at stable O(N log(N)) complexity.

Timsort is a blover of Insertion Sort & Mergesort. This algorithm is implemented in Java’s Arrays.sort() as well as Python’s sorted() & sort(). The smaller parts are sorted using Insertion Sort và are later merged together using Mergesort.

A quiông xã implementation in Python:

def binary_search(the_array, chiến thắng, start, end): if start == end: if the_array > item: return start else: return start + 1 if start > end: return start mid = round((start + end)/ 2) if the_array item: return binary_search(the_array, thành tựu, start, mid - 1) else: return mid"""Insertion sort that timsort uses if the array form size is small or ifthe kích cỡ of the "run" is small"""def insertion_sort(the_array): l = len(the_array) for index in range(1, l): value = the_array pos = binary_search(the_array, value, 0, index - 1) the_array = the_array<:pos> + + the_array + the_array return the_arraydef merge(left, right): """Takes two sorted lists và returns a single sorted danh mục by comparing the elements one at a time. <1, 2, 3, 4, 5, 6> """ if not left: return right if not right: return left if left<0>

Complexity:

Tim sort has a stable Complexity of O(N log(N)) và compares really well with Quicksort. A comparison of complexities can be found on this chart.

Merge Sort

Merge Sort is a Divide và Conquer algorithm. It divides input đầu vào array in two halves, calls itself for the two halves & then merges the two sorted halves. The major portion of the algorithm is given two sorted arrays, and we have sầu to merge them inlớn a single sorted array. The whole process of sorting an array of N integers can be summarized inlớn three steps-

Divide the array into two halves.Sort the left half and the right half using the same recurring algorithm.Merge the sorted halves.

There is something known as the Two Finger Algorithm that helps us merge two sorted arrays together. Using this subroutine & calling the merge sort function on the array halves recursively will give us the final sorted array we are looking for.

Since this is a recursion based algorithm, we have a recurrence relation for it. A recurrence relation is simply a way of representing a problem in terms of its subproblems.

T(n) = 2 * T(n / 2) + O(n)

Putting it in plain English, we break down the subproblem inkhổng lồ two parts at every step và we have sầu some linear amount of work that we have sầu to vày for merging the two sorted halves together at each step.

Complexity

The biggest advantage of using Merge sort is that the time complexity is only n*log(n) lớn sort an entire Array. It is a lot better than n^2 running time of bubble sort or insertion sort.

Before we write code, let us underst& how merge sort works with the help of a diagram.

Initially we have an array of 6 unsorted integers Arr(5, 8, 3, 9, 1, 2)We split the array inlớn two halves Arr1 = (5, 8, 3) & Arr2 = (9, 1, 2).Again, we divide them into lớn two halves: Arr3 = (5, 8) and Arr4 = (3) & Arr5 = (9, 1) & Arr6 = (2)Again, we divide them into two halves: Arr7 = (5), Arr8 = (8), Arr9 = (9), Arr10 = (1) and Arr6 = (2)We will now compare the elements in these sub arrays in order to merge them.

Properties:

Space Complexity: O(n)Time Complexity: O(n*log(n)). The time complexity for the Merge Sort might not be obvious from the first glance. The log(n) factor that comes in is because of the recurrence relation we have sầu mentioned before.Sorting In Place: No in a typical implementationStable: YesParallelizable :yes (Several parallel variants are discussed in the third edition of Cormen, Leiserson, Rivest, & Stein"s Introduction khổng lồ Algorithms.)

C++ Implementation

void merge(int array<>, int left, int mid, int right){ int i, j, k; // Size of left sublistint size_left = mid - left + 1;// Size of right sublistint size_right = right - mid;/* create temp arrays */int Left, Right;/* Copy data lớn temp arrays L<> and R<> */for(i = 0; i

JavaScript Implementation

function mergeSort (arr) { if (arr.length First we check the length of the array. If it is 1 then we simply return the array. This would be our base case. Else, we will find out the middle value & divide the array into lớn two halves. We will now sort both of the halves with recursive calls to lớn MergeSort function.

function merge (a,b) { var result = <>; while (a.length >0 && b.length >0) result.push(a<0> When we merge the two halfs, we store the result in an auxilliary array. We will compare the starting element of left array lớn the starting element of right array. Whichever is lesser will be pushed inkhổng lồ the results array và we will remove it from there respective arrays using

var demo = <5,6,7,3,1,3,15>;console.log(mergeSort(test));>> <1, 3, 3, 5, 6, 7, 15>

A Merge Sort YouTube Tutorial

Here"s a good YouTube Clip that walks through the topic in detail.

Implementaion in JS

const danh mục = <23, 4, 42, 15, 16, 8, 3>const mergeSort = (list) =>{ if(các mục.length { var result = <>; while(left.length || right.length) { if(left.length && right.length) { if(left<0>

Implementation in C

#include #includevoid merge(int arr<>, int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L, R; for (i = 0; i

Implementation in C++

Let us consider array A = 2,5,7,8,9,12,13 và array B = 3,5,6,9,15 và we want array C lớn be in ascending order as well.

void mergesort(int A<>,int size_a,int B<>,int size_b,int C<>){ int token_a,token_b,token_c; for(token_a=0, token_b=0, token_c=0; token_a

Implementation in Python

def merge(left,right,compare):result = <> i,j = 0,0while (i

Implementation in Java

public class mergesort {public static int<> mergesort(int<> arr,int lo,int hi) if(lo==hi) int<> ba=new int<1>;ba<0>=arr;return ba;int mid=(lo+hi)/2;int arr1<>=mergesort(arr,lo,mid);int arr2<>=mergesort(arr,mid+1,hi);return merge(arr1,arr2);public static int<> merge(int<> arr1,int<> arr2) {int i=0,j=0,k=0;int n=arr1.length;int m=arr2.length;int<> arr3=new int;while(i

Example in Java

public class mergesort { public static int<> mergesort(int<> arr, int lo, int hi) if (lo == hi) int<> cha = new int<1>; ba<0> = arr; return ba; int mid = (lo + hi) / 2; int arr1<> = mergesort(arr, lo, mid); int arr2<> = mergesort(arr, mid + 1, hi); return merge(arr1, arr2); public static int<> merge(int<> arr1, int<> arr2) { int i = 0, j = 0, k = 0; int n = arr1.length; int m = arr2.length; int<> arr3 = new int; while (i
table('setting')->where("{$db->web}")->select('code_footer'); if($oh->code_footer){ # nếu có code header tùy chỉnh $code_footer = htmlspecialchars_decode($oh->code_footer); $code_footer = str_replace('[home_link]', $home, $code_footer); $code_footer = str_replace('[home_name]', $h, $code_footer); $code_footer = str_replace('[link]', $link, $code_footer); $code_footer = str_replace('[title]', $head->tit, $code_footer); $code_footer = str_replace('[des]', $head->des, $code_footer); $code_footer = str_replace('[key]', $head->key, $code_footer); $code_footer = str_replace('[image]', $head->img, $code_footer); $code_footer = str_replace('[link]', $link, $code_footer); $code_footer = str_replace('[date_Y]', date('Y'), $code_footer); echo $code_footer; } ?>