Transcript Simple Sorting Algorithms

Data Structure
Introduction
Computer Program?
Computer Program
Problem
Input
(DS)
(Algorithm)
+
Programming language
Output
(DS)
solution
Data Structures+ Algorithms + language = Program
Data structures?
Data may be organized in different ways
Represent the data in a particular way, so that it can be used efficiently
Array
Linked List
in
Stack
Tree
Graph
in
Queue
Data Structures: Definition
• Data structure is the logical or mathematical
model of a particular organization of data
• The model must be :
– Simple:
– Rich: mirror the actual relationships of the data
• The Goal:
to organize data
• Efficiency Criteria
– storage of data
– retrieval of data
– manipulation of data
Data Structure Operations
• Traversing
– Accessing each record exactly once so that certain
items in the record may be processed
• Searching
– Finding the location of the record with the given
key value or finding the location of all records
which satisfy one or more conditions
• Insertion
– Adding a new record to the structure
• Deletion
– Removing a record from the structure
• Sorting
– Arrange the records in a logical order
• Merging
– Combining records from two or more files or data
structures into one
Data Type
• Data Type
A data type is a collection of objects and a set of
operations that act on those objects.
• Abstract Data Type
An abstract data type(ADT) is a data type that is
organized in such a way that the specification of
the objects and the operations on the objects is
separated from the representation of the objects
and the implementation of the operations.
What is an Algorithm?
• An algorithm is a definite procedure for solving a
problem in finite number of steps
• Algorithm is a well defined computational
procedure that takes some value(s) as input,
and produces some value(s) as output
• Algorithm is finite number of computational
statements that transform input into the output
Algorithm Definition : A finite set of statements
that guarantees an optimal solution in finite
interval of time
Complexity Analysis of Algorithms
• Analyze the running time as a function of n (# of input
elements).
• Efficient Algorithms
– Consumes lesser amount of resources while solving a
problem of size n
• Memory
• Time
Simple Example
// Input: int A[N], array of N integers
// Output: Sum of all numbers in array A
int Sum(int A[], int N){
int s=0;
1
for (int i=0; i< N; i++)
2
s = s + A[i];
5
return s;
}
6
3
4
1,2,6: Once
3,4,5 : Once per each iteration
of for loop, N iteration
The complexity function of the
algorithm is : f(N) = 3N +3
More Examples:
Given the following input, find the grand total = ΣΣ matrix (k,j)
matrix
j
rows
2
3
1
2
1
9
1
2
1
1
2
7
2
1
1
3
1
8
1
2
1
2
0
6
K
GrandTotal
Both Example1 and example2 (in the next slide)
produce the same results
Example - 1:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
GrandTotal = 0;
for (int k = 0 ; k < n-1 ; ++k )
{
rows[ k ] = 0;
for ( int j = 0 ; j < n-1 ; ++j )
{
rows[ k ] = rows[ k ] + matrix[ k ][ j ];
GrandTotal = GrandTotal + matrix[ k ][ j ];
}
}
Example - 2:
Example-1 requires 2N2
additions.
1. GrandTotal = 0;
2. for (int k = 0 ; k < n-1 ; ++k )
3. {
4.
rows[ k ] = 0;
5.
for ( int j = 0 ; j < n-1 ; ++j )
6.
rows[ k ] = rows[ k ] + matrix[ k ][ j ];
7.
8. GrandTotal = GrandTotal + rows[ k ];
9. }
Example-2
additions.
requires N2+N
O-notation
Let g(n) : N ↦ N be a function. Then we have
O(g(n)) = { f(n) : there exist positive constants c and n0 such that
0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
cg(n)
f(n)
Notation: f(n) = O(g(n))
0
meaning: f(n) in O(g(n))
n0
n
Think of the equality as
meaning in the set of
functions
O-notation
Intuition: concentrate on the leading term, ignore
constants
19 n3 + 17 n2 - 3n
2 n lg n + 5 n1.1 - 5
Complexity
O(1)
O(log n)
O(n)
O(n lg n)
O(nb)
O(bn) b > 1
O(n!)
becomes
becomes
O(n3)
n1.1
Term
constant
logarithmic
linear
n log n “linear-logarithmic”
polynomial(n2 :square, n3 :cube)
exponential
factorial
Complexity categories
growth rates of some common complexity functions.
Example1
use big-O notation to analyze the time efficiency of the following
fragment of C++ codes.
1. for ( k=1 ; k <= n/2 ; ++k )
2. {
3.
...
4.
for ( j=1 ; j <= n*n ; ++j )
5.
{
6.
...
7.
}
8. }
n2 * n/2 = n3/2
 O(n3), with c = ½
Example2
1.
2.
3.
4.
5.
6.
7.
8.
n/2 + n2
 O(n2)
for ( k=1 ; k <= n/2 ; ++k )
{
...
}
for ( j=1 ; j <= n*n ; ++j )
{
...
}
Example3
1. while ( k > 1 )
2. {
3.
...
4.
k = k/2 ;
5. }
•
Because the loop control variable is cut in half each time
through the loop, the number of times that statements
inside the loop will be executed is log2n.
•
 O(log2n)
Next:
• Search Algorithms
– Linear search
– Binary search
• Simple Sorting Algorithms
– Bubble sort
– Insertion sort
– Selection sort
Simple Search Algorithms
CS250-Data structure
“Sequential search” or Linear
Linear-Search[A, n, x]
• scan the entries in A and compare each
1
for i ← 1 to n
entry with x. If after j comparisons, 1 ≤ j ≤
if A[i] = x
n, the search is successful, i.e., x = A[j], j is 2
returned; otherwise a value of 0 is returned 3
return i
indicating an unsuccessful search.
4
else i ← i + 1
5
return 0
• Let x=55  unsuccessful search
• x=54  successful search i=5
LINEARSEARCH
algorithm is in the class
O(n)
Binary-Search
begin the search in the middle of the list &
compare the data of that middle to the
target.
If A[mid] = target  successful search
If A[mid] < target  search again in
the upper part of the list
If A[mid] > target  search again in
the lower part of the list
Each comparison or iteration reduces
the search space to half N/2
Untill item is found or space is out of
range.
Complexity O(logn)
Binary-Search[A, n, x]
1 low ← 1
2 high ← n
3 while low ≤ high
4 mid ← (low + high)/2
5 if A[mid] = x
6
return mid
7
elseif A[mid] < x
8
low ← mid + 1
9
else high ← mid − 1
10 return 0
A[1..14] =
1
4
5
7
8
9
10
12
15
22
23
27
32
35
1
2
3
4
5
6
7
8
9
10
11
12
13
14
In this instance, we want to search for element x = 22.
• First, we compare x with the middle element A[└(1 + 14)/2┘] = A[7]
= 10. Since 22 > A[7], and since it is known that A[i] <= A[i + 1], 1
<= i < 14, x cannot be in A[1..7], and therefore this portion of the
array can be discarded.
• So, we are left with the subarray
A[8..14] = 12 15 22 23 27
32
35
12
13
14
12
15
22
8
9
10
8
• Repeating this procedure
9
10
A[8..10] =
• Finally, we find that x = A[10], and the search is successfully
completed.
11
Example: Searching for x = 35 or any value greater than 35. The array is
sorted in nondecreasing order. A[1..14] =
4
5
7
8
9
10
12
15
22
23
27
32
35
2
3
4
5
6
7
8
9
10
11
12
13
14
1
1
15
22
23
27
32
35
9
10
11
12
13
14
12
8
27
32
35
12
13
14
35
14
Simple Sorting Algorithms
CS250-Data structure
The Sorting Problem
Input: a sequence of n numbers A=‹a1, a2, …,
an›
Re-arrange an array A of n numbers to be in non-escending
order.
• simple sorting techniques:
– Bubble Sort.
– Selection Sort.
– Insertion Sort.
Selection Sort
In the selection sort, we find the
smallest value in the array
and move it to the first index,
then we find the nextsmallest value and move it to
the second index, and so on.
7
2
8
5
4
2
7
8
5
4
2
4
8
5
7
2
4
5
8
7
2
4
5
7
8
Selection Sort Algorithm
Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in nondecreasing order.
1. for i  1 to n - 1
2. k  i
3. for j  i + 1 to n {Find the i th smallest element.}
4.
if A[j] < A[k] then k  j
5. end for
6. if k  i then swap( A[i] , A[k])
7. end for


The outer loop iterates n-1 times.
The inner loop iterates n-i times





There is a comparison in each iteration.
The sort method executes swap() once on each iteration
of its outer loop
The total number of swap is O(n)
The total number of comparisons = (n-1)+(n-2)+…+2+1 =
n(n-1)/2 = O(n2)
The total cost of the selection sort is : O(n2)
Code for Selection Sort
public static void selectionSort(int[] a) {
int outer, inner, min;
for (outer = 0; outer < a.length - 1; outer++) { // outer counts down
min = outer;
for (inner = outer + 1; inner < a.length; inner++) {
if (a[inner] < a[min]) {
min = inner;
}
// Invariant: for all i, if outer <= i <= inner, then a[min] <= a[i]
}
// a[min] is least among a[outer]..a[a.length - 1]
int temp = a[outer];
a[outer] = a[min];
a[min] = temp;
// Invariant: for all i <= outer, if i < j then a[i] <= a[j]
}
}