Data Structure

Lecture (7)
 Array
(Cont.)
 Introduction To Sorting
• Sorting means arranging the elements of an array so that they are placed in
some relevant order which may be either ascending or descending.
• If A is an array, then the elements of A are arranged in an ascending order in
such a way that A[0] < A[1] < A[2] < ...... < A[N].
• For example, if we have an array that is declared and initialized as:

• Then the sorted array (ascending order) can be given as:

 Bubble Sort
• Bubble sort is a very simple method that sorts the array elements by repeatedly
moving the largest element to the highest index position of the array segment
(in case of arranging elements in ascending order).
• In bubble sorting, consecutive adjacent pairs of elements in the array are
compared with each other.
• If the element at the lower index is greater than the element at the higher
index, the two elements are interchanged so that the element is placed before
the bigger one.
• This process will continue till the list of unsorted elements exhausts.
 Bubble Sort
• This procedure of sorting is called bubble sorting because elements ‘bubble’ to
the top of the list.
• At the end of the first pass, the largest element in the list will be placed at the
end of the list.
• If the elements are to be sorted in descending order, then in first pass the
smallest element is moved to the highest index of the array.
 Bubble Sort
Technique for bubble sort (ascending order):
• In Pass 1:
➢ A[0] and A[1] are compared,
➢ then A[1] is compared with A[2],
➢ A[2] is compared with A[3], and so on.
➢ Finally, A[N–2] is compared with A[N–1].
➢ Pass 1 involves n–1 comparisons and places the biggest element at the
highest index of the array.
 Bubble Sort
• In Pass 2:
➢ A[0] and A[1] are compared,
➢ then A[1] is compared with A[2],
➢ A[2] is compared with A[3], and so on.
➢ Finally, A[N–3] is compared with A[N–2].
➢ Pass 2 involves n–2 comparisons and places the second biggest element
at the second highest index of the array.
 Bubble Sort
• In Pass 3:
➢ A[0] and A[1] are compared,
➢ then A[1] is compared with A[2],
➢ A[2] is compared with A[3], and so on.
➢ Finally, A[N–4] is compared with A[N–3].
➢ Pass 3 involves n–3 comparisons and places the third biggest element at
the third highest index of the array.
 Bubble Sort
• In Pass n–1:
➢ A[0] and A[1] are compared so that A[0] < A[1].
• After this step, all the elements of the array are arranged in ascending order.

• For example, Consider an array A that has the following elements:

 Bubble Sort

• After the end of the first pass, the largest element is placed at the highest
index of the array. All the other elements are still unsorted
 Bubble Sort

• After the end of the second pass, the second largest element is placed at the
second highest index of the array. All the other elements are still unsorted.
 Bubble Sort

• After the end of the third pass, the third largest element is placed at the third
highest index of the array. All the other elements are still unsorted.
 Bubble Sort

• After the end of the fourth pass, the fourth largest element is placed at the
fourth highest index of the array. All the other elements are still unsorted.
 Bubble Sort

• After the end of the fifth pass, the fifth largest element is placed at the fifth
highest index of the array. All the other elements are still unsorted.
 Bubble Sort

• After the end of the sixth pass, the sixth largest element is placed at the sixth
largest index of the array. All the other elements are still unsorted.

• The entire list is sorted now.

 Bubble Sort
Algorithm
• The outer loop is for the total number of passes which
is N – 1.
• The inner loop will be executed for every pass.
• The algorithm for Bubble
Sort of array A having total • The frequency of the inner loop will decrease with
number of elements N is: every pass because after every pass, one element will
be in its correct position.
• Therefore, for every pass, the inner loop will be
executed N – (I + 1) = N – I – 1 times.
 Example
• Write a program to enter n
numbers in an array.
Redisplay the array with
elements being sorted in
ascending order using
bubble sort?
 Insertion Sort
• Insertion sort is a very simple sorting algorithm in which the sorted array is
built one element at a time.
• The main idea behind insertion sort is that it inserts each item into its proper
place in the final list.
• To save memory, most implementations of the insertion sort algorithm work by
moving the current data element past the already sorted values and repeatedly
interchanging it with the preceding value until it is in its correct place.
• Insertion sort is less efficient as compared to other more advanced algorithms.
 Insertion Sort
Technique for insertion sort :
• The array to be sorted is divided into two sets: One that stores sorted values
and another that contains unsorted values.
• Initially, the element with index 0 is in the sorted set while the rest of the
elements are in the unsorted set. Therefore, the first element of the unsorted
set has index 1.
• During each iteration of the algorithm, the first element in the unsorted set is
picked up and inserted into the correct position in the sorted set.
• The algorithm will proceed until there are no elements in the unsorted set.
Insertion Sort
 Insertion Sort
• Initially: A[0] is the only element in the sorted set.
• In Pass 1: A[1] will be placed either before or after A[0], so that the array A
is sorted.
• In Pass 2: A[2] will be placed either before A[0], in between A[0] and A[1], or
after A[1].
• In Pass 3: A[3] will be placed in its proper place.
• In Pass N–1: A[N–1] will be placed in its proper place to keep the array
sorted.
 Insertion
Sort
Algorithm
• To insert an element A[I] in a sorted list A[0], A[1], ...,
A[I–1], we need to compare A[I] with A[I–1], then
• The algorithm for Insertion
with A[I–2], A[I–3], and so on until we meet an
Sort of array A having total
element A[J] such that A[J] <= A[I].
number of elements N is:
• In order to insert A[I] in its correct position, we need
to move elements A[I–1], A[I–2], ..., A[J] by one
position and then A[I] is inserted at the (J+1)th
location.
 Example
• Write a program to enter n
numbers in an array.
Redisplay the array with
elements being sorted in
ascending order using
insertion sort?
 Selection Sort
• Selection sort works by starting at the beginning of the array, comparing the
first element with the other elements in the array.
• First find the smallest value in the array and place it in the first position. Then,
find the second smallest value in the array and place it in the second position.
• Repeat this procedure until the entire array is sorted.
 Selection Sort
Technique for selection sort :
• In Pass 1: find the position POS of the smallest value in the array and then
swap A[POS] and A[0]. Thus, A[0] is sorted.
• In Pass 2: find the position POS of the smallest value in sub-array of N–1
elements. Swap A[POS] with A[1]. Now, A[0] and A[1] is sorted.
• In Pass N–1, find the position POS of the smallest of the elements A[N–2] and
A[N–1]. Swap A[POS] and A[N–2] so that A[0], A[1], ..., A[N–1], i.e., the entire
list, is sorted.
Selection Sort
 Selection
Sort
Algorithm

• The algorithm for Selection • During the Ith pass, we need to find the position POS
Sort of array A having total of the smallest elements from A[I], A[I+1], ..., A[N-1].
number of elements N is:
• To find the smallest element, we use a variable
SMALL to hold the smallest value in the sub-array
ranging from A[I] to A[N-1]. Then, swap A[I] with
A[POS].
 Example
• Write a program to enter n
numbers in an array.
Redisplay the array with
elements being sorted in
ascending order using
selection sort?
Thank You !