How would you sort an array or list using a sorting algorithm?

Najwa

How would you approach sorting an array or list using different sorting algorithms, such as bubble sort and quicksort? Can you explain the step-by-step process of each algorithm, discuss their time complexities, and describe scenarios where one might be more suitable than the other?

David_Seidman

I’ll assume here that you are trying to sort data stored in the nodes of a linked list and that moving that data wholesale in and out of the list is not an option. (Even so, you could either swap the data within the nodes while sorting or swap the metadata/pointers ordering the nodes; perhaps you intend the latter?)

With that assumption, HeapSort is out of the picture: It assumes O(1) random access into the heap.

QuickSort is rarely mentioned as an option for sorting list nodes, but it can actually be made to work with doubly-linked lists. For sufficiently large lists this might well be the most efficient approach on average. But as you likely know, QuickSort has excellent performance characteristics on average but terrible ones in the worst cases. (Originally, I mentioned here that it doesn’t work for singly-linked lists, but as Jerry Coffin mentions in the comments, that’s not correct: If you give up the “start from both ends strategy” in the textbook implementations, you can also implement QuickSort on singly-linked lists, and it doesn’t even add real complexity.)

InsertionSort is often the basis for the fastest sorts of short lists (less than 100 elements, for example, but the cut-off is highly application-dependent). It is terrible for larger datasets, however, unless they’re already mostly sorted. One reasonable application of InsertionSort is to sort the lead partitions in the QuickSort algorithm; I.e., instead of partitioning all the way down to partitions of size 1, you go down to some size N after which InsertionSort is more likely to do better. (InsertionSort works with singly-linked lists.)

MergeSort works with singly-linked lists and is fairly straightforward. It’s worst-case behavior is not bad. Here too, it can be useful to use InsertionSort to start the process.

The thing to remember though, is that algorithm behavior in practice depends on the realities of your data and machinery. So if the performance is truly important, experimentation (including careful benchmarking) will be needed.

Michael_Charton

