PHP 7 Data Structures and Algorithms by Mizanur Rahman

Author:Mizanur Rahman
Language: eng
Format: epub, azw3
Publisher: Packt Publishing
Published: 2017-05-26T06:37:43+00:00

We will keep our discussion limited to the preceding list, as they are the most commonly used sorting algorithms and can be grouped and classified under different criteria such as simple sorting, efficient sorting, distribution sorting, and so on. We will now explore each of the sorting functionalities, their implementations, and complexity analysis, along with their pros and cons. Let's get started with the most commonly used sorting algorithm - bubble sort.

Understanding bubble sort

Bubble sort is the most commonly used sorting algorithm in the programming world. Most of the programmers start learning about sorting with this algorithm. It is a comparison-based sorting algorithm, which is always referred to as one of the most inefficient sorting algorithms. It requires maximum number of comparisons, and the average, and worst case complexity are the same.

In bubble sort, each item of the list is compared with the rest of the items and swapped if required. This continues for each item in the list. We can sort either in ascending or descending order. Here is the pseudo algorithm for bubble sort:

procedure bubbleSort( A : list of sortable items )

n = length(A)

for i = 0 to n inclusive do

for j = 0 to n-1 inclusive do

if A[j] > A[j+1] then

swap( A[j], A[j+1] )

end if

end for

end for

end procedure

As we can see from the preceding pseudocode, we are running one loop to ensure that we iterate each item of the list. The inner loop ensures that, once we point to an item, we are comparing the item with other items in the list. Based on our preference, we can swap the two items. The following image shows a single iteration to sort one item of the list. Let's assume our list has the following items: 20, 45, 93, 67, 10, 97, 52, 88, 33, 92. For the first pass (iteration) to sort out the first item, the following steps will be taken:

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.