# Sorting Algorithms

Understanding sorting algorithms is a must for software engineers. This topic is also common in a programming interview. There is a lot of sorting algorithms out there, and I want to cover some of them here. I also gave some examples in C.

## Selection Sort

Select and compare an element with other elements at each iteration. The complexity of Selection Sort is O(n2).

## Bubble Sort

Select and compare an element with its neighbor then swap if it is not in order. The complexity of Bubble Sort is O(n2).

## Insertion Sort

Similar to Bubble Sort. It inserts the next element into the sorted sublist. The complexity of Insertion Sort is O(n2).

## Shell Sort

Shell Sort partitions the list into sublists where a sublist is elements that are separated by a gap. The gap keeps reducing the value until it becomes one. Each sublist is sorted using Insertion Sort. The complexity of Shell Sort is O(n2).

## Merge Sort

Merge Sort is a Divide and Conquer algorithm. Divide the unsorted list into sublists then repeatedly merge sublists to produce new sorted list. The complexity of Merge Sort is O(n log n).

## Quick Sort

Quick Sort is similar to Merge Sort. It is a Divide and Conquer algorithm. It partitions the list at every step based on a pivot. The complexity of Quick Sort is O(n log n).

## Conclusion

It is also important to understand Big-O notation, to understand the time complexity of an algorithm. Most of them are O(n2). But some recursive sorts such as Merge and Quick Sort have O(n log n). There is still a lot of sorting algorithms that I didn't cover here. But these are the famous ones.

There is a question that asks you to sort in some programming interview. Whatever the sorting algorithm that you choose is up to you. I prefer the Insertion or Merge Sort.

## References

Most of the resources I got are from Wikipedia and GeeksforGeeks.org. I wrote my C codes on repl.it.