Loading...

SortDouble Implementation

Course video 20 of 26

In this module we continue studying algorithmic challenges of the string algorithms. You will learn an O(n log n) algorithm for suffix array construction and a linear time algorithm for construction of suffix tree from a suffix array. You will also implement these algorithms and the Knuth-Morris-Pratt algorithm in the last Programming Assignment in this course.

Algorithms on Strings

University of California San Diego

Course 4 of 6 in the Data Structures and Algorithms Specialization

World and internet is full of textual information. We search for information using textual queries, we read websites, books, e-mails. All those are strings from the point of view of computer science. To make sense of all that information and make search efficient, search engines use many string algorithms. Moreover, the emerging field of personalized medicine uses many search algorithms to find disease-causing mutations in the human genome.

Skills You'll Learn

Suffix Tree, Suffix Array, Knuth–Morris–Pratt (KMP) Algorithm, Algorithms On Strings

Taught By

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Pavel Pevzner
Professor
Neil Rhodes
Adjunct Faculty

Transcript

Now lets consider the pseudocode for the procedure SortDoubled which will sort

the doubled cycled shifts of length to L, given the string S.

The current length L, the order of the current shifts of length L, and

their equivalents classes in the array class.

We'll start with initializing the array count with the zero array of size

equal to the length of the string this is the standard array for counting sort,

but as oppose to sort characters procedure it will sort not characters,

but equivalents classes of cyclic shift of length L.

And there are at most length of S difference including classes

that's why we initialized the array with size length of the string.

As opposed to sort characters where we initialized it with the size

of the alphabet.

We'll also need another array new order, which will store our answer.

It will be the order of the sorted doubled cyclic shift.

We initialize it with area of size, length of S.

The next two four loops are standard four loops for the counting sort.

When we first count the number of occurrences of each equivalence class of

single cyclic shifts and then we compute the partial sums of that counting array

and the last four loop of the counting sort needs to go through the array.

We're going to sort from the end to the beginning and that is important for

the sort to be stable.

So, we need to go through the array of double cyclic shifts which

are initially sorted by their second half in the reverse order.

But you don't want to actually build this array of doubled cyclic shifts and

then go through it in reverse order.

We want to only build this array in our head and

in the code, we just want to go through this array in the reverse order.

So how to do that?

Remember that we have the array order, and if we go in the direct order of this

array, we'll go through all the cyclic shifts of length L in increasing order.

What we need instead is, first,

to go not through cyclic shifts of length L, but through cyclic

shifts of length to L which starts exactly L counter clockwise from those.

And that is why we decrease order I by L and

at length of the string and take modulo S, just because we're going through a circle.

And we need to go downwards from

the last i to the first i, because we need to go in the reverse order.

So these two lines for i from length of S- 1 down to 0.

And the last line which assigns variable starts to

order i minus L plus length of string s module s.

What they basically do is they go with variable start

in the reverse order through the array of double cyclic shifts.

Sorted by their second half.

So start goes through the starts of those double cyclic shifts in the reverse order.

Now, everything else that happens in this for loop is just regular counting sort.

We take the class of this start position, which is the class

of the first half of the corresponding doubled shift by which we want to sort.

Then we go and decrease the partial sum

corresponding to that equivalence class in our counting array.

And then we just put our start in the position

which the counting sort prescribes to it.

So these three lines from getting the clust of the start position

decreasing the partial sum and assigning the start to the position counter

of clause are the three standards lines of the counting sort.

The complexity here is that start is going in the reverse order.

Through the array of double cyclic shifts sorted by their second half and

that we instead of comparing characters or

something else we compare equivalence classes of the single cyclic shift.

So this is what this last forlob does.

And in the end what we have is the array new order.

Which contains the double cyclic shifts which were initially sorted by

their second half and then we sorted them by count and sort, by their first half.

And so now they are sorted by the first half and the count and sort was stable.

So in case when their first part, first half is the same, they're

also sorted by the second half, because they were sorted by second half initially.

So new order finally contains all the dabbled cyclic shifts

in the correct order, in the sorted order.

So this is the function that sorts all the doubled cyclic shifts.

And the running time of this procedure is linear

because this is basically the regular counting sort.

Although it sorts very complex objects, in practice in the code,

it just sorts integers, the equivalent classes of

the single cyclic shifts and it does so in the running time of the counting

sort which runs in the time number of items plus number of different values.

Number of items is equal to length of the string and the number of different values

of a clauses is also to smallest length of the stream.

So all in all, those three for loops run in linear time.

In the next video, we will talk about how to

update the classes of those double cyclic shifts after they are sorted,

and how to finally build the suffix array from scratch.

About Coursera

Courses, Specializations, and Online Degrees taught by top instructors from the world's best universities and educational institutions.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play