Алгоритми сортування, пояснені прикладами на Python, Java та C ++

Що таке алгоритм сортування?

Алгоритми сортування - це набір інструкцій, які беруть масив або список як вхідні дані та упорядковують елементи в певний порядок.

Сорти найчастіше мають цифровий або алфавітний формат (так званий лексикографічний), і можуть бути у порядку зростання (AZ, 0-9) або спадання (ZA, 9-0).

Чому алгоритми сортування важливі

Оскільки сортування часто може зменшити складність проблеми, це важливий алгоритм в інформатиці. Ці алгоритми мають пряме застосування в алгоритмах пошуку, алгоритмах баз даних, методах поділу та завоювання, алгоритмах структури даних та багатьох інших.

Компроміси алгоритмів

При використанні різних алгоритмів потрібно задати деякі питання. Наскільки велика колекція сортується? Скільки пам’яті слід використовувати? Чи потрібно колекції зростати?

Відповіді на ці запитання можуть визначати, який алгоритм буде найкращим чином відповідати ситуації. Деякі алгоритми, такі як сортування за злиттям, можуть вимагати багато місця для запуску, тоді як сортування вставки не завжди є найшвидшим, але для запуску не потрібно багато ресурсів.

Вам слід визначити, які вимоги до системи та її обмеження, перш ніж вирішити, який алгоритм використовувати.

Деякі загальні алгоритми сортування

Деякі найпоширеніші алгоритми сортування:

  • Сортування вибору
  • Сортування бульбашок
  • Сортування вставки
  • Сортувати злиття
  • Швидке сортування
  • Сортування купи
  • Сортування підрахунку
  • Сортування Radix
  • Сортування відра

Але перш ніж ми розберемося з кожним із них, давайте дізнаємось трохи більше про те, що робить класифікує алгоритм сортування.

Класифікація алгоритму сортування

Алгоритми сортування можна класифікувати за такими параметрами:

  1. На основі кількості обмінів або інверсії Це кількість разів, коли алгоритм міняє місцями елементи для сортування вхідних даних.  Selection Sort  вимагає мінімальної кількості свопів.
  2. На основі кількості порівнянь Це кількість разів, коли алгоритм порівнює елементи для сортування вхідних даних. Використовуючи нотацію Big-O, перелічені вище приклади алгоритмів сортування вимагають принаймні   O(nlogn)порівнянь у найкращому випадку та   O(n^2)  порівнянь у гіршому випадку для більшості результатів.
  3. На основі рекурсії або Quick Sortнерекурсії Деякі алгоритми сортування, наприклад   , використовують рекурсивні методи для сортування вхідних даних. Інші алгоритми сортування, такі як   Selection Sort  або   Insertion Sort, використовують нерекурсивні методи. Нарешті, деякі алгоритми сортування, такі як   Merge Sort, використовують як рекурсивні, так і нерекурсивні методи для сортування вхідних даних.
  4. Засновано на алгоритмах сортування за стабільністю,   stable  якщо алгоритм підтримує відносний порядок елементів з однаковими ключами. Іншими словами, два еквівалентні елементи залишаються в тому ж порядку у відсортованому виведенні, як вони були у вхідних даних.
  5. Insertion sort,,   Merge Sortі   Bubble Sort  стабільні
  6. Heap Sort  і   Quick Sort  не є стабільними
  7. На основі вимоги до додаткового простору алгоритми сортування називаються такими,   in place  якщо вони потребують постійного   O(1)  додаткового місця для сортування.
  8. Insertion sort  і   Quick-sort  є   своїм in place  родом , як ми переміщаємо елементи щодо осі повороту і на самому ділі не використовувати окремий масив , який не має місця в сортуваннях злиття , де розмір входу повинен бути виділений заздалегідь , щоб зберегти вихід під час сортування.
  9. Merge Sort  є прикладом   out place  сортування, оскільки для його роботи потрібен додатковий простір у пам'яті.

