Sorting Algorithms

By Dr. Zakaria Alqattan

 Sorting:

Sorting : is a process that organizes a collection of data into either ascending or

descending order.
There are many sorting algorithms, such as:
– Selection Sort
– Insertion Sort
– Bubble Sort
– Merge Sort
– Quick Sort
 Sorting algorithms
In terms of time complexity
• Quadratic Sorting--O(n2) in worst case
• Selection Sort
• Insertion Sort
• Bubble Sort
• Faster Sorting--O(nlogn) in general
• Merge Sort
• Quick Sort
 The Selection sort Algorithm
• Start by finding the smallest entry.
• Swap the smallest entry with the first entry.
• The list is divided into two sublists, sorted and unsorted, which are
divided by an imaginary wall.
• We find the smallest element from the unsorted sublist and swap it with
the element at the beginning of the unsorted sublist.
• After each selection and swapping, the imaginary wall between the two
sublists move one element ahead, increasing the number of sorted
elements and decreasing the number of unsorted ones.
• Each time we move one element from the unsorted sublist to the sorted
sublist, we say that we have completed a sort pass.
• A list of n elements requires n-1 passes to completely rearrange the
data.
 The Selection sort Algorithm
def selectionSort(elemType a[], int count) def swap(lhs, rhs)
{
Loop (for i < count – 1) tmp = lhs;
// Find the smallest in unsorted portion lhs = rhs;
small  i rhs = tmp;
}
Loop (for index = i + 1 to count – 1)
If (a[index] < a[small] Then
small  index
End If

Swap a[i] and a[small]

...
End Loop
End Loop
 The Insertion sort Algorithm

• Insertion sort is a simple sorting algorithm that is appropriate for

small inputs.
• The list is divided into two parts: sorted and unsorted.
• In each pass, the first element of the unsorted part is picked up,
transferred to the sorted sublist, and inserted at the appropriate
place.
• A list of n elements will take at most n-1 passes to sort the data.
 The Insertion sort Algorithm

• The Insertion sort 70

algorithm also 60
views the array as
50
having a sorted
40
side and an
30
unsorted side.
20
10
0
[0]
[1] [1]
[2] [2]
[3] [3]
[4] [4]
[5] [5]
[6]
 The Insertion sort Algorithm

Sorted side Unsorted side

• The sorted side starts 70
with just the first 60
element, which is not 50
necessarily the
40
smallest element.
30
20
10
0
[0]
[1] [1]
[2] [2]
[3] [3]
[4] [4]
[5] [5]
[6]
 The Insertion sort Algorithm

Sorted side Unsorted side

• The sorted side 70
grows by taking the 60
front element from
50
the unsorted side...
40
30
20
10
0
[1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
 The Insertion sort Algorithm

Sorted side Unsorted side

• ...and inserting it in 70
the place that keeps
60
the sorted side
50
arranged from small
to large. 40
30
20
10
0
[1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
 The Insertion sort Algorithm

Sorted side Unsorted side

• In this example, the 70
new element goes in 60
front of the element 50
that was already in the
40
sorted side.
30
20
10
0
[1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
 The Insertion sort Algorithm

Sorted side Unsorted side

• Sometimes we 70
are lucky and
60
the new
50
inserted item
doesn't need 40
to move at all. 30
20
10
0
[1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
 The Insertion sort Algorithm

Sorted side Unsorted side

• Sometimes we 70
are lucky twice 60
in a row. 50
40
30
20
10
0
[1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
 How to Insert One Element

• Copy the new Sorted side Unsorted side

element to a 70
70 separate
60
60
location.
50
50
40
40
30
30 20
20
10
10 0
0 [1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 How to Insert One Element

• Shift elements
in the sorted 70
70 side, creating
60
60
an open space
for the new 50
50
element. 40
40
30
30 20
20
10
10 0
0 [1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 How to Insert One Element

• Shift elements
in the sorted
70
side, creating
an open space 60
for the new 50
element. 40
30
20
10
0
[1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 How to Insert One Element

• Continue
shifting 70
70 elements... 60
60 50
50
40
40
30
30 20
20
10
10 0
0 [1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 How to Insert One Element

• Continue
shifting 70
0 elements... 60
0 50
0
40
0
30
0 20
0
10
0 0
0 [1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 How to Insert One Element

• ...until you
reach the 70
70
location for the 60
60 new element. 50
50
40
40
30
30 20
20
10
10 0
0 [1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 How to Insert One Element

• Copy the new Sorted side Unsorted side

element back
70
into the array,
70
at the correct 60
60 location. 50
50
40
40
30
30 20
20
10
10 0
0 [1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 How to Insert One Element

• The last Sorted side Unsorted side

element must
70
also be
60
inserted. Start
by copying it... 50
40
30
20
10
15 0
[1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 A Test

How many shifts

will occur before
70
we copy this
70
element back into 60
60
the array? 50
50
40
40
30
30 20
20
10
10 15 0
0 [1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 A Test

• Four items
are shifted. 70
70
60
60 50
50
40
40
30
30 20
20
10
10 0
15
0 [1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 A Test

• Four items
are shifted.
70
70 • And then the 60
60 element is
50
50
copied back
into the 40
40
array. 30
30 20
20
10
10 15 0
0 [1]
[0] [2]
[1] [3]
[2] [4]
[3] [5]
[4] [6]
[5]
[1] [2] [3] [4] [5] [6]
 The insertion sort algorithm

def insertionSort(elemType a[], int count)

Loop (for next = 1 to count – 1)
insert  a[next]
move  next
Loop (while move > 0 && a[move – 1] > insert)
// Shift to right
a[move]  a[move – 1]
move  move - 1
End Loop
// Insert item in correct position
a[move]  insert
End Loop
 Timing and Other Issues
• Both Selectionsort and Insertionsort have a worst-
case time of O(n2), making them impractical for large
arrays.
• But they are easy to program, easy to debug.
• Insertionsort also has good performance when the
array is nearly sorted to begin with.
• But more sophisticated sorting algorithms are needed
when good performance is needed in all cases for large
arrays.
 The bubble sort algorithm

• Bubble sort is based on the idea of repeatedly comparing pairs of adjacent

elements and swap their positions if they exists in the wrong order.
• Another words a bigger elements will 'bubble' towards the end and the
smaller elements will 'bubble' towards the beginning until all elements are in
the correct location.
 The bubble sort algorithm

• Step 0 : Initialize n to length of the array

• Step 1 : Initialize j to 0 and compare a[j] with a[j+1] (compare adjacent elements
starting from 0th index)
• Step 2 : if a[j] > a[j+1] swap a[j] and a[j+1]
• Step 3 : repeat steps 1 and 2 until j reached end of the array ( by end of this one
element will be placed at its correct order )
• Step 4 : continue from Step 1 to n-1 times ( so that all elements will be in proper
order)
 The bubble sort algorithm

Iteration 1 :
 The bubble sort algorithm

Iteration 2 :
 The bubble sort algorithm

Iteration 3 :
 The bubble sort algorithm

Iteration 4 :
 The bubble sort algorithm

Iteration 5 :
 The bubble sort algorithm

Iteration 6 :
 The bubble sort algorithm
def bubbleSort(elemType a[], int count)
Loop (for i =0 to i < count ) def swap(lhs, rhs)
{
// compare adjacent elements starting from 0th index tmp = lhs;
lhs = rhs;
Loop (for index = 0 to count-1) rhs = tmp;
}
If (a[index] > a[index+1] Then
Swap a[index] and a[index+1]
End If
End Loop
End Loop
 Mergesort Algorithm

Mergesort algorithm is one of two important divide-and-

conquer sorting algorithms (the other one is quicksort).
It is a recursive algorithm.
– Divides the list into halves,
– Sort each halve separately, and
– Then merge the sorted halves into one sorted array.
# MergeSort i=j=k=0
def mergeSort(arr):
# Copy data to temp arrays L[] and R[]
if (len(arr)==1):
while i < len(L) and j < len(R):
return if L[i] <= R[j]:
if len(arr) > 1: arr[k] = L[i]
i += 1
# Finding the mid of the array
else:
mid = len(arr) // 2 arr[k] = R[j]
# Dividing the array elements j += 1
k += 1
# into 2 halves
L = arr[:mid] # Checking if any element was left
R = arr[mid:] while i < len(L):
arr[k] = L[i]
i += 1
# Sorting the first half k += 1
mergeSort(L)
while j < len(R):
# Sorting the second half arr[k] = R[j]
mergeSort(R) j += 1
k += 1
 pivot
Quicksort
• Algorithm left subarray right subarray

• Divides array into 2 parts by choosing a pivot

value
• All items less than the pivot are placed in the
left side of pivot.
• All items greater than the pivot are placed in
the right side of pivot.
• Invented by Tony Hoare
 Quicksort

• An element is in the sorted position if all the elements in the left-hand side
are smaller than this element and all the elements on the right-hand side
are bigger than this element
10 80 90 60 50 30
2356819
4 6 7 10 14 12 16 20
• It is also one of the divide-and-conquer sorting algorithms
 Quicksort Algorithm

Given an array of n elements (e.g., integers):

• If array only contains one element, return
• Else
– pick one element to use as pivot.
– Partition elements into two sub-arrays:
• Elements less than or equal to pivot
• Elements greater than pivot

– Quicksort two sub-arrays

– Return results
Algorithm

def quicksort(a, lo, hi): #lo=0 , hi= len(a)-1

if lo < hi:
pv = partition(a, lo, hi)
quicksort(a, lo, pv-1)
quicksort(a, pv + 1, hi)
def partition(a, lo, hi):
pivot = a[lo]
i = lo
j = hi
while i < j:

while a[i] <= pivot and i < hi:

i += 1
while a[j] > pivot and j > lo:
j -= 1
if i < j:
a[i], a[j] = a[j], a[i]

a[lo], a[j] = a[j], a[lo]

return j
Step-by-step breakdown:
[Link] = a[lo]: The first element of the given range (a[lo]) is selected as the

pivot.
2.i=lo, j=hi: Two index pointers are initialized. i starts at the beginning of the

range (lo), and j starts at the end (hi).

[Link](i<j): The main loop continues as long as the i pointer is less than

the j pointer.
[Link] (a[i]<= pivot and i<hi) i++: This inner loop moves the i pointer to the right
as long as the element at a[i] is less than or equal to the pivot, and i has not
reached the end of the range (hi).
[Link](a[j]> pivot and j>lo) j--: This inner loop moves the j pointer to the left as long as

the element at a[j] is greater than the pivot, and j has not reached the beginning of the
range (lo).

[Link](a[i],a[j]): When the inner loops stop, i and j are pointing to elements that are in

the wrong partitions (an element greater than or equal to the pivot at index i, and an
element less than or equal to the pivot at index j). These two elements are swapped.

:
[Link](a[lo],a[j]) After the while(i<j) loop finishes, j is the final position of the pivot.

This line swaps the original pivot element (a[lo]) with the element at index j, placing
the pivot in its correct sorted position.
[Link] j: The function returns the final index j, which is the position of the pivot

after the partitioning is complete.