CSE408

Bubble sort
Maximum & Minimum
Lecture #16
Why Study Sorting Algorithms?

• There are a variety of situations that we can

encounter
– Do we have randomly ordered keys?
– Are all keys distinct?
– How large is the set of keys to be ordered?
– Need guaranteed performance?

• Various algorithms are better suited to some of

these situations
Some Definitions

• Internal Sort
– The data to be sorted is all stored in the computer’s
main memory.
• External Sort
– Some of the data to be sorted might be stored in
some external, slower, device.
• In Place Sort
– The amount of extra space required to sort the
data is constant with the input size.
Bubble Sort

• Idea:
– Repeatedly pass through the array
– Swaps adjacent elements that are out of order
i
1 2 3 n

8 4 6 9 2 3 1
j

• Easier to implement, but slower than Insertion sort

Example
8 4 6 9 2 3 1 1 8 4 6 9 2 3
i=1 j i=2 j

8 4 6 9 2 1 3 1 2 8 4 6 9 3
i=1 j i=3 j

8 4 6 9 1 2 3 1 2 3 8 4 6 9
i=1 j i=4 j

8 4 6 1 9 2 3 1 2 3 4 8 6 9
i=1 j i=5 j

8 4 1 6 9 2 3 1 2 3 4 6 8 9
i=1 j i=6 j

8 1 4 6 9 2 3 1 2 3 4 6 8 9
i=1 j i=7
j
1 8 4 6 9 2 3
i=1 j
Bubble Sort

Alg.: BUBBLESORT(A)
for i  1 to length[A]
do for j  length[A] downto i + 1
do if A[j] < A[j -1]
i then exchange A[j]  A[j-1]
8 4 6 9 2 3 1
i=1 j
Bubble-Sort Running Time
Alg.: BUBBLESORT(A)
for i  1 to length[A] c1
do for j  length[A] downto i + 1 c2
Comparisons:  n2/2 do if A[j] < A[j -1] c3
Exchanges:  n2/2 then exchange A[j]  A[j-1] c4
n n n

T(n) = c1(n+1) + c2  (n  i  1)  c3  (n  i )  c4  (n  i)
i 1
i 1 i 1
n

= (n) + (c2 + c2 + c4)  (n  i )

i 1
2
n n n
n ( n  1) n n
where  (n  i )  n   i  n 2   
i 1 i 1 i 1 2 2 2
Thus,T(n) = (n2)
Selection Sort
• Idea:
– Find the smallest element in the array
– Exchange it with the element in the first position
– Find the second smallest element and exchange it
with the element in the second position
– Continue until the array is sorted
• Disadvantage:
– Running time depends only slightly on the amount
of order in the file
Example
8 4 6 9 2 3 1 1 2 3 4 9 6 8

1 4 6 9 2 3 8 1 2 3 4 6 9 8

1 2 6 9 4 3 8 1 2 3 4 6 8 9

1 2 3 9 4 6 8 1 2 3 4 6 8 9
Selection Sort

Alg.: SELECTION-SORT(A) 8 4 6 9 2 3 1

n ← length[A]
for j ← 1 to n - 1
do smallest ← j
for i ← j + 1 to n
do if A[i] < A[smallest]
then smallest ← i
exchange A[j] ↔ A[smallest]
Analysis of Selection Sort
Alg.: SELECTION-SORT(A)
n ← length[A] cost
for j ← 1 to n - 1 times
do smallest ← j c1 1
for i ← j + 1 to n c2 n
n2/2
do if A[i] < A[smallest]
c3  j 1 (nn-
n 1
 j  1)
comparisons
then smallest ← i

n 1
1 j 1
(n  j )
n exchange A[j] ↔ A[smallest]

n 1
exchanges c4 j 1
(n  j )

n 1 n 1 n 1
c5
T (n)  c1  c2 n  c3 (n  1)  c4  ( n  j  1)  c5   n  j   c6   n  j   c7 (n  1)  (n 2 )
j 1 j 1 j 2
MINIMUM AND MAXIMUM