Найкраща часова складність для будь-якого сортування на основі порівняння

Будь-який алгоритм сортування на основі порівняння повинен робити принаймні порівняння nLog2n, щоб сортувати вхідний масив, а сортування за допомогою Хепсорту та злиття є асимптотично оптимальними сортами порівняння. Це можна легко довести, склавши діаграму дерева рішень.

Сортування відра

Сортування сегмента - це алгоритм сортування порівняння, який діє на елементи, розділяючи їх на різні сегменти, а потім сортуючи ці сегменти окремо. Кожне сегмент сортується окремо за допомогою окремого алгоритму сортування або шляхом рекурсивного застосування алгоритму сортування сегмента.

Сортування сегмента корисно в основному, коли вхідні дані рівномірно розподілені по діапазону.

Припустимо, перед вами така проблема

Вам було надано великий масив цілих чисел із плаваючою комою, які рівномірно лежать між нижньою та верхньою межею. Цей масив тепер потрібно відсортувати.

Простим способом вирішення цієї проблеми було б використання іншого алгоритму сортування, такого як злиття, сортування за купою або швидке сортування. Однак ці алгоритми гарантують найкращу часову складність O (NlogN). Однак, використовуючи відсортоване сортування, вищезазначене завдання може бути виконане за O (N) раз.

Давайте розглянемо його ближче.

Вважайте, що вам потрібно створити масив списків, тобто сегментів. Тепер елементи слід вставляти в ці сегменти на основі їх властивостей. Потім кожне з цих сегментів можна сортувати окремо за допомогою Insertion Sort.

Псевдокод для сортування відра:

void bucketSort(float[] a,int n) { for(each floating integer 'x' in n) { insert x into bucket[n*x]; } for(each bucket) { sort(bucket); } } 

Сортування підрахунку

Сортування підрахунку - це техніка сортування, заснована на клавішах між певним діапазоном. Це працює, підраховуючи кількість об'єктів, що мають різні значення ключів (вид хешування). Потім виконуємо арифметику для обчислення положення кожного об’єкта у вихідній послідовності.

Приклад:

For simplicity, consider the data in the range 0 to 9. Input data: 1, 4, 1, 2, 7, 5, 2 1) Take a count array to store the count of each unique 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 7 The modified count array indicates the position of each object in the output sequence. 3) Output each object from the input 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 place next data 1 at an index 1 smaller than this index. 

Властивості

  • Складність простору: O (K)
  • Найкраща ефективність: O (n + K)
  • Середня продуктивність справи: O (n + K)
  • Найгірший показник: O (n + K)
  • Стабільний: Так (K - кількість різних елементів у масиві)

Реалізація в JavaScript

let numbers = [1, 4, 1, 2, 7, 5, 2]; let count = []; let i, z = 0; let max = Math.max(...numbers); // initialize counter for (i = 0; i <= max; i++) { count[i] = 0; } for (i=0; i < numbers.length; i++) { count[numbers[i]]++; } for (i = 0; i  0) { numbers[z++] = i; } } // output sorted array for (i=0; i < numbers.length; i++) { console.log(numbers[i]); } 

Впровадження C ++

#include  void countSort(int upperBound, int lowerBound, std::vector numbersToSort) //lower and upper bounds of numbers in vector { int range = upperBound - lowerBound; //create a range large enough to get every number between the min and max std::vector counts (range); //initialize of counts of the size of the range std::fill(counts.begin(), counts.end(), 0); //fill vector of zeros for (int i = 0; i < numbersToSort.size(); i++) { int index = numbersToSort[i] - lowerBound; //For example, if 5 is the lower bound and numbersToSort[i] is 5. index will be 0 and the counts[index]+= 1; //count of 5 will be stored in counts[0] } std::cout << counts << std::endl; } 

Швидке впровадження

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

Сортування вставки

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 to size of the input array.

[ 8 3 5 1 4 2 ]

Step 1 :

