What are Data Structures?

 Definition: Data structures are ways to store and organize data

efficiently to enable fast and easy access, modification, and processing
 Purpose: The right data structure enables optimal performance and
resource utilization in applications and algorithms.

Types of Data Structures:

 Linear Structures: Organize data sequentially (e.g., Arrays, Linked
Lists, Stacks, Queues).
 Non-linear Structures: Allow complex relationships and hierarchies
(e.g., Trees, Graphs).

Real-World Use Cases:

 Arrays for storing a fixed number of items (like a list of student scores).
 Linked Lists for dynamic data storage and efficient insertions.
 Trees for representing hierarchical data, like file directories.
 Graphs for mapping networks, social connections, and routing paths.
1
Sorting and Searching
 Fundamental problems in computer science
and programming
 Sorting done to make searching easier
 Multiple different algorithms to solve the
same problem
– How do we know which algorithm is "better"?
 Look at searching first
 Examples will use arrays of ints to illustrate
algorithms

CS 307 Fundamentals of 2
Computer Science Sorting and Searching
Searching

3
Sorting and Searching
Searching
 Given a list of data find the location of a
particular value or report that value is not
present
 linear search
– intuitive approach
– start at first item
– is it the one I am looking for?
– if not go to next item
– repeat until found or all items checked
 If items not sorted or unsortable this
approach is necessary
4
Linear Search
/* pre: list != null
post: return the index of the first occurrence
of target in list or -1 if target not present in
list
*/
public int linearSearch(int[] list, int target) {
for(int i = 0; i < list.length; i++)
if( list[i] == target )
return i;
return -1;
}

CS 307 Fundamentals of 5
Computer Science Sorting and Searching
Linear Search, Generic
/* pre: list != null, target != null
post: return the index of the first occurrence
of target in list or -1 if target not present in
list
*/
public int linearSearch(Object[] list, Object target) {
for(int i = 0; i < list.length; i++)
if( list[i] != null && list[i].equals(target) )
return i;
return -1;
}

T(N)? Big O? Best case, worst case, average case?

CS 307 Fundamentals of 6
Computer Science Sorting and Searching
Binary Search
 If items are sorted then we can divide and
conquer
 dividing your work in half with each step
– generally a good thing
 The Binary Search on List in Ascending order
– Start at middle of list
– is that the item?
– If not is it less than or greater than the item?
– less than, move to second half of list
– greater than, move to first half of list
– repeat until found or sub list size = 0
CS 307 Fundamentals of 7
Computer Science Sorting and Searching
Binary Search
list

low item middle item high item

Is middle item what we are looking for? If not is it
more or less than the target item? (Assume lower)

list

low middle high

item item item
CS 307 Fundamentals of
and so forth…
8
Computer Science Sorting and Searching
Binary Search in Action
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
public static int bsearch(int[] list, int target)
{ int result = -1;
int low = 0;
int high = list.length - 1;
int mid;
while( result == -1 && low <= high )
{ mid = low + ((high - low) / 2);
if( list[mid] == target )
result = mid;
else if( list[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return result;
}
// mid = ( low + high ) / 2; // may overflow!!!
// or mid = (low + high) >>> 1; using bitwise op
CS 307 Fundamentals of 9
Computer Science Sorting and Searching
Trace When Key == 3
Trace When Key == 30

Variables of Interest?

CS 307 Fundamentals of 10
Computer Science Sorting and Searching
Sorting

CS 307 Fundamentals of 11
Computer Science Sorting and Searching
Sorting
 Sorting Basics in Computers
 Sorting helps computers find data faster.
 There are many different ways to sort data (called "sorting
algorithms").
 A challenge in sorting is when data is stored in a fixed-size container
(like an array).
 If we need to make this container bigger, it can slow things down.
 Simple Sorting Methods (Take more time, around O(N²)):
 Bubble Sort: Repeatedly swaps items to move the largest to the
end.
 Selection Sort: Finds the smallest item and puts it in the right spot,
one by one.
 Insertion Sort: Adds each new item in the correct place within the
sorted section.
 Quick Sort: A faster, more efficient sorting method for many cases
12
Quicksort
 Quick Sort
 Invented by: C.A.R. (Tony) Hoare
 How It Works: Uses a "divide and conquer" method with recursion
(a process that calls itself).
 Steps:
– If the list has 0 or 1 items, it’s already sorted.
– Pick an item in the list to be the pivot (a reference point).
– Divide the other items into two groups:
• Items less than the pivot.
• Items greater than the pivot.
– Sort each group separately with quicksort and combine them for
the final sorted list.

13
Quicksort in Action
39 23 17 90 33 72 46 79 11 52 64 5 71
Pick middle element as pivot: 46
Partition list
23 17 5 33 39 11 46 79 72 52 64 90 71
quick sort the less than list
Pick middle element as pivot: 33
23 17 5 11 33 39
quicksort the less than list, pivot now 5
{} 5 23 17 11
quicksort the less than list, base case
quicksort the greater than list
Pick middle element as pivot: 17
and so on….
CS 307 Fundamentals of 14
Computer Science Sorting and Searching
Quicksort on Another Data Set
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
44 68 191 119 119 37 83 82 191 45 158 130 76 153 39 25

Big O of Quicksort?
15
public static void swapReferences( Object[] a, int index1, int index2 )
{ Object tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
public void quicksort( Comparable[] list, int start, int stop )
{ if(start >= stop)
return; //base case list of 0 or 1 elements
int pivotIndex = (start + stop) / 2;
// Place pivot at start position
swapReferences(list, pivotIndex, start);
Comparable pivot = list[start];
// Begin partitioning
int i, j = start;
// from first to j are elements less than or equal to pivot
// from j to i are elements greater than pivot
// elements beyond i have not been checked yet
for(i = start + 1; i <= stop; i++ )
{ //is current element less than or equal to pivot
if(list[i].compareTo(pivot) <= 0)
{ // if so move it to the less than or equal portion
j++;
swapReferences(list, i, j);
}
}
//restore pivot to correct spot
swapReferences(list, start, j);
quicksort( list, start, j - 1 ); // Sort small elements
quicksort( list, j + 1, stop ); // Sort large elements
}
16