When we organise and work with data, we eventually want to search for some specific record within the collection or sort the collection for presentation for easy and faster access. Searching and sorting are the most common applications found in computer science.

In this lesson, we will explore some important topics and look at some of the basic algorithms for use with sequence programming. The searching problem will be discussed many times as it can be applied to collections stored using many different data structures, not just sequences.

Sorting

Sorting is the technique of arranging or ordering a collection of items such that each item and its successor satisfy a prescribed rule. The items can be simple values, such as integers and reals, or more complex types, such as student records or dictionary entries.

Ordering can be done on the basis of integer value, alphabetical order, date of creation, or any other comparison parameter.

We face the enormous requirement of sorting in everyday life. Consider the listings of a phone directory, the keys in a dictionary, or the terms in an index, all of which are organized in alphabetical order to make finding an entry much easier.

Bubble Sort

A simple solution to the sorting problem is the bubble sort algorithm, which rearranges the values by iterating over the list multiple times causing larger values to bubble to the top or end of the list.

It is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Example:

First Pass:

( 6 1 4 2 8 ) –> ( 1 6 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 6 > 1.

( 1 6 4 2 8 ) –>  ( 1 4 6 2 8 ), Swap since 6 > 4

( 1 4 6 2 8 ) –>  ( 1 4 2 6 8 ), Swap since 6 > 2

( 1 4 2 6 8 ) –> ( 1 4 2 6 8 ), Now, since these elements are already in order (8 > 6), algorithm does not swap them.

Second Pass:

( 1 4 2 6 8 ) –> ( 1 4 2 6 8 )

( 1 4 2 6 8 ) –> ( 1 2 4 6 8 ), Swap since 4 > 2

( 1 2 4 6 8 ) –> ( 1 2 4 6 8 )

( 1 2 4 6 8 ) –>  ( 1 2 4 6 8 )

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 1 2 4 6 8 ) –> ( 1 2 4 6 8 )

( 1 2 4 6 8 ) –> ( 1 2 4 6 8 )

( 1 2 4 6 8 ) –> ( 1 2 4 6 8 )

( 1 2 4 6 8 ) –> ( 1 2 4 6 8 )

Implementation of Bubble Sort

# Python program for implementation of Bubble Sort 
def bubbleSort(arr):
   n = len(arr)

   # Traverse through all array elements
   for i in range(n):

       # Last i elements are already in place
       for j in range(0, n-i-1):

           # traverse the array from 0 to n-i-1
           # Swap if the element found is greater
           # than the next element
           if arr[j] > arr[j+1] :
               arr[j], arr[j+1] = arr[j+1], arr[j]

# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print ("Sorted array is:")
for i in range(len(arr)):
   print ("%d" %arr[i]),

Bubble sort is considered one of the most inefficient sorting algorithms due to the total number of swaps required. Given an array of keys in reverse order, a swap is performed for every iteration of the inner loop, which can be costly in practice.

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.

2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

The following example explains the above steps:

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

Implementation of Selection Sort

# Python program for implementation of Selection
# Sort
import sys
A = [64, 25, 12, 22, 11]

# Traverse through all array elements
for i in range(len(A)):
    
   # Find the minimum element in remaining
   # unsorted array
   min_idx = i
   for j in range(i+1, len(A)):
       if A[min_idx] > A[j]:
           min_idx = j
            
   # Swap the found minimum element with
   # the first element     
   A[i], A[min_idx] = A[min_idx], A[i]

# Driver code to test above
print ("Sorted array")
for i in range(len(A)):
   print("%d" %A[i]),

The selection sort, which makes n − 1 passes over the array to reposition n − 1 values, is also O(n2). The difference between the selection and bubble sorts is that the selection sort reduces the number of swaps required to sort the list to O(n ).

Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

Let us consider an example:

12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 5 (Size of input array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12

11, 12, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13

11, 12, 13, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.

5, 11, 12, 13, 6

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.

5, 6, 11, 12, 13

Now, let us try to implement this using a sample snippet:

# Python program for implementation of Insertion Sort

# Function to do insertion sort
def insertionSort(arr):

   # Traverse through 1 to len(arr)
   for i in range(1, len(arr)):

       key = arr[i]

       # Move elements of arr[0..i-1], that are
       # greater than key, to one position ahead
       # of their current position
       j = i-1
       while j >=0 and key < arr[j] :
               arr[j+1] = arr[j]
               j -= 1
       arr[j+1] = key


# Driver code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
   print ("%d" %arr[i])

The insertion sort is an example of a sorting algorithm in which the best and worst cases are different. Determining the different cases and the corresponding run times is left as an exercise.