[ 8 3 5 1 4 2 ]
 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 to the next position and insert `key` to the previous position. Result: [ 3 8 5 1 4 2 ] 

Step 2 :

[ 3 8 5 1 4 2 ]
 key = 5 //2nd index 8 > 5 //move 8 to 2nd index and insert 5 to the 1st index. Result: [ 3 5 8 1 4 2 ] 

Step 3 :

[ 3 5 8 1 4 2 ]
 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 :

[ 1 3 5 8 4 2 ]
 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 :

[ 1 3 4 5 8 2 ]
 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] 
[ 1 2 3 4 5 8 ]

The algorithm shown below is a slightly optimized version to avoid swapping the  key  element in every iteration. Here, the  key  element will be swapped at the end of the iteration (step).

 InsertionSort(arr[]) for j = 1 to arr.length key = arr[j] i = j - 1 while i > 0 and arr[i] > key arr[i+1] = arr[i] i = i - 1 arr[i+1] = key 

Here is a detailed implementation in JavaScript:

function insertion_sort(A) { var len = array_length(A); var i = 1; while (i = 0 && A[j] > x) { A[j + 1] = A[j]; j = j - 1; } A[j+1] = x; i = i + 1; } } 

A quick 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 && array[i] > key){ array[i+1] = array[i] i = i-1 } array[i+1] = key } return array } 

The Java example is shown below:

public int[] insertionSort(int[] arr) for (j = 1; j  0 and arr[i] > key) { arr[i+1] = arr[i] i -= 1 } arr[i+1] = key } return arr; 

And in c....

void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i = 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = 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 sorted
  • Average Case: array is randomly sorted
  • Worst Case: array is reversely sorted.
  • Sorting In Place: Yes
  • Stable: 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 to 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 to the top of the heap and extracting it from the heap and into a sorted array. Thus, after n iterations we will have a sorted version of the input array.

