Sort Algorithm
DATA STRUCTURE
Jay G. Cantonjos
MIT - 1
Sort Algorithm
is an algorithm that puts elements
of a list in a certain order.
sorting is important for optimizing
the use of other algorithms
Data Structure: Sort Algorithm
The Sort algorithm reorders a List
so that its elements are in
ascending order according to an
ordering relationship.
Data Structure: Sort Algorithm
Bubble Sort
a sorting technique that is
typically used for sequencing
small lists.
makes quite inefficient for sorting
large data volumes.
Bubble sort is slow algorithm.
Data Structure: Sort Algorithm
The algorithm works as follows:
1. Find the minimum value in
the list
2. Comparing each pair of
adjacent items
3. Swapping them if they are in
the wrong order.
Data Structure: Sort Algorithm
Bubble Sort
Data Structure: Sort Algorithm
Bubble Sort
Data Structure: Sort Algorithm
Selection Sort
is a sorting algorithm, specifically
an in-place comparison sort.
noted for its simplicity, and also
has performance advantages over
more complicated algorithms in
certain situations
Data Structure: Sort Algorithm
The algorithm works as follows:
1. Find the minimum value in
the list
2. Swap it with the value in the
first position
Data Structure: Sort Algorithm
3. Repeat the steps above for the
remainder of the list (starting at
the second position and
advancing each time)
Data Structure: Sort Algorithm
Selection Sort
Data Structure: Sort Algorithm
Selection Sort
Data Structure: Sort Algorithm
Merge Sort
merge sort is based on the divide-
and-conquer paradigm.
its worst-case running time has a
lower order of growth than
insertion sort.
Data Structure: Sort Algorithm
The algorithm works as follows:
1. Divide the unsorted list into
n sublists, each containting 1
element
2. Repeatedly Merge sublists to
produce new sublists until there
is only 1 sublist remaining.
Note: A list of 1 element is considered sorted.
Data Structure: Sort Algorithm
Merge Sort
Data Structure: Sort Algorithm
Merge Sort
Data Structure: Sort Algorithm
Quick Sort
quick sort is a fast sorting algorithm.
Quicksort (also known as
"partition-exchange sort")
is a comparison sort and, in
efficient implementations, is not a
stable sort.
Data Structure: Sort Algorithm
The algorithm works as follows:
1. Choose a pivot value. We take
the value of the middle element
as pivot value, but it can be any
value, which is in range of sorted
values, even if it doesn't present
in the array.
Data Structure: Sort Algorithm
2. Partition. Rearrange elements in
such a way, that all elements
which are lesser than the pivot go
to the left part of the array and all
elements greater than the pivot, go
to the right part of the array.
Data Structure: Sort Algorithm
Values equal to the pivot can stay
in any part of the array. Notice,
that array may be divided in non-
equal parts.
3. Sort both parts. Apply quicksort
algorithm recursively to the left
and the right parts.
Data Structure: Sort Algorithm
Quick Sort
Data Structure: Sort Algorithm
Quick Sort
Data Structure: Sort Algorithm
Insertion Sort
is the most conceptually simple
of all the sorting algorithms.
efficient for (quite) small data sets
Data Structure: Sort Algorithm
The algorithm works as follows:
It works the way you might sort a hand of
playing cards:
1. We start with an empty left hand
[sorted array] and the cards face
down on the table [unsorted array].
Data Structure: Sort Algorithm
2. Then remove one card [key] at a
time from the table [unsorted
array], and insert it into the correct
position in the left hand [sorted
array].
Data Structure: Sort Algorithm
3. To find the correct position for
the card, we compare it with each
of the cards already in the hand,
from right to left.
Data Structure: Sort Algorithm
Insertion Sort
Data Structure: Sort Algorithm
Insertion Sort
Data Structure: Sort Algorithm
Data Structure: Sort Algorithm
Thank You
Data Structure: Sort Algorithm
