Introduction to Data Structure & Algorithms in Java - Part 3

Other Sorting Algorithms

Introduction

• Quick short

• Shell sort

• Counting sort

• Radix sort

• Bucket sort

Quicksort

• Worse case: O(

• Average case: O()

Quicksort(A, start, end)
	if start < end
		pivot = Partition(A, start, end)
		Quicksort(A, start, pivot-1)
		Quicksort(A, pivot + 1, end)

Quicksort: The partitioning step

Partition(A, start, end)
	pivot = A[end]
	i = start
	for j = start to end - 1
		if A[j] <= pivot
			exchange A[i] with A[j]
			i += 1
	exchange A[i] with A[end]
	return i

Shell sort

• Assume we are sorting this array using the Insertion sort

• After a few steps, we have the left items sorted

• Now, we need to insert 10 into the left-sorted items

• We have to move all those sorted items to the right

• Instead of sorting all items, we do sort a few items with a gap = 3

• And continue sorting with other items with gap = 3 until gap times

• How do we choose the gap?

• we often choose a big gap, ex: 121

• Then we reduce the gap until 1

Shell sort example

• Assume we have array with 100 items need to be sorted

• We choose gap = 40

• So, there are 3 items at index 0, 40, and 80 will be sorted

• Then loop them for other items with same gap 40

• After first iteration, the result looks like this one on the left

• Next iteration, we reduce the gap to 13

• And do same for gap = 4

• In the last iteration, the gap = 1

• We will sort all items

• We often choose insertion sort

• shell sort time complexity: O() - O()

Counting sort

• Assume we need to sort the marks of students

• We know that the values of marks are only from 0 to 10

• n is number of items of array need to be sorted

• k is distinct values of items in the array and k very very small compared to n

• O(n)

Radix sort

• Assume we have 6 items

• Each item have 3 digits

• First, we sort items by unit digits

• Then, we sort items by ten digits

• Finally, we sort items by hundreds digits

• O(n)

Bucket sort

• we found that data need to sort are only up to hundreds

• Go through linked list to sort them

Heaps

Introduction

• This is complete binary tree

• This is an incomplete binary tree

• A heap is a binary tree which is
• complete
• every node’s key is larger than or equal to the keys of its children
 

Delete the root

• Delete the root is very often if the heap is priority queue

Inserting an item in a heap

Heaps as priority queues

• Assume we change key from 10 to 25

• We need to fix the heap

• Time complexity to fix it is O()

Representing heaps using arrays

Heap sort

Building a heap

Hashtables

Introduction

Direct access tables

Hashing

Resolving collisions through chaining

The hash function

Open addressing to resolve collisions

Strategies for open addressing

Time complexity: Open addressing

References

• https://www.linkedin.com/learning/introduction-to-data-structures-algorithms-in-java/introduction-7?autoplay=true