The algorithm is not an in-place algorithm and would require a heap data structure to 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 [O(n) including the space required to store the input data] 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) { //test array Integer[] 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 STABLE public 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[i]; arr[i] = max; heaplength--; arr = maxheapify(arr, 1, heaplength); } return arr; } //Creates maxheap from array public 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[node-1]; arr[node-1] = arr[largest-1]; arr[largest-1] = 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]) largest = l; if (r  arr[largest]) largest = r; if (largest != i) { swap(arr[i], arr[largest]); 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[i]); 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 input 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 to extend 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 the most significant digit of a number, sort input array using countsort algorithm according to ith digit. We used count sort because it is a stable sort.

Example: Assume the input array is:

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

Based on the algorithm, we will sort the input array according to the one's digit (least significant digit).

0: 10

1: 21 11

2:

3: 123

4: 34 44 654

5:

6:

7: 17

8:

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 17

2: 21 123

3: 34

4: 44

5: 654

6:

7:

8:

9:

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

Finally, we sort according to the hundred's digit (most significant digit):

0: 010 011 017 021 034 044

1: 123

2:

3:

4:

5:

6: 654

7:

8:

9:

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

An implementation in C:

void countsort(int arr[],int n,int place){ int i,freq[range]={0}; //range for integers is 10 as digits range from 0-9 int output[n]; 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, and swaps it into place.

Here's how it works:

  1. Find the smallest element in the array and swap it with the first element.
  2. Find the second smallest element and swap with with the second element in the array.
  3. Find the third smallest element and swap wit with the third element in the array.
  4. Repeat the process of finding the next smallest element and swapping it into 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 to notice that the smallest value has already been swapped into 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 implementation of the Selection Sort algorithm. Both implementations are invoked in the  main()  function.

#include  #include  using namespace std; template void print_array(T const(&arr)[n]) { for (size_t i = 0; i < n; i++) std::cout << arr[i] << ' '; cout << "\n"; } int minIndex(int a[], int i, int j) { if (i == j) return i; int k = minIndex(a, i + 1, j); return (a[i] < a[k]) ? i : k; } void recurSelectionSort(int a[], int n, int index = 0) { if (index == n) return; int k = minIndex(a, index, n - 1); if (k != index) swap(a[k], a[index]); recurSelectionSort(a, n, index + 1); } void iterSelectionSort(int a[], int n) { for (int i = 0; i < n; i++) { int min_index = i; int min_element = a[i]; for (int j = i + 1; j < n; j++) { if (a[j] < min_element) { min_element = a[j]; min_index = j; } } swap(a[i], a[min_index]); } } int main() { int recurArr[6] = { 100,35, 500, 9, 67, 20 }; int iterArr[5] = { 25, 0, 500, 56, 98 }; cout << "Recursive Selection Sort" << "\n"; print_array(recurArr); // 100 35 500 9 67 20 recurSelectionSort(recurArr, 6); print_array(recurArr); // 9 20 35 67 100 500 cout << "Iterative Selection Sort" << "\n"; print_array(iterArr); // 25 0 500 56 98 iterSelectionSort(iterArr, 5); print_array(iterArr); // 0 25 56 98 500 } 

Implementation in JavaScript

function selection_sort(A) { var len = A.length; for (var i = 0; i < len - 1; i = i + 1) { var j_min = i; for (var j = i + 1; j < len; j = j + 1) { if (A[j] < A[j_min]) { j_min = j; } else {} } if (j_min !== i) { swap(A, i, j_min); } else {} } } function swap(A, x, y) { var temp = A[x]; A[x] = A[y]; A[y] = temp; } 

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[j] < arr[min_i]: min_i = j arr[i], arr[min_i] = arr[min_i], arr[i] 

Implementation in Java

public void selectionsort(int array[]) { int n = array.length; //method to find length of array for (int i = 0; i < n-1; i++) { int index = i; int min = array[i]; // taking the min element as ith element of array for (int j = i+1; j < n; j++) { if (array[j] < array[index]) { index = j; min = array[j]; } } int t = array[index]; //Interchange the places of the elements array[index] = array[i]; array[i] = t; } } 

Implementation in MATLAB

function [sorted] = selectionSort(unsorted) len = length(unsorted); for i = 1:1:len minInd = i; for j = i+1:1:len if unsorted(j) < unsorted(minInd) minInd = j; end end unsorted([i minInd]) = unsorted([minInd i]); end sorted = unsorted; end 

Properties

  • Space Complexity:  O(n)
  • Time Complexity:  O(n2)
  • Sorting in Place:  Yes
  • Stable:  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 to bubble up to the top. The algorithm traverses a list 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 to other sorting algorithms like quicksort. The upside is that it is one of the easiest sorting algorithms to understand and 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 and 2. It swaps them because 2 < 4: [2, 4, 6, 3, 9]
  • It compares the next two values, 4 and 6. As 4 < 6, these are already in order, and the algorithm moves on: [2, 4, 6, 3, 9]
  • The next two values are also swapped because 3 < 6: [2, 4, 3, 6, 9]
  • The last two values, 6 and 9, are already in order, so the algorithm does not swap them.

Second pass through the list:

  • 2 < 4, so there is no need to swap positions: [2, 4, 3, 6, 9]
  • The algorithm swaps the next two values because 3 < 4: [2, 3, 4, 6, 9]
  • No swap as 4 < 6: [2, 3, 4, 6, 9]
  • Again, 6 < 9, so no swap occurs: [2, 3, 4, 6, 9]

The list is already sorted, but the bubble sort algorithm doesn't realize this. Rather, it needs to complete an entire pass through the list without swapping any values to 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 to wrap your head around and implement yourself.

Properties

  • Space 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 < arr.length; i++) { if(arr[i] < arr[i-1]) { let temp = arr[i]; arr[i] = arr[i-1]; arr[i-1] = temp; sorted = false; } } } 

Example in Java.

public class BubbleSort { static void sort(int[] arr) { int n = arr.length; int temp = 0; for(int i=0; i < n; i++){ for(int x=1; x  arr[x]){ temp = arr[x-1]; arr[x-1] = arr[x]; arr[x] = temp; } } } } public static void main(String[] args) { for(int i=0; i < 15; i++){ int arr[i] = (int)(Math.random() * 100 + 1); } System.out.println("array before sorting\n"); for(int i=0; i < arr.length; i++){ System.out.print(arr[i] + " "); } bubbleSort(arr); System.out.println("\n array after sorting\n"); for(int i=0; i < arr.length; i++){ System.out.print(arr[i] + " "); } } } 