We can think of linked list like an array too.. The only difference is that linked list use pointer(in case we use c++) to connect different nodes by next pointer.
In Insertion sort we divide our array into two part . Sorted and Unsorted.
in worst case we have go through every element in sorted array to put our current array element . Basically its the case when the array is sorted and then reverse . Eg - 5 4 3 2 1
Insertion Sort
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr;
j = i - 1;
/* Move elements of arr[0..i-1], that are greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
If everything is sorted then the tc will be O(N) * O(1) = O(N).
So the time complexity will be still O(N) in case of sorted array. We call its as the best case and in worst case the time complexity will still be O(N²)...

Maida_Shahid

Best Case:

Selection sort: The best-case complexity is O(N2) as to find the minimum element at every iteration, we will have to traverse the entire unsorted array.
Bubble sort: The best-case complexity is O(N). It happens when we have an already sorted array, as in that case, we will stop the procedure after a single pass.
Insertion sort: The best-case complexity is O(N). It occurs when we have a sorted array; as in that case, each element has already been placed at its correct position, and no swap operation will be required.
Worst Case:

Selection sort: The worst-case complexity is O(N2) as to find the minimum element at every iteration, we will have to traverse the entire unsorted array.
Bubble sort: The worst-case complexity is O(N2). It happens when we have a reverse sorted array, as in that case, we will have to make all the passes.
Insertion sort: The worst-case complexity is O(N2). It occurs when we have a reverse sorted array, as in that case, to find the correct position for any element, we will have to fully traverse the sorted array each time.
Average Case:

For random datasets, all three algorithms take O(N2) time complexity. The expected (also average) number of inversions in a randomly generated dataset of size N having distinct elements is N * (N - 1) / 4.

In bubble sort and insertion sort, we swap adjacent elements, which reduces the inversion count by 1, and in one iteration, we can make a maximum of N - 1 adjacent swap. So to make the inversion count zero, we have to do more than one iteration (around N/4 iterations), and hence the complexity becomes O(N2).
In selection sort, we make just 1 swap (which is not adjacent) and place an element at its correct place. This can reduce the inversion count by N-1, but to find that element, we have to traverse the entire unsorted array, which happens multiple times making up for O(N2) complexity.
Space Complexity

It is O(1) for all three algorithms as we don’t need to take any extra space to sort them, thus making them in-place algorithms.
Stability

Bubble sort and insertion sort are stable, whereas selection sort isn’t.
The selection sort can be made stable by incorporating the indices of equal elements when comparing and sorting them. But then the space complexity increases from O(1) to O(N), where N is the size of the array.
When swapping elements, we also swap their indices which are stored in another array. When finding the appropriate element to replace the current element, we consider lesser elements (assuming we have to sort in ascending order) and elements having equal values with lesser indices.
What They Work Well On

Selection sort works similarly on all kinds of dataset
Both, Bubble sort and Insertion sort, are adaptive which means they perform a lesser number of operations if a partially sorted array is provided as input
Applications

Selection sort can be used to sort a linked list as we can efficiently remove the smallest element and append it in the sorted list.
Bubble sort can detect minor errors in a sorted dataset and sort an almost sorted dataset quickly.
Insertion sort is used to sort online data — it can start the sorting process even if the complete data set isn’t available.
Advantages

Selection sort is efficient where swapping operation is costly as it makes a maximum of N swaps for an array of size N.
Bubble sort is the simplest stable in-place sorting algorithm and very easy to code.
Insertion sort makes fewer comparisons compared to the other two algorithms and hence is efficient where comparison operation is costly.
Disadvantages

All three algorithms have a quadratic worst-case time complexity and hence work slowly on large datasets.
Bubble sort makes many comparisons and swaps and thus is not efficient if swapping or comparison is a costly operation.
Insertion sort makes a lot of swaps and thus becomes inefficient if swapping operations are costly.

Arun_Mishra

Each of the sorting algorithms has its advantages and disadvantages. Here are a few of them:

Insertion sort:
(+) fastest for small inputs
(-) quadratic for most large inputs
Quick Sort:
(+) fast for most inputs
(+) cache-friendly
(-) the simplest version has a quadratic worst case
(-) the guaranteed-n-log n version has a much worse performance in practice
(-) the randomized version is only O(n log n) with high probability, not certainly
Heap Sort:
(+) guaranteed O(n log n)
(+) works in place, i.e., with O(1) extra memory
(-) almost always runs in Theta(n log n), even if the input is sorted
(-) worse practical performance than Quick Sort
Luckily, in practice nobody forces you to choose one of these three. Many standard libraries nowadays implement Intro Sort as their default sorting algorithm. This happens to be a combination of these three algorithms:
Start with Quick Sort.
In each branch that happens to be too deep (e.g., deeper than 2 lg n), switch to Heap Sort.
In each branch that happens to be short enough, finish the sorting by running Insert Sort.
This way, Intro Sort is usually fast in practice, and at the same time it gives you the guaranteed O(n log n) worst-case performance.

Ashely_Lobo

An algorithm is a set of steps used to solve a problem. In computer programming, algorithms are used to solve problems. Furthermore, sorting is an important operation on a set of data. A data set can be sorted using a variety of algorithms. Two simple sorting algorithms are insertion sort and selection sort.
Both insertion sort and selection sort have an outer loop (that goes around every index) and an inner loop (over a subset of indices). Each pass of the inner loop adds one element to the sorted region at the expense of the unsorted region until it runs out of unsorted elements.
The inner loop is what makes the difference:
The inner loop in selection sort is over the unsorted elements. Each pass selects and moves one element to its final location (at the current end of the sorted region).
Each pass of the inner loop iterates over the sorted elements in insertion sort. Sorted elements are displaced until the loop locates the proper location to insert the next unsorted element.
In a selection sort, sorted elements are found in output order and remain in place once found. In contrast, unsorted elements remain in place in an insertion sort until consumed in input order, whereas sorted elements are constantly moved around.
In terms of swapping, the selection sort performs one swap per inner loop pass. Insertion sort typically saves the element to be inserted as a temp before the inner loop, allowing the inner loop to shift sorted elements up by one before copying temp to the insertion point.
The distinction between Insertion Sort and Selection Sort-
Definition
Insertion sort is a simple sorting algorithm that constructs the final sorted list one element at a time. Selection sort, on the other hand, is a simple sorting algorithm that searches the remaining items repeatedly for the smallest element and moves it to the correct location. This is the primary distinction between insertion sort and selection sort.
Functionality
Insertion sort adds an element to the partially sorted array one at a time, whereas selection sort finds the smallest element and moves it accordingly.
Efficiency
Another distinction between insertion sort and selection sort is that insertion sort is more efficient.
Complexity
There is also a difference in complexity between insertion sort and selection sort. Insertion sort is more difficult to understand than selection sort.
Conclusion
Sorting algorithms include insertion sort and selection sort. Both are appropriate for sorting a small dataset. The primary distinction between insertion sort and selection sort is that insertion sort sorts by exchanging one element at a time with the partially sorted array, whereas selection sort sorts by selecting the smallest element from the remaining elements and exchanging it with the element in the correct location.

Andrew_John

In layman's terms:

In case of bubble sort, all adjacent elements compare to check which one is greater(or smaller), and then arrange accordingly.

Let's take an example:

We've an array 9,6,4,7 and we want to sort it in ascending order.

First we compare 9,6 to see which one is larger, and swap the larger element on the right, i.e. the array now becomes 6,9,4,7.

Next we compare 9 and 4, and on similar lines(as above), the array becomes 6,4,9,7.

Now finally, we compare 9 and 7, and the array after one full iteration becomes 6,4,7,9.

Now, if you observe carefully, the largest element automatically reached on the rightmost position. We now have one element in place (the last one), and now we repeat the iteration with first n-1 elements (n being the total number of elements).

We repeat the iteration till the size of the array to be iterated is 1, or the array is sorted.

Insertion Sort, on the contrary makes us assume that we've two arrays, one is sorted and the other one is unsorted.

The sorted array is initially empty.

Again, let's see with an example:

Unsorted Array:6,9,4,7

Sorted Array:

Now, we iterate over the elements of unsorted array, and place them accordingly in the sorted array, in a sorted manner.

Element scanned: 6

Since the sorted array is empty, we simply put 6 in it.

Unsorted Array:9,4,7

Sorted Array:6

Element scanned 9

Since 9>6, we put it on the top of sorted array.

Unsorted array:4,7

Sorted Array: 6,9

Element scanned: 4

Clearly, 4 is less than 9 and 6, so we put it in the first place in the sorted array:

Unsorted array: 7

Sorted Array: 4,6,9

On scanning the last element, we get:

Unsorted array:

Sorted Array: 4,6,7, 9