Simple Explanation of Algorithmic Design and Data Structures

 Searching algorithms perform the function of comparing two values and a desired value in order to find the position of the desired value.  The two main algorithms that perform this task is linear search and binary search.  Linear search is the most basic of searches, checking each item until the desired item is located (Rajinikanth, B 2022).  When using linear search on average it will take searching half the list to find the position of the desired item. 

Binary search is a lot more efficient than linear search.  It relies on elements of the list being sorted already, then smaller sub lists are searched.  It starts with the entire list and checks the middle element, halving the list each time.  Then the item is found the search stops.

There is a long list of different sorting algorithms, selection sort, merge sort, bubble sort, quick sort, and shell sort, and insertion sort to name a few.  in order to complete selection sort the algorithm is finding minimum to maximum elements and sorting them into the correct position (Kumar, Deepak 2022).

Merge sort repeatedly merges sorted sub sections starting with selections of a single item.  Merge sort requires less operations than selection sort (Jaisingh, Anand 2022).

Bubble sort compares two adjacent elements and if the first element is greater than the second they swap places.  This continues through the list as many times as it takes to get the elements into the correct position (Jaisingh, A 2022).

Quick sort reduces the space complexity by picking a partition and separating lesser elements and greater elements and sorting the two halves (Jaisingh, A 2022).

Shell sort is an optimized version of insertion, by allowing sorting elements that are farther apart it can move elements into position faster than sorting the nearest neighbor elements (Codeahoy.com 2022).

Insertion sort is an algorithm that splits input into two parts, a sorted part and unsorted part.  The algorithm inserts the next value from the unsorted part into the correct location in the sorted part.  The typical run time for this algorithm is calculated as an O notation.

Complexity analysis of data structures analyzes the efficiency of the algorithm which is broken up into two parts as well, time complexity and space complexity.  This makes it easier to determine the efficiency of the algorithm with measuring the time it takes for an algorithm to run and also how much space the algorithm takes up on a system.

Space complexity matters a lot in real world applications because physical memory is limited to the systems that they are intended to run on.  Application developers do not want to build an application that uses functions that exceed the amount of space that systems have.  Time is also important because if a an application is taking up too much time it can slow down the system.  So even with modern computers and operating systems that are running faster than ever it is still important to take time/space complexity in account with choosing between sorting and searching algorithms (Bekgrave, A, 2019).

 

References:

Belgrave, Alejandro.  (Oct 9, 2019).  Understanding Time and Space Complexity.  https://medium.com/@whosale/understanding-time-and-space-complexity-f94b3140541b

Code Ahoy.  (Sourced November 26, 2022).  Shell Sort.  codeahoy.com/learn/sortingalgorithmsa/shellsort/

Jaisingh, A.  (Sourced November 26, 2022).  Sorting Algorithms Tutorial.  https://www.hackearth.com/practice/algorithms/sorting/quick-sort/tutorial/

Kumar, Deepak.  (Sourced November 26,2022).  Selections Sort Algorithm.  interviewkickstart.com/learn/selection-sort

Rajinikanth, B.  (Sourced November 26, 2022).  Linear Search Algorithm.  btechsmartclass.com/data_structures/linear-search.html

 

 

 

Comments

Post a Comment

Popular posts from this blog

Operating System Theory and Design

Image
      The fundamental goal of computers is to execute programs so that users can solve problems faster and easier (Silberschatz, 2014).  The operating system is the one program that is constantly running on a computer.  This is because the opeating system creates a pathway or space where other programs can be useful.  Operating systems such as Mac, Windows, and even Android for smartphones allow computers and smart phones to boot up and be useful.  Without an operating system using a computer is very difficult because th operating system is what allows hardware and applications to communicate and run programs.  The major function of the operating system is to continually run in the background so that harware and applications can be accessed and used by the user.  The operating system is a link between the memory and storage and assists with opening and using application that have been saved in the storage. Describing the process is simple, it is the act of a program in execution, the p
Read more

PING goes the Traceroute

When learning about how internet connections are made and the simple act of a google search sends out a message requesting information.  One can perform a PING command or Traceroute command.  I tested these commands on some websites and this is what my results were below. First off the acronym PING is Packet Internet Groper.  This is command is used to test whether an IP address or domain is working correctly.  How this is done is the Ping command measures how long it takes for packets to be sent to the destination IP address and back.  This is measures in milliseconds.  When performing the Ping command on google.com multiple packets were sent out, the ping command is still going, the average response time is 22.746 ms.  It times out for a brief period and then continues on.  The next domain was Japan.go.jp which is a japanese government website, the average time was 15.944 ms.  The last domain was Abs.gov.au which is the Australian Bureau of Statistics website, and the average time 42
Read more