Sorting Problems and algorithms

Quote of the day: An algorithm must be seen to be believed.

 

In Computer Science, we may sometimes deal with large amounts of data where it is crucial to access the data in a particular order due to for example time efficiency. Wherever, these problems occur, you will often find the need to sort your data. In this article, I am going to talk about the sorting problem and mention some sorting algorithms. 

 

What is the sorting problem?

 

You can see the sorting problem as a problem of selecting a permutation that always orders the elements in a certain way. I could not find any definition on the problem so I provided my own definition.

 

There are several problems that arises here:

  • You have the problem of finding the actual algorithm: 
    • How do I find a sorting algorithm?
  • You can have the problem of selecting an efficient sorting algorithm depending on the amount of data you want to sort. And there can be several algorithms to choose from. Here efficiency can mean extra storage or the time it takes to sort the list of data.

 

The problems lead us to consider different sorting algorithms used for various reasons.

 

What is a sorting algorithm?

A sorting algorithm is a step by step procedure such that when you give it a list of items, the output is a list with the same items but sorted based on some criteria.

 

In the problem, we wanted to know how we can sort the items, or find the procedure of reaching the correct permutation (the permutation that gives us an ordered list). This means that a sorting algorithm is a description of what to do in order to reach the permutation we desire.

 

There are many sorting algorithms and they are classified based on different categories. I would like to explore them based on these:

  • General Method: this is how the algorithm transforms the input into the output.
  • Computational complexity:  this is looking at how expensive it will take the algorithm to transform the input to the output depending on the size of the input.

 

There is another classification of sorting algorithm which is comparison vs. non-comparison. I will be only focusing on the comparison-based sorting algorithm and looking at them based on the two classification described above.

 

Among the comparisons algorithms, we have sorting algorithms such as: 



Name

General Method

Worst Case time

Merge Sort

Merging

nlog n

quicksort

Partition

n2

Insertion Sort

Insertion

n2

Bubble Sort

Exchanging

n2

Heapsort

Selection

nlogn


Stay tuned, next article, I will be looking at the Partition general method with the example of the Quicksort algorithm.