Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems
Complexity
Worst-case time complexity :
Average time complexity :
Best-case time complexity :
Worst-case space complexity :
O(n2)
O(n2)
O(n)
O(1)
Insertion Sort
Insertion Sort is a simple sorting algorithm that iterates through an array and at each iteration it removes one element from the array, finds the location it belongs to in the sorted list and inserts it there, repeating until no elements remain in the unsorted list. It is an in-place, stable sorting algorithm that is inefficient on large input arrays but works well for data sets that are almost sorted. It is more efficient in practice compared to other quadratic sorting algorithms like bubble sort and selection sort.
Complexity
Worst-case time complexity :
Average time complexity :
Best-case time complexity :
Worst-case space complexity :
O(n2)
O(n2)
O(n)
O(1)
Selection Sort
Selection Sort is an in-place comparison sorting algorithm that divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
Complexity
Worst-case time complexity :
Average time complexity :
Best-case time complexity :
Worst-case space complexity :
O(n2)
O(n2)
O(n2)
O(1)
Merge Sort
Merge Sort is an efficient, stable sorting algorith that makes use of the divide and conquer strategy. Conceptually the algorithm works as follows:
- Divide the unsorted list into n sublists, each containing one element(a list of one element is considered sorted)
- Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
Complexity
Worst-case time complexity :
Average time complexity :
Best-case time complexity :
Worst-case space complexity :
O(n log n)
O(n log n)
O(n log n)
O(n)
Quick Sort
Quick Sort is an efficient, in-place sorting algorith that in practice is faster than MergeSort and HeapSort. However, it is not a stable sorting algorithm, meaning that the relative positioning of equal sort items is not preserved.Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. The steps are:
- Pick an element, called a pivot, from the array. This is usually done at random.
- Move pivot element to the start of the array.
- Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
Complexity
Worst-case time complexity :
Average time complexity :
Best-case time complexity :
Worst-case space complexity :
O(n2)
O(n log n)
O(n log n)
O(log n)