Example in C++

// Recursive Implementation void bubblesort(int arr[], int n) { if(n==1) //Initial Case return; bool swap_flag = false; for(int i=0;iarr[i+1]) { int temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=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: [Int]) -> [Int] { guard inputArray.count > 1 else { return inputArray } // make sure our input array has more than 1 element var numbers = inputArray // function arguments are constant by default in Swift, so we make a copy for i in 0..<(numbers.count - 1) { for j in 0..<(numbers.count - i - 1) { if numbers[j]> numbers[j + 1] { 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[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j] print(arr) 

Example in PHP

function bubble_sort($arr) { $size = count($arr)-1; for ($i=0; $i<$size; $i++) { for ($j=0; $j<$size-$i; $j++) { $k = $j+1; if ($arr[$k] < $arr[$j]) { // Swap elements at indices: $j, $k list($arr[$j], $arr[$k]) = array($arr[$k], $arr[$j]); } } } return $arr;// return the sorted array } $arr = array(1,3,2,8,5,7,4,0); print("Before sorting"); print_r($arr); $arr = bubble_sort($arr); print("After sorting by using bubble sort"); print_r($arr); 

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 < 10; i++) { printf("%d", arr[i]); } return 0; } int BubbleSort(int array[], n) { for (int i = 0 ; i < n - 1; i++) { for (int j = 0 ; j  array[j+1]) // For decreasing order use { int swap = array[j]; array[j] = array[j+1]; array[j+1] = swap; } } } } 

Quick Sort

Quick sort is an efficient divide and conquer sorting algorithm. Average case time complexity of Quick 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 into two sub arrays.

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

On the other hand, if the algorithm, which selects of pivot element of the input arrays, consistently outputs 2 sub arrays with a large difference in terms of array sizes, quick sort algorithm can achieve the worst case time complexity of O(n^2).

The steps involved in Quick Sort are:

  • Choose an element to serve 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.
  • Call Quicksort recursively, taking into account the previous pivot to properly subdivide the left and 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 event that the value at arr[0] is greater than arr[pivot] // Succeeding comments will expound upon the above comment let i = start - 1, j = start; // Increment j up to the index preceding the pivot while (j  arr[pivot]) { j++; } // When the value at arr[j] is less than the pivot: // increment i (arr[i] will be a value greater than arr[pivot]) and swap the value at arr[i] and arr[j] else { i++; swap(arr, j, i); j++; } } //The value at arr[i + 1] will be greater than the value of arr[pivot] swap(arr, i + 1, pivot); //You return i + 1, as the values to the left of it are less than arr[i+1], and values to the right are greater than arr[i + 1] // 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[firstIndex]; arr[firstIndex] = arr[secondIndex]; arr[secondIndex] = 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[high]; int i = (low - 1); for (int j = low; j <= high- 1; j++) { if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } void printArray(int arr[], int size) { int i; for (i=0; i < size; i++) printf("%d ", arr[i]); printf("n"); } int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr)/sizeof(arr[0]); quickSort(arr, 0, n-1); printf("Sorted array: n"); printArray(arr, n); return 0; } 

Implementation in Python3

import random z=[random.randint(0,100) for i in range(0,20)] def quicksort(z): if(len(z)>1): piv=int(len(z)/2) val=z[piv] lft=[i for i in z if ival] 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 [unsorted] = quicksort(unsorted, low, high) if low < high [pInd, unsorted] = partition(unsorted, low, high); unsorted = quicksort(unsorted, low, pInd-1); unsorted = quicksort(unsorted, pInd+1, high); end end function [pInd, unsorted] = partition(unsorted, low, high) i = low-1; for j = low:1:high-1 if unsorted(j) <= unsorted(high) i = i+1; unsorted([i,j]) = unsorted([j,i]); end end unsorted([i+1,high]) = unsorted([high,i+1]); pInd = i+1; end 

The space complexity of quick sort is  O(n) . This is an improvement over other divide and 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, and quicksort is usually done in-place with O(log(n)) stack 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 blend of Insertion Sort and Mergesort. This algorithm is implemented in Java’s Arrays.sort() as well as Python’s sorted() and sort(). The smaller parts are sorted using Insertion Sort and are later merged together using Mergesort.

A quick implementation in Python:

def binary_search(the_array, item, start, end): if start == end: if the_array[start] > item: return start else: return start + 1 if start > end: return start mid = round((start + end)/ 2) if the_array[mid]  item: return binary_search(the_array, item, start, mid - 1) else: return mid """ Insertion sort that timsort uses if the array size is small or if the size of the "run" is small """ def insertion_sort(the_array): l = len(the_array) for index in range(1, l): value = the_array[index] pos = binary_search(the_array, value, 0, index - 1) the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:] return the_array def merge(left, right): """Takes two sorted lists and returns a single sorted list 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] < right[0]: return [left[0]] + merge(left[1:], right) return [right[0]] + merge(left, right[1:]) def timsort(the_array): runs, sorted_runs = [], [] length = len(the_array) new_run = [the_array[0]] # for every i in the range of 1 to length of array for i in range(1, length): # if i is at the end of the list if i == length - 1: new_run.append(the_array[i]) runs.append(new_run) break # if the i'th element of the array is less than the one before it if the_array[i] < the_array[i-1]: # if new_run is set to None (NULL) if not new_run: runs.append([the_array[i]]) new_run.append(the_array[i]) else: runs.append(new_run) new_run = [] # else if its equal to or more than else: new_run.append(the_array[i]) # for every item in runs, append it using insertion sort for item in runs: sorted_runs.append(insertion_sort(item)) # for every run in sorted_runs, merge them sorted_array = [] for run in sorted_runs: sorted_array = merge(sorted_array, run) print(sorted_array) timsort([2, 3, 1, 5, 6, 7]) 

Complexity:

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

Merge Sort

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The major portion of the algorithm is given two sorted arrays, and we have to merge them into a single sorted array. The whole process of sorting an array of N integers can be summarized into 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 and 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 into two parts at every step and we have some linear amount of work that we have to do 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) to 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 understand how merge sort works with the help of a diagram.

Original text


  • Initially we have an array of 6 unsorted integers Arr(5, 8, 3, 9, 1, 2)
  • We split the array into two halves Arr1 = (5, 8, 3) and Arr2 = (9, 1, 2).
  • Again, we divide them into two halves: Arr3 = (5, 8) and Arr4 = (3) and Arr5 = (9, 1) and 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 mentioned before.
  • Sorting In Place: No in a typical implementation
  • Stable: Yes
  • Parallelizable :yes (Several parallel variants are discussed in the third edition of Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms.)

C++ Implementation

void merge(int array[], int left, int mid, int right) { int i, j, k; // Size of left sublist int size_left = mid - left + 1; // Size of right sublist int size_right = right - mid; /* create temp arrays */ int Left[size_left], Right[size_right]; /* Copy data to temp arrays L[] and R[] */ for(i = 0; i < size_left; i++) { Left[i] = array[left+i]; } for(j = 0; j < size_right; j++) { Right[j] = array[mid+1+j]; } // Merge the temp arrays back into arr[left..right] i = 0; // Initial index of left subarray j = 0; // Initial index of right subarray k = left; // Initial index of merged subarray while (i < size_left && j < size_right) { if (Left[i] <= Right[j]) { array[k] = Left[i]; i++; } else { array[k] = Right[j]; j++; } k++; } // Copy the remaining elements of Left[] while (i < size_left) { array[k] = Left[i]; i++; k++; } // Copy the rest elements of R[] while (j < size_right) { array[k] = Right[j]; j++; k++; } } void mergeSort(int array[], int left, int right) { if(left < right) { int mid = (left+right)/2; // Sort first and second halves mergeSort(array, left, mid); mergeSort(array, mid+1, right); // Finally merge them merge(array, left, mid, right); } }

JavaScript Implementation

function mergeSort (arr) { if (arr.length < 2) return arr; var mid = Math.floor(arr.length /2); var subLeft = mergeSort(arr.slice(0,mid)); var subRight = mergeSort(arr.slice(mid)); return merge(subLeft, subRight); }

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 and divide the array into two halves. We will now sort both of the halves with recursive calls to MergeSort function.

function merge (a,b) { var result = []; while (a.length >0 && b.length >0) result.push(a[0] < b[0]? a.shift() : b.shift()); return result.concat(a.length? a : b); }

When we merge the two halfs, we store the result in an auxilliary array. We will compare the starting element of left array to the starting element of right array. Whichever is lesser will be pushed into the results array and we will remove it from there respective arrays using [shift() operator. If we still end up with values in either of left or right array, we would simply concatenate it in the end of the result. Here is the sorted result:

var test = [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 video that walks through the topic in detail.

Implementaion in JS

const list = [23, 4, 42, 15, 16, 8, 3] const mergeSort = (list) =>{ if(list.length  { var result = []; while(left.length || right.length) { if(left.length && right.length) { if(left[0] < right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } else if(left.length) { result.push(left.shift()) } else { result.push(right.shift()) } } return result; } console.log(mergeSort(list)) // [ 3, 4, 8, 15, 16, 23, 42 ] 

Implementation in C

#include #include void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1+ j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l+(r-l)/2; mergeSort(arr, l, m); mergeSort(arr, m+1, r); merge(arr, l, m, r); } } void printArray(int A[], int size) { int i; for (i=0; i < size; i++) printf("%d ", A[i]); printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int arr_size = sizeof(arr)/sizeof(arr[0]); printf("Given array is \n"); printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); printf("\nSorted array is \n"); printArray(arr, arr_size); return 0; 

Implementation in C++

Let us consider array A = {2,5,7,8,9,12,13} and array B = {3,5,6,9,15} and we want array C to 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,0 while (i < len(left) and j < len(right)): if compare(left[i],right[j]): result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 while (i < len(left)): result.append(left[i]) i += 1 while (j < len(right)): result.append(right[j]) j += 1 return result def merge_sort(arr, compare = lambda x, y: x < y): #Used lambda function to sort array in both(increasing and decresing) order. #By default it sorts array in increasing order if len(arr) < 2: return arr[:] else: middle = len(arr) // 2 left = merge_sort(arr[:middle], compare) right = merge_sort(arr[middle:], compare) return merge(left, right, compare) arr = [2,1,4,5,3] print(merge_sort(arr)) 

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[lo]; 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[m+n]; while(i

Example 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[lo]; 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[m + n]; while (i < n && j < m) { if (arr1[i] < arr2[j]) { arr3[k] = arr1[i]; i++; } else { arr3[k] = arr2[j]; j++; } k++; } while (i < n) { arr3[k] = arr1[i]; i++; k++; } while (j < m) { arr3[k] = arr2[j]; j++; k++; } return arr3; } public static void main(String[] args) { int arr[] = {2, 9, 8, 3, 6, 4, 10, 7}; int[] so = mergesort(arr, 0, arr.length - 1); for (int i = 0; i < arr.length; i++) System.out.print(so[i] + " "); } }