Data Structure Lecture Note (Week 2, Lecture 4)

• Array
• Sorting by: bubble sort, merge sort, and quicksort
• worst case analysis
• Simple average case analysis
• Lower bound for sorting algorithms
• Linear time sorting algorithms

---

Abstract Data Type (ADT)

Describe its behaviour by language, not directly implemented by you.

Example: array. Typically all elements are of the same data type. Each element is identified and accessed by a number j called index. V = [1,2,3,4,5,6]

• Fetch and replace
• insertion and deletion (vector ADT)

In C++ and many languages, array is an elementary data structure, allocated continuously in memory

Each access to X[i] is in constant time due to smart circuit design.

Operations: insertion: O(n), delete: O(n) [Worst case]; Replace: O(1)

---

Subarrary of A: the array whose elements are part of the original array A without changing the ordering

[1,…,X] to say a continous subarray

---

2D array, matrix

X = [[1,2,3], [4,5,6], [7,8,9]], say mxn matrix

X[i * n + j] = X [i] [j] (How C++ implements )

---

Sorting Algorithms

Naive sorting: bubble sort

while (there is a j such that A[j] > A[j+1]) do {
	switch A[j] and A[j+1]
}

O(n^3)

Slightly more advanced:

while (A is not in ascending order) do {
	for each j in {0,1,...,n-2} do 
		if A[j] > A[j+1] then
			switch A[j] and A[j+1]
}

Observe that the for loop will bubble the largest number to the end of the array always, so at most n times!

Worst case: O(n^2), Best case: O(n)

---

Average running time of bubble sort?

Merge Sort

Divide and Conquer Approach.

Merge two sorted array, each N/2, time complexity O(N)

In-place merge: not allow to use extra place. Naive one takes O(N^2) time, as worse as bubble sort. It’s difficult to find a smart way…

BAD: have to use extra linear place (It’s probably fine in 2020, not in 1990 lol)

---

Best case and Worst case: O(nlog n)

Quick Sort

Idea: Find an element e as a pivot, divide the array A by e, if numbers are larger than e, put the numbers to the right of e, if numbers are smaller, put to the left. Then iterate on both left and right side

qsort(A, h, t) {
	if (h < t) 
		q = partition(A, h, t)
		qsort(A, h, q-1)
		qsort(A, q+1, t)
}

call qsort(A, 0, n-1) to begin

partition is the algorithm to select an element to be a pivot. Then put the numbers less than A[q] to the left, and numbers larger than A[q] to the right.

(how to select the pivot? how to do in-place? )

2-pass algorithm:

First loop through and see p is the ?-th element. Insert p into that element.

Insert the element other than p to the left if smaller than p, O/W to the right.

1-pass algorithm:

1. Let’s assume we pick p = A[0], O/W, do a switch
2. now scan from the beginning and from the tail at the same time
3. Derease t to find an element such that A[t] < p, switch numbersin h and t
4. increase t to find an element such that A[h]>p, sweitch numbers of h and t
5. repeat last 2 steps until h==t
6. Claim: p will go to the right position
   • We are always switching p with someone, until h==t, and according to the algotithm, at any time, for any number before h index, it will be smaller than p and for any number after t index, it will be larger than p.

---

Average Case Analysis (Elementary)

Review of permutation.

Claim: comparation-based algorithm: sorting (10, 20, 5, 3, 100) is the same as sorting (3, 4, 2, 1, 5)

Let T§ be the running time of the sorting algorithm A for the permutation P, then
$T_{avg} (A) = \frac{\sum_P T(P)} {N!}$Tavg​(A)=N!∑P​T(P)​
(usually assume uniform ditribution)

Review of discrete prob basics

For sorting average case analysis

Probability space $\Omega = $ all permutations of 1 to N

Ditribution is uniformly random among all permutations

---

I think the average running time analysis is very complicated …