Time Complexity for Sorting Algorithms

snehangsude · January 6, 2022, 3:26pm

I was looking into the time taken for each of the sorting functions to be run and I’m quite confused as to why Divide and Conquer or any sorting algorithm is used when the in-built one is miles faster.

In-Built sort

in-built_sort

This is run on 10000 samples. Since I’m new I can only post a single Image. However, if I can attach images to the comments, I will.

If this has been answered or a related topic is answered, please re-direct me.

Sebgolos · January 6, 2022, 4:26pm

Well, the built-in solution uses probably not only even more efficient sorting technique, but also may be multi-threaded or even written in C to speed things up.

The only reason you code them up is to practice coding skills

amitbudhiraja00 · January 16, 2022, 7:19am

Hi guys I would like to tell u all something that by default the complexity of the Insertion sort is O(n^2) [time] . So I have updated it a by putting the concept of binary search to it and
made it O(nlogn)< complexity >O(n^2).

And the code for it is attached below must see
Regards

amitbudhiraja00 · January 19, 2022, 3:25pm

There are also few edge cases for this
I have made the Insertion Sort to the complexity of O(n^2) to O(nlogn)
See below for the final code

github.com

amitbudhiraja573/Data-Structures-and-Algorithms-using-Python-/blob/master/Bubble_and_Insertion_Sort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5bb8f357",
   "metadata": {},
   "source": [
    "# Notebook contents : \n",
    "- Bubble Sort \n",
    "- Insertion Sort \n",
    "- Insertion Sort(Optimized version using Binary Search)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0ebc4f8c",
   "metadata": {},
   "outputs": [],
   "source": []

This file has been truncated. show original

Regards

amitbudhiraja00 · January 23, 2022, 2:24pm

Hi everyone the code of Merge Sort is taking the space complexity of O(n) .
I have optimised the Merge Sort with time complexity : O(nlogn) same . but the space complexity as O(1). By doing the sorting inline in the original list/arr.
So in this way it is more reliable to use when working with huge lists.
Providing the GitHub link for the code
Regards

github.com

amitbudhiraja573/Data-Structures-and-Algorithms-using-Python-/blob/master/Merge_and_Quick_sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d3384f56",
   "metadata": {},
   "source": [
    "# Notbook Contents\n",
    "- Merge Sort\n",
    "- Quick Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e3598c1",
   "metadata": {},
   "source": [
    "__Creating different Test Cases for Sorting__"
   ]
  },

This file has been truncated. show original

snehangsude · January 29, 2022, 8:47am

This is nice! I see you have mentioned on Hoare Partitioning. Could you share more on that? Thanks